Question from bit twiddling site

Question

Here is the code:

unsigned int v;  // word value to compute the parity of
v ^= v >> 16;
v ^= v >> 8;
v ^= v >> 4;
v &= 0xf;
return (0x6996 >> v) & 1;

It computes the parity of given word, v. What is the meaning of 0x6996?

The number 0x6996 in binary is 110100110010110.

Answer 1

The first four lines convert v to a 4-bit number (0 to 15) that has the same parity as the original. The 16-bit number 0x6996 contains the parity of all the numbers from 0 to 15, and the right-shift is used to select the correct bit. It is similar to using a lookup table:

//This array contains the parity of the numbers 0 to 15
char parities[16] = {0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0};
return parities[v];

Note that the array entries are the same as the bits of 0x6996. Using (0x6996 >> v) & 1 gives the same result, but doesn't require the memory access.

Answer 2

Well the algorithm is compressing the 32-bit int into a 4-bit value of the same parity by successive bitwise ORs and then ANDing with 0xf so that there are only positive bits in the least-significant 4-bits. In other words after line 5, v will be an int between 0 and 15 inclusive.

It then shifts that magic number (0x6996) to the right by this 0-16 value and returns only the least significant bit (& 1).

That means that if there is a 1 in the v bit position of 0x6996 then the computed parity bit is 1, otherwise it's 0 - for example if in line 5 v is calculated as 2 then ` is returned, if it was 3 then 0 would be returned.