Find "edges" in a 32-bit word bitpattern
I'm trying to find the most efficient algorithm for counting "edges" in a bitmap. The edge means a change from 0 to 1, or from 1 to 0. I take a sample of each bit every 250 us and rearrange it into a 32-bit unsigned variable.
This is my algorithm so far
void CountEdges(void)
{
uint_least32_t feedback_samples_copy = feedback_samples;
signal_edges = 0;
while (feedback_samples_copy > 0)
{
uint_least8_t flank_information = (feedback_samples_copy & 0x03);
if (flank_information == 0x01 || flank_information == 0x02)
{
signal_edges++;
}
feedback_samples_copy >>= 1;
}
}
It should be at least 2 or 3 times faster.
source to share
You must be able to XOR together to get a bit pattern representing the flipped bits. Then use one of the bit-counting tricks on this page: http://graphics.stanford.edu/~seander/bithacks.html to calculate how many of them you get.
source to share
One thing that might help is to pre-copy the edge counter for the entire possible 8-bit value (lookup table 512 entries, since you have to include the bit preceding each value) and then add the 1 byte counter at the time.
// prevBit is the last bit of the previous 32-bit word
// edgeLut is a 512 entry precomputed edge count table
// Some of the shifts and & are extraneous, but there for clarity
edgeCount =
edgeLut[(prevBit << 8) | (feedback_samples >> 24) & 0xFF] +
edgeLut[(feedback_samples >> 16) & 0x1FF] +
edgeLut[(feedback_samples >> 8) & 0x1FF] +
edgeLut[(feedback_samples >> 0) & 0x1FF];
prevBit = feedback_samples & 0x1;
source to share
My suggestion:
- copy your input value into a temporary variable, shifted left by one
- copy the LSB of your input to the temt temp variable
- XOR is two values. Each bit set in the result represents one edge.
- use this algorithm to count the number of bits set.
This could be the code for the first three steps:
uint32 input; //some value
uint32 temp = (input << 1) | (input & 0x00000001);
uint32 result = input ^ temp;
//continue to count the bits set in result
//...
source to share
In each iteration, you are looking at only 2 bits.
The fastest algorithm would probably be to create a hash table for all possible values. Since there are 2 ^ 32 values, this is not a good idea.
But why don't you take a look at 3, 4, 5 ... bits in one step? You can, for example, provide your edgecount for all 4-bit combinations. Just take care of the possible edges between the pieces.
source to share