计算奇偶校验

Question

我不完全理解这个计算奇偶校验位的算法。有没有人能详细解释一下？

以下代码摘自“黑客的快乐”一书：

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

如果x只有1位，显然((x ^ (x >> 1)) & 1会计算奇偶校验(只是将这些位彼此进行异或)。

该模式可以扩展到更多的位。

如果你有4位，你会得到(至少，这是一种方法)

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

其中位执行此操作：

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

如果将模式一直扩展到32位，就会得到问题中显示的代码。