c - How to check if value has even parity of bits or odd?

Question

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 1

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.