通过取消右最位来计算奇偶性

Question

计算奇偶校验的第一种方法是对每一个比特位进行异或运算。这种方法很简单，容易理解。

一种改进的方法是去掉最低位，然后不断反转奇偶校验，直到数字变成0。

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

这到底是怎么回事呢？我想理解这个方法的思路会稍微有点难。

Answer 1

一旦你明白了 number &= number - 1 是什么意思，解决这个问题就简单了。这里有个二进制的例子：

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

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

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

注意，把这个数字变成零需要的步骤次数，实际上就是这个数字里“1”的数量，因为每一步你都会去掉一个“1”。而奇偶性就是“1”的数量对2取余的结果。对2取余的加法就是异或运算，所以在这个算法中用到了异或来找出奇偶性。