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.

Answer 1

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).

Answer 2

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.