The basic program is

```
short Parity(unsigned long x) {
x ^= x >> 32;
x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
return x & 0x1;
```

}

There’s the same issue wrt the meaningful bits being the lower half, quarter, etc., similar to the issue with table lookup you brought up earlier, but it’s otherwise pretty clear.

We optimized this program a tiny bit, at the cost of clarity, by getting the parity when you get to 4 bits by table lookup.

You dont need an array for the table lookup, you can use a single word, as long as it fits 16 bits. The idea is that the parities of 0, 1, 2, 3, 4, … 15 are 0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0, respectively. You can pack these bits into the following word

const int kFourBitParityLookupTable = 0x6996; // = 0b0110100110010110.

Then the parity of x, assumed to be 15 or less, is (kFourBitParityLookupTable >> x) & 1. Essentially, the right shift is the array indexing.

The optimized approach does show how you can mix table lookup and bit-wise operations, which are the two hallmarks of optimized bit-fiddling, and it’s marginally faster.

In retrospect, we should have stuck to the more direct approach, since it’s much clearer.

Let me know if you have questions about this or other problems, we always enjoy hearing from readers.

Cheers,

Adnan