Understanding parity of a number

Question

I'm going through "Elements of Programming Interviews" and the very first question is about computing the parity of a number ( whether the number of 1's in the binary representation is even or odd). The final solution provided does this:

short Parity(unsigned long x) {
  x ^= x >> 32;
  x ^= x >> 16;
  x ^= x >> 8;
  x ^= x >> 4;
  x &= 0xf;
  ...

I understand that with that final value of x you can lookup the answer in a lookup table = 0x6996. But my question is why does the above code work? I've worked a 16 bit example out by hand and it does give the correct parity, I just don't understand it conceptually.

Answer 1

The lookup table is confusing. Let's drop it and keep going:

...
x ^= x >> 2;
x ^= x >> 1;
p = x&1;

To figure it out, let's start with the 1-bit case. In the 1-bit case, p=x, so if x is 1 the parity is odd, and if x is 0 the parity is even. Trivial.

Now the two bit case. You look at b0^b1 (bit 0 XOR bit 1) and that's the parity. If they're equal, the parity is even, otherwise it's odd. Simple, too.

Now let's add more bits. In the four bit example - b3 b2 b1 b0, we calculate x ^ (x>>2), which gives us a two bit number: b3^b1 b2^b0 . These are actual two parities - one for the odd bits of the original number, and one for the even bits of the original number. XOR the two parities and we get the original parity.

And now this goes on and on for us many bits as you want.

Answer 2

It works because,

• the parity of a single bit is itself (base case)
• the parity of the concatenation of bitstrings x and y is the xor of the parity of x and the parity of y

That gives a recursive algorithm by splitting every string down the middle until it's a base case, which you can then group by layer and flip upside down to get the code shown in the question .. sort of, because it ends early and apparently does the last step by lookup.