Computing the Parity

Question

I don't fully understand this algorithm of calculating the parity bit. Can someone please explain in detail?

The following code is taken from the 'Hacker's Delight' book:

int parity(unsigned x) {
   unsigned y;
   y = x ^ (x >> 1);
   y = y ^ (y >> 2);
   y = y ^ (y >> 4);
   y = y ^ (y >> 8);
   y = y ^ (y >>16);
   return y & 1;
}

Answer 1

First a bit of theory.

• The parity of a set of bits is even if the number of 1-bits is even, is odd if the number of 1-bits is odd.

• We encode the parity information as:

  • 1 --> parity of the set is odd
  • 0 --> parity of the set is even

• The parity of a set of two bits can simply be computed using XOR:

  b0 b1 --> P1-0
  –-------------------------
  0 ^ 0 --> 0 --> parity even
  0 ^ 1 --> 1 --> parity odd
  1 ^ 0 --> 1 --> parity odd
  1 ^ 1 --> 0 --> parity even
  

• The parity of a set of bits S can be computed from the parities of two disjoint subsets S1, S2 such that S = S1 UNION S2 using XOR: P(S) = P(S1) ^ P(S2). In fact:
  • if S1 and S2 have the same parity, i.e. they both have an even number of bits or an odd number of bits, their union S will have an even number of bits.
  • if S1 and S2 have different parity, S will have an odd number of bits.

Now we are able to understand the trick, assuming an unsigned int has 32 bits: it computes the parity "recursively" starting by grouping the bits in subsets of two bits (two adjacent bits), then it performs the parity check on those subsets. Then it checks the parity of the next-bigger sets of 4 bits by using the parity of the 2-bits subsets just computed. Then it goes on with 8-bits and 16-bits subsets.

Let's see it graphically (on the least significative bits for clarity):

y = x ^ (x >> 1)

   x:  b7    b6    b5    b4    b3    b2    b1    b0
x>>1:  b8    b7    b6    b5    b4    b3    b2    b1
  y=:  P8-7  P7-6  P6-5  P5-4  P4-3  P3-2  P2-1  P1-0

Where I used the notation Pn-m to denote the parity of the set of bits having position from m to n. Since we must compute the parity using disjoint subsets, we use only one out of two of those parity values, I'll mark the others with ? to mean they are not meaningful. So we have:

   y:  ?  P7-6  ?  P5-4  ?  P3-2  ?  P1-0

y = y ^ (y >> 2) (taking into account more higher order bits)

   y:  P15-14 ? P13-12 ? P11-10 ? P9-8   ? P7-6 ? P5-4 ? P3-2 ? P1-0
y>>2:  P17-16 ? P15-14 ? P13-12 ? P11-10 ? P9-8 ? P7-6 ? P5-4 ? P3-2
  y=:  P17-14 ? P15-12 ? P13-10 ? P11-8  ? P9-6 ? P7-4 ? P5-2 ? P3-0

Again, since we need only the parity of disjoint subset, we neglect some bits of the result to avoid overlapping sets, i.e. P5-2, P9-6, etc., thus obtaining:

   y:  ?? P15-12 ??? P11-8  ??? P7-4 ??? P3-0

y = y ^ (y >> 4) (taking into account more higher order bits)

   y:  P23-20 ??? P19-16 ??? P15-12 ??? P11-8  ??? P7-4  ??? P3-0
y>>4:  P27-24 ??? P23-20 ??? P19-16 ??? P15-12 ??? P11-8 ??? P7-4
  y=:  P27-20 ??? P23-16 ??? P19-12 ??? P15-8  ??? P11-4 ??? P7-0

Again, neglecting overlapping sets (and grouping ?s for readability):

   y:  ???? P23-16 ??? ???? P15-8 ??? ???? P7-0

y = y ^ (y >> 8) (taking into account all 32 bits):

   y:  P31-24 ??? ???? P23-16 ??? ???? P15-8  ??? ???? P7-0
y>>8:  0      000 0000 P31-24 ??? ???? P23-16 ??? ???? P15-8
  y=:  P31-24 ??? ???? P31-16 ??? ???? P23-8  ??? ???? P15-0

Again, neglecting overlapping sets:

   y:  ???? ???? P31-16 ??? ???? ???? ???? P15-0

y = y ^ (y >> 16)

    y:  ???? ???? P31-16 ??? ???? ???? ???? P15-0
y>>16:  0000 0000 0      000 0000 ???? ???? P31-16
   y=:  ???? ???? P31-16 ??? ???? ???? ???? P31-0

return y & 1

    y:  ???? ???? P31-16 ??? ???? ???? ???? P31-0
    1:  0000 0000 0      000 0000 0000 0000 1
  y&1:  0000 0000 0      000 0000 0000 0000 P31-0

So you can see that the returned value is just the parity bit P31-0 for the bits of the argument x, which is what we wanted.

Answer 2

If x had only 1 bit, clearly ((x ^ (x >> 1)) & 1 would calculate the parity (just xor the bits with each other).

This pattern can be extended to more bits.

If you have 4 bits, you get (at least, this is one way to do it)

y = x ^ (x >> 1);
y = y ^ (y >> 2);
return y & 1;

where the bits do this:

x = a     b     c     d
y = a   a^b   b^c    c^d
y = a  a^b  a^b^c  a^b^c^d

If you extend the pattern all the way to 32 bits you get the code you showed in the question.