我不完全理解这种计算奇偶校验位的算法。有人可以详细解释一下吗？
以下代码摘自《Hacker's Delight》一书：
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;
}
问问题
12826 次
2 回答
22
先说一点理论。
一组位的奇偶性在 1 位数为偶数时为偶数，如果 1 位数为奇数则为奇数。
我们将奇偶校验信息编码为：
- 1 --> 集合的奇偶性是奇数
- 0 --> 集合的奇偶性是偶数
- 一组两位的奇偶校验可以简单地使用 XOR 计算：
b0 b1 --> P1-0 -------------- 0 ^ 0 --> 0 --> 奇偶校验 0 ^ 1 --> 1 --> 奇偶校验 1 ^ 0 --> 1 --> 奇偶校验 1 ^ 1 --> 0 --> 奇偶校验
- 一组比特 S 的奇偶校验可以从两个不相交的子集 的奇偶校验中计算出来
S1，S2这样S=S1 UNION S2使用 XOR：P(S) = P(S1) ^ P(S2)。实际上：- 如果
S1和S2具有相同的奇偶性，即它们都具有偶数位或奇数位，则它们的并集S将具有偶数位。 - 如果
S1和S2具有不同的奇偶性，则 S 将具有奇数位。
- 如果
现在我们能够理解这个技巧了，假设 anunsigned 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
我使用符号来表示位置为 from的Pn-m位集的奇偶性。由于我们必须使用不相交的子集来计算奇偶校验，因此我们只使用其中两个奇偶校验值中的一个，我将用其他值标记以表示它们没有意义。所以我们有：mn?
是：？P7-6？P5-4 ? P3-2 ? P1-0
y = y ^ (y >> 2)（考虑到更多的高阶位）
是：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
同样，忽略重叠集（?为了可读性而对 s 进行分组）：
你：？？？P23-16 ？？？？？？P15-8 ？？？？？？P7-0
y = y ^ (y >> 8)（考虑到所有 32 位）：
是：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，这就是我们想要的。
于 2013-10-16T09:35:07.890 回答
7
如果x只有 1 位，显然((x ^ (x >> 1)) & 1会计算奇偶校验（只需将这些位相互异或）。
这种模式可以扩展到更多位。
如果你有 4 位，你会得到（至少，这是一种方法）
y = x ^ (x >> 1);
y = y ^ (y >> 2);
return y & 1;
这些位在哪里执行此操作：
x = a b c d
y = a a^b b^c c^d
y = a a^b a^b^c a^b^c^d
如果将模式一直扩展到 32 位，则会得到问题中显示的代码。
于 2013-06-27T18:59:24.453 回答