通过取消最右边的位来计算奇偶校验

Question

计算奇偶校验的第一种方法是对每个位进行xor运算. - 这很容易理解.对此的增强是丢弃较低位并保持反转奇偶校验直到数字变为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

请注意,将数字转换为零所需的传递次数等于设置位数,因为每次传递都会删除一个设置位.奇偶校验是模2的设置位的数量(或和).模2加法是xor运算,因此在算法中使用xor来找到奇偶校验.