Find "edges" in 32 bits word bitpattern

Question

Im trying to find the most efficient algorithm to count "edges" in a bit-pattern. An edge meaning a change from 0 to 1 or 1 to 0. I am sampling each bit every 250 us and shifting 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 needs to be at least 2 or 3 times as fast.

Answer 1

One thing that may help is to precompute the edge count for all possible 8-bit value (a 512 entry lookup table, since you have to include the bit the precedes each value) and then sum up the count 1 byte at a 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;

Answer 2

Create a look-up table so you can get the transitions within a byte or 16-bit value in one shot - then all you need to do is look at the differences in the 'edge' bits between bytes (or 16-bit values).

Answer 3

You are looking at only 2 bits during every iteration.
The fastest algorithm would probably be to build a hash table for all possibles values. Since there are 2^32 values that is not the best idea.
But why don't you look at 3, 4, 5 ... bits in one step? You can for instance precalculate for all 4 bit combinations your edgecount. Just take care of possible edges between the pieces.

Answer 4

you could always use a lookup table for say 8 bits at a time this way you get a speed improvement of around 8 times

don't forget to check for bits in between those 8 bits though. These then have to be checked 'manually'

Answer 5

You should be able to bitwise XOR them 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 count how many 1's there are in the result.

Answer 6

My suggestion:

• copy your input value to a temp variable, left shifted by one
• copy the LSB of your input to yout temp variable
• XOR the two values. Every bit set in the result value represents one edge.
• use this algorithm to count the number of bits set.

This might be the code for the first 3 steps:

uint32 input; //some value
uint32 temp = (input << 1) | (input & 0x00000001);
uint32 result = input ^ temp;

//continue to count the bits set in result
//...