Fast way to check whether an odd number of bits is set?

Question

I need to determine whether the number of bits set in a variable of some type (it might be a 32-bit unsigned or a 64-bit unsigned) is odd, or not. I've read:

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

Which is of course quite useful, but I want to do better since I only need a binary answer, not the whole count. I suppose replacing the one-byte or two-byte LUT should be pretty fast, but maybe the non-LUT code can be improved somehow.

Did you read this? http://www-graphics.stanford.edu/~seander/bithacks.html#ParityParallel — Henrik, Aug 13 '13 at 11:18
@Henrik The link is dead. [Here it is again](https://graphics.stanford.edu/~seander/bithacks.html#ParityParallel). — Morwenn, Jun 19 '15 at 09:36

score 5 · Answer 1 · answered Aug 13 '13 at 11:58

XOR all the bits. To do it optimal you can reduce a 64 bit number to a 32 bit number by xoring the 32 MSB with the 32 LSB. Then reduce the 32 bit number to a 16 bits number and finaly the 16 bits number to 8. Once you have a byte, a simple map table can be used to determine if you have an even or odd number of bits.

score 5 · Accepted Answer · edited Aug 13 '13 at 18:02

Pure bits solution: Repeatedly XOR the lower and upper half of your value, as in the following:

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 may want to use different pre-populated table sizes; in my example I used an 8-bit table (256 items).

AShelly · Answer 3 · 2014-01-13T15:35:53.963

4

For modern processors and the gcc compiler:

 IsOdd = __builtin_popcount(value)&1;

Or, as Falk points out, simply:

 IsOdd = __builtin_parity(value);

gcc builtin documentation here.

edited Jan 13 '14 at 15:35

answered Aug 13 '13 at 15:10

AShelly

34,686
15
91
152

Fast way to check whether an odd number of bits is set?

3 Answers3