了解数字的奇偶性

Question

我正在学习 "Elements of Programming Interviews"，第一个问题是关于计算数字的奇偶校验（二进制表示中 1 的个数是偶数还是奇数）。提供的最终解决方案是这样做的：

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

我知道使用 x 的最终值，您可以在查找 table = 0x6996 中查找答案。但我的问题是为什么上面的代码有效？我已经手工制作了一个 16 位示例，它确实给出了正确的奇偶校验，我只是在概念上不理解它。

Answer 1

之所以有效，是因为

单个位的奇偶校验本身（基本情况）
位串 x 和 y 的奇偶校验是 x 的奇偶校验和 y 的奇偶校验的异或

这给出了一个递归算法，通过将每个字符串从中间拆分直到它是一个基本情况，然后你可以按层分组并颠倒翻转以获得问题中显示的代码..有点，因为它结束了很早就通过查找完成了最后一步。

Answer 2

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

...
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 。这些是实际的两个奇偶校验 - 一个用于原始数的奇数位，一个用于原始数的偶数位。将两个奇偶异或，我们得到原始奇偶。

现在这对我们来说继续下去，你想要的很多位。

Answer 3

对于n位数x，在z次迭代后，答案总是在x的最右边n/(2的z次方)位。让我们举一个例子，其中 n=8 和 x=10110001 (b7, b6, b5, b4, b3, b2, b1, b0).

actual/correct答案是even_parity.

1 次迭代后

                10110001

                00001011
              ___________
            x = 10111010

最右8/(2的1次方)=x的4位=1010(偶校验)

2次迭代后

          10111010

          00101110
        ___________

      x = 10010100

最右边的8/(2的2次方)=x的2位=00(偶校验)

3次迭代后

                10010100

                01001010
              ___________
            x = 11011110

最右8/(2的3次方)=x的第1位=0(偶校验)

现在我们可以通过 ANDING 与 a 提取数字 b 的第 d 位数字 q 其中只有第 d 个数字是 1（一），所有其他数字都是 0（零）。

这里我们要提取x的最终值的(第0位)/(最右位)

所以让我们 AND 它（即，（ final_value_of_x

                         (i.e, 11011110)

                ) 
                                       after (

                                                2 to the power( 
                                                                log n to the base 2
                                                               )
                                             ) iterations
           )  with 00000001 to get the answer.


               11011110

               00000001
           _________________
               00000000

了解数字的奇偶性

Understanding parity of a number

algorithm

binary