algorithm - 了解数字的奇偶性

我正在复习“编程元素访谈”，第一个问题是计算一个数字的奇偶性（二进制表示中的1是偶数还是奇数）。提供的最终解决方案：

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

我知道，最后的x值可以在查找表中查找答案。但我的问题是为什么上面的代码能工作？我已经手工制作了一个16位的例子，它给出了正确的奇偶校验，我只是不理解它的概念。

最佳答案

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

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

为了解决这个问题，让我们从1位的情况开始。在1位的情况下，p=x，所以如果x是1，奇偶校验是奇数，如果x是0，奇偶校验是偶数。琐碎的。
现在是两位的情况。你看b0^b1（位0或位1），这是奇偶校验。如果它们相等，则奇偶性为偶数，否则为奇数。也很简单。
现在让我们添加更多的位。在四位示例b3 b2 b1 b0中，我们计算x ^ (x>>2)，得到一个两位数字：b3^b1 b2^b0。这实际上是两个部分-一个用于原始数的奇数位，一个用于原始数的偶数位。对两个平价进行异或运算，得到原始平价。
现在这件事在我们身上不断发生，你想要多少就多少。