CODEWITHSUNDEEP
algorithmbinary
kavinderd
kavinderd

Reputation: 113

Understanding parity of a number

I'm going through "Elements of Programming Interviews" and the very first question is about computing the parity of a number ( whether the number of 1's in the binary representation is even or odd). The final solution provided does this:

short Parity(unsigned long x) {
  x ^= x >> 32;
  x ^= x >> 16;
  x ^= x >> 8;
  x ^= x >> 4;
  x &= 0xf;
  ...

I understand that with that final value of x you can lookup the answer in a lookup table = 0x6996. But my question is why does the above code work? I've worked a 16 bit example out by hand and it does give the correct parity, I just don't understand it conceptually.

Upvotes: 4

Views: 894

Answers (3)

NIRBHAY KUMAR PANDEY
NIRBHAY KUMAR PANDEY

Reputation: 33

For an n bit number x, the answer is always in the rightmost n/(2 to the power z) bits of x after z iterations. Let's take an example where n=8 and x=10110001 (b7, b6, b5, b4, b3, b2, b1, b0).

It's actual/correct answer is even_parity.

After 1 iteration 

                10110001

                00001011
              ___________
            x = 10111010

Rightmost 8/(2 to the power 1) = 4 digits of x = 1010(even parity)

After 2 iterations 

          10111010

          00101110
        ___________

      x = 10010100

Rightmost 8/(2 to the power 2) = 2 digits of x = 00(even parity)

After 3 iterations 

                10010100

                01001010
              ___________
            x = 11011110

Rightmost 8/(2 to the power 3) = 1 digit of x = 0(even parity)

Now we can extract any dth digit of a number b by ANDING it with a number q in which only the dth digit is 1(one) and all other digits are 0(zero).

Here we want to extract the (0th digit)/(rightmost digit) of final value of x.

So let's AND it(i.e, ( final_value_of_x

                         (i.e, 11011110)

                ) 
                                       after (

                                                2 to the power( 
                                                                log n to the base 2
                                                               )
                                             ) iterations
           )  with 00000001 to get the answer.


               11011110

               00000001
           _________________
               00000000

Upvotes: 2

zmbq
zmbq

Reputation: 39013

The lookup table is confusing. Let's drop it and keep going:

...
x ^= x >> 2;
x ^= x >> 1;
p = x&1;

To figure it out, let's start with the 1-bit case. In the 1-bit case, p=x, so if x is 1 the parity is odd, and if x is 0 the parity is even. Trivial.

Now the two bit case. You look at b0^b1 (bit 0 XOR bit 1) and that's the parity. If they're equal, the parity is even, otherwise it's odd. Simple, too.

Now let's add more bits. In the four bit example - b3 b2 b1 b0, we calculate x ^ (x>>2), which gives us a two bit number: b3^b1 b2^b0 . These are actual two parities - one for the odd bits of the original number, and one for the even bits of the original number. XOR the two parities and we get the original parity.

And now this goes on and on for us many bits as you want.

Upvotes: 5

user555045
user555045

Reputation: 64904

It works because,

  • the parity of a single bit is itself (base case)
  • the parity of the concatenation of bitstrings x and y is the xor of the parity of x and the parity of y

That gives a recursive algorithm by splitting every string down the middle until it's a base case, which you can then group by layer and flip upside down to get the code shown in the question .. sort of, because it ends early and apparently does the last step by lookup.

Upvotes: 3

Related Questions