Question from bit twiddling site
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
.
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.
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.
精彩评论