How to check if value has even parity of bits or odd?
A value has even parity if it has an even number of 1 bits. A value has an odd parity if it has an odd number of 1 bits. For example, 0110 has even parity, and 1110 has odd parity.
I have to return 1 if x has even parity.
int has_even_parity(unsigned int x) {
return
}
Answer
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.