Possible to determine number of bitwise transitions in an 8 bit integer?

Question

I can't seem to find any bit magic on this, so i was hoping someone here might be able to shed a little light on if this is even possible.

I'm trying to find the number of bitwise transitions in an 8 bit integer (the integer is actually a 32 bit integer, but i'm only using the first 8 bits) to determine if the 8 bits are uniform (2 or less transitions).

For example:

00100000 - two transitions - uniform
00100001 - three transitions - not uniform
10101010 - seven transitions - not uniform
00000000 - no transitions - uniform

Is there a faster way to find the number of transitions other than looping through each bit (looping through each bit is currently the only solution i can come up with)?

Answer 1

You can x-or the value with the value shifted by one bit and then count the number of 1 in the result.

unsigned v = (x ^ (x>>1)) & 0x7F;
unsigned count = 0;
while (v) {
    count++;
    v &= (v - 1);
}

Note also that a byte can only have 256 configurations, so the computation can be done once and put in a very small table of 256 bytes.

If you just want to know if there are 2 or less changes the loop can be unrolled:

unsigned v = (x ^ (x >> 1)) & 0x7F;
v &= v - 1;
v &= v - 1;
uniform = (v == 0);

Note that this computation is independent on how big is the number and you can use for example directly a 32-bit unsigned number (the only thing that changes is the mask that becomes 0x7FFFFFFF)