A quick way to check if an odd number of bits is set?

Question

I need to determine if the number of bits set in a variable of any type (it can be 32-bit unsigned or 64-bit unsigned) is odd or not. I read:

How to count the number of bits in a 32-bit integer?

This, of course, is very useful, but I want to do better, because I need only a binary answer, and not the whole account. I believe replacing a single-byte or double-byte LUT should be pretty quick, but maybe the non-LUT code could be improved in some way.

Answer 1

Solution with pure bits:. Repeat XOR the lower and upper half of your value as shown below:

function IsOdd(n) { n ^= n >> 32; n ^= n >> 16; n ^= n >> 8; n ^= n >> 4; n ^= n >> 2; n ^= n >> 1; return (n & 1) == 1; } 

This can be optimized using a pre-populated lookup table:

 function Prepopulate() { bool[] answer = new bool[256]; answer[0] = false; for (int i = 1; i < 256; i++) answer[i] = answer[i >> 1] ^ ((i & 1) == 1); } function IsOdd(n) { n ^= n >> 32; n ^= n >> 16; n ^= n >> 8; return answer[n & 255]; } 

You might want to use different sizes of the filled tables; in my example, I used an 8-bit table (256 elements).

Answer 2

XOR all the bits. To do this optimally, you can reduce the number of bits to a 32-bit number by doing xoring 32 MSB with 32 LSB. Then, reduce the 32-bit number to a 16-bit number and end the 16-bit number to 8. Once you have the byte, you can use a simple map table to determine if there is an even or odd number of bits.

Answer 3

For modern processors and a gcc compiler:

  IsOdd = __builtin_popcount(value)&1; 

Or, as Falk points out, simply:

  IsOdd = __builtin_parity(value); 

gcc inline documentation here .