Can I determine the number of bitwise transitions in an 8-bit integer?

Question

I can't seem to find any little magic, so I was hoping that someone here could shed some light if possible.

I am trying to find the number of bitwise transitions in an 8-bit integer (the integer is actually a 32-bit integer, but I use only the first 8 bits) to determine if 8 bits are uniform (2 or fewer transitions).

For instance:

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 besides loops through each bit (looping through every bit is currently the only solution I can come up with)?

Answer 1

You can x or a value with a value shifted by one bit, and then count the number 1 as a result.

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

Please also note that a byte can contain only 256 configurations, so the calculation can be performed once and placed in a very small table of 256 bytes.

If you just want to find out if there are 2 or less changes, you can expand the loop:

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

Note that this calculation does not depend on how large the number is, and you can use, for example, a 32-bit unsigned number directly (the only thing that changes is the mask, which becomes 0x7FFFFFFF )

Answer 2

To determine uniformity, the number must be in the form 00011111 or 11110000 . Consider the first (zeros followed by ones).

Add a value to the value. If it is uniform, it will have exactly one bit 1 , which means power 2.

To check if a value is a power of two, use (x & (x - 1)) == 0 . To shorten the code, we do not need to add it in the previous step. Instead, we check (x & (x + 1)) == 0

Apply this to another case, NOT specifying the initial value and repeat the process described above.

 #include <cstdio> bool isuniform(unsigned char x) { unsigned char y = ~x; return (x & (x + 1)) == 0 || (y & (y + 1)) == 0; } int main() { printf("%d\n", isuniform(0)); // 00000000 printf("%d\n", isuniform(1)); // 00000001 printf("%d\n", isuniform(3)); // 00000011 printf("%d\n", isuniform(7)); // 00000111 printf("%d\n", isuniform(15)); // 00001111 printf("%d\n", isuniform(31)); // 00011111 printf("%d\n", isuniform(63)); // 00111111 printf("%d\n", isuniform(127)); // 01111111 printf("%d\n", isuniform(255)); // 11111111 printf("%d\n", isuniform(254)); // 11111110 printf("%d\n", isuniform(252)); // 11111100 printf("%d\n", isuniform(248)); // 11111000 printf("%d\n", isuniform(240)); // 11110000 printf("%d\n", isuniform(224)); // 11100000 printf("%d\n", isuniform(192)); // 11000000 printf("%d\n", isuniform(128)); // 10000000 //---------- printf("%d\n", isuniform(2)); printf("%d\n", isuniform(4)); printf("%d\n", isuniform(50)); printf("%d\n", isuniform(123)); printf("%d\n", isuniform(129)); printf("%d\n", isuniform(253)); return 0; }