了解数字的奇偶性

Question

我正在经历“编程面试的要素”，第一个问题是关于计算数字的奇偶性（二进制表示形式中的1的个数是偶数还是奇数）。提供的最终解决方案是：

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

我了解使用x的最终值可以在查找表=中查找答案0x6996。但是我的问题是上面的代码为什么起作用？我手工制作了一个16位示例，它确实提供了正确的奇偶校验，但我只是从概念上不了解。

Answer 1

查找表令人困惑。让我们放下并继续：

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

为了弄清楚，让我们从1位的情况开始。在1位情况下，p = x，因此如果x为1，则奇偶校验为奇数；如果x为0，则奇偶校验为偶数。不重要的。

现在是两位的情况。您看b0 ^ b1（位0 XOR位1），这就是奇偶校验。如果它们相等，则奇偶校验为偶数，否则为奇数。也很简单。

现在让我们添加更多位。在四位示例-b3 b2 b1 b0中，我们计算x ^ (x>>2)得出了两位数：b3 ^ b1 b2 ^ b0。这是实际的两个奇偶校验-一个用于原始数字的奇数位，另一个用于原始数字的偶数位。对两个奇偶校验位进行XOR，我们得到原始奇偶校验。

现在，这对我们来说是不停的，只要您想要。