bit-manipulation - 计算奇偶校验

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

先说点理论。

一组位的奇偶校验是
即使 1 位的数量是偶数，如果
1 位的数量是奇数。

我们将奇偶校验信息编码为:

1 --> 集合的奇偶校验

0 --> 集合的奇偶性是偶数

一组两位的奇偶校验可以简单地计算
使用异或:b0 b1 --> P1-0
--------------------------
0 ^ 0 --> 0 --> 奇偶校验
0 ^ 1 --> 1 --> 奇偶校验
1 ^ 0 --> 1 --> 奇偶校验
1 ^ 1 --> 0 --> 奇偶校验

一组比特 S 的奇偶校验可以从两个不相交的子集的奇偶校验S1 中计算出来。 , S2使得 S = S1 UNION S2使用异或:P(S) = P(S1) ^ P(S2) .实际上:

如果 S1和 S2具有相同的奇偶性，即它们都有偶数位或奇数位，它们的并集 S将有偶数位。

如果 S1和 S2有不同的奇偶校验，S 将有奇数位。

现在我们能够理解这个技巧，假设 unsigned int有 32 位:它通过将位分组为两位(两个相邻位)的子集中的位开始“递归地”计算奇偶校验，然后对这些子集执行奇偶校验。然后它通过使用刚刚计算的 2 位子集的奇偶校验来检查下一个更大的 4 位组的奇偶校验。然后继续处理 8 位和 16 位子集。

让我们以图形方式查看它(为清楚起见，在最不重要的位上):

y = x ^ (x >> 1)

x: b7 b6 b5 b4 b3 b2 b1 b0
x>>1: b8 b7 b6 b5 b4 b3 b2 b1
y=: P8-7 P7-6 P6-5 P5-4 P4-3 P3-2 P2-1 P1-0

我使用符号的地方 Pn-m表示位置来自 m 的一组位的奇偶校验至 n .由于我们必须使用不相交的子集计算奇偶校验，因此我们只使用其中两个奇偶校验值中的一个，我将用 ? 标记其他奇偶校验值。意味着它们没有意义。所以我们有:

你:？ P7-6 ? P5-4 ? P3-2 ? P1-0

y = y ^ (y >> 2) (考虑到更多的高阶位)

y: P15-14 ? P13-12 ? P11-10 ? P9-8 ? P7-6 ? P5-4 ? P3-2 ? P1-0
y>>2: P17-16 ? P15-14 ? P13-12 ? P11-10 ? P9-8 ? P7-6 ? P5-4 ? P3-2
y=: P17-14 ? P15-12 ? P13-10 ? P11-8 ? P9-6 ? P7-4 ? P5-2 ? P3-0

同样，由于我们只需要不相交子集的奇偶性，我们忽略结果的某些位以避免重叠集合，即 P5-2 , P9-6等，从而得到:

你:？？ P15-12 ？？？ P11-8 ？？？ P7-4 ？？？ P3-0

y = y ^ (y >> 4) (考虑到更多的高阶位)

y:P23-20 ？？？ P19-16 ？？？ P15-12 ？？？ P11-8 ？？？ P7-4 ？？？ P3-0
y>>4:P27-24 ？？？ P23-20 ？？？ P19-16 ？？？ P15-12 ？？？ P11-8 ？？？ P7-4
y=: P27-20 ??? P23-16 ？？？ P19-12 ？？？ P15-8 ？？？ P11-4 ？？？ P7-0

同样，忽略重叠集(并将 ? 分组以提高可读性):

你:？？？ P23-16 ？？？ ？？？ P15-8 ？？？ ？？？ P7-0

y = y ^ (y >> 8) (考虑到所有 32 位):

y:P31-24 ？？？ ？？？ P23-16 ？？？ ？？？ P15-8 ？？？ ？？？ P7-0
y>>8: 0 000 0000 P31-24 ??? ？？？ P23-16 ？？？ ？？？ P15-8
y=: P31-24 ??? ？？？ P31-16 ？？？ ？？？ P23-8 ？？？ ？？？ P15-0

再次，忽略重叠集:

你:？？？ ？？？ P31-16 ？？？ ？？？ ？？？ ？？？ P15-0

y = y ^ (y >> 16)

你:？？？ ？？？ P31-16 ？？？ ？？？ ？？？ ？？？ P15-0
y>>16: 0000 0000 0 000 0000 ???? ？？？ P31-16
y=: ???? ？？？ P31-16 ？？？ ？？？ ？？？ ？？？ P31-0

return y & 1

你:？？？ ？？？ P31-16 ？？？ ？？？ ？？？ ？？？ P31-0
1:0000 0000 0 000 0000 0000 0000 1
y&1: 0000 0000 0 000 0000 0000 0000 P31-0

所以你可以看到返回的值只是奇偶校验位 P31-0对于参数的位 x ，这就是我们想要的。