compute parity by unsetting right most bit

Question

The first approach to computing parity is doing xor operation on every bit. - This was simple to understand. An enhancement to that is to drop the lower bit and keep inverting parity till the number becomes 0 ie

While loop till number is greater than 0
1) parity = parity^1
2) number = number & (number-1)

How does this work? It is a little more difficult to grasp the idea of this method I guess.

Answer 1

So once you see what number &= number - 1 is, doing the problem is trivial. Here's a binary example:

first pass
1001001 - 1 = 1001000
1001001 & 1001000 = 1001000 

second pass
1001000 - 1 = 1000111
1001000 & 1000111 = 1000000

third pass
1000000 - 1 = 111111
1000000 & 111111 = 0

Note that the number of passes it takes to turn the number into zero, is equivalent to the number of set bits, because you remove one set bit each pass. Parity is the number (or sum) of set bits modulo 2. Modulo 2 addition is the xor operation, hence the use of xor in the algorithm to find the parity.