How to check if value has even parity of bits or odd?
x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
return (~x) & 1;
Assuming you know ints are 32 bits.
Let's see how this works. To keep it simple, let's use an 8 bit integer, for which we can skip the first two shift/XORs. Let's label the bits a through h. If we look at our number we see:
( a b c d e f g h )
The first operation is x ^= x >> 4 (remember we're skipping the first two operations since we're only dealing with an 8-bit integer in this example). Let's write the new values of each bit by combining the letters that are XOR'd together (for example, ab means the bit has the value a xor b).
( a b c d e f g h ) xor ( 0 0 0 0 a b c d )
The result is the following bits:
( a b c d ae bf cg dh )
The next operation is x ^= x >> 2:
( a b c d ae bf cg dh ) xor ( 0 0 a b c d ae bf )
The result is the following bits:
( a b ac bd ace bdf aceg bdfh )
Notice how we are beginning to accumulate all the bits on the right-hand side.
The next operation is x ^= x >> 1:
( a b ac bd ace bdf aceg bdfh ) xor ( 0 a b ac bd ace bdf aceg )
The result is the following bits:
( a ab abc abcd abcde abcdef abcdefg abcdefgh )
We have accumulated all the bits in the original word, XOR'd together, in the least-significant bit. So this bit is now zero if and only if there were an even number of 1 bits in the input word (even parity). The same process works on 32-bit integers (but requires those two additional shifts that we skipped in this demonstration).
The final line of code simply strips off all but the least-significant bit (& 1) and then flips it (~x). The result, then, is 1 if the parity of the input word was even, or zero otherwise.
GCC has built-in functions for this:
Built-in Function:
int __builtin_parity (unsigned int x)Returns the parity of
x, i.e. the number of 1-bits in x modulo 2.
and similar functions for unsigned long and unsigned long long.
I.e. this function behaves like has_odd_parity. Invert the value for has_even_parity.
These should be the fastest alternative on GCC. Of course its use is not portable as such, but you can use it in your implementation, guarded by a macro for example.
The following answer was unashamedly lifted directly from Bit Twiddling Hacks By Sean Eron Anderson, [email protected]
Compute parity of word with a multiply
The following method computes the parity of the 32-bit value in only 8 operations >using a multiply.
unsigned int v; // 32-bit word
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x11111111U) * 0x11111111U;
return (v >> 28) & 1;
Also for 64-bits, 8 operations are still enough.
unsigned long long v; // 64-bit word
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x1111111111111111UL) * 0x1111111111111111UL;
return (v >> 60) & 1;
Andrew Shapira came up with this and sent it to me on Sept. 2, 2007.