c - 奇数位的位奇偶校验码

Question

我在研究寻找位奇偶校验时遇到了这段代码，几乎不知道为什么会这样。有人能告诉我它的算法吗？

x ^= x >> 16
x ^= x >> 8
x ^= x >> 4
x ^= x >> 2
x ^= x >> 1

x &= 1;

Answer 1

您将 32 位折叠到 16 位，然后将 16 位折叠到 8 位，......最后是 2 到 1。那么折叠是如何工作的呢？好吧，让我们举一个简单的例子，从一个 4 位数字开始（以二进制显示）

x = 1110

x ^= x >> 2用计算折叠它是

1110      // x three bits, odd parity
0011      // x >> 2
----
xx01      // after the XOR, ignoring the upper bits

此时，我们已经将 4 位折叠为 2，我们只关心 2 个 lsb，它们是01. 请注意，奇偶校验已被保留，设置了一位，奇偶校验仍然是奇数。那是怎么发生的？如果你只检查低两位，你会看到

10       // the lower two bits from the 4-bit number
11       // the upper two bits from the 4-bit number
01       // after exclusive-OR

异或将第一列转换为0，从结果中删除两位，但保持奇偶校验相同。这就是它起作用的原因。1只要同一列中有两个 s，异或就会将总位数减少 2 。因此，如果原始位数为奇数，则最终位数将为奇数。如果原始位数是偶数，则最终位数将是偶数。

继续这个例子，再次折叠它x ^= x >> 1

01    // the lower 2 bits from the previous calculation
00    // shifted by one
--
x1    // after the XOR, ignoring the upper bits

拼图的最后一块是x &= 1结尾。这会丢弃所有高位，留下一位结果。

Answer 2

第一行将高 16 位异或到低 16 位。

第二行将低 16 位的高半部分异或到低半部分。

等等

在最后一行之前，低位包含初始 32 位的奇偶校验，但其他位包含中间结果（垃圾）。最后一行清除所有垃圾位。

每行取剩余值的一半并将其异或到另一半。总的来说，因为 XOR 操作是关联的和可交换的，所以这与单独对每个位进行 XOR 相同。