计算奇偶校验

Question

我不完全理解这种计算奇偶校验位的算法.有人可以详细解释一下吗？

以下代码取自"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;
}

Answer 1

首先是一点理论.

• 即使1比特的数量是偶数,一组比特的奇偶校验也是奇数,如果1比特的数目是奇数则是奇数.

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

  • 1 - >该组的奇偶校验是奇数
  • 0 - >设置的奇偶校验是偶数

• 可以使用XOR简单地计算一组两位的奇偶校验:

  b0 b1 --> P1-0
  –-------------------------
  0 ^ 0 --> 0 --> parity even
  0 ^ 1 --> 1 --> parity odd
  1 ^ 0 --> 1 --> parity odd
  1 ^ 1 --> 0 --> parity even
  

• 可以从两个不相交的子集的奇偶校验来计算一组比特S的奇偶校验S1,S2使得S = S1 UNION S2使用XOR : 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来表示位置为mto 的位组的奇偶校验n.由于我们必须使用不相交的子集计算奇偶校验,我们只使用其中两个奇偶校验值中的一个,我将其他的标记?为意味着它们没有意义.所以我们有:

   y:  ?  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等,由此获得:

   y:  ?? 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

同样,忽略重叠集(并?为了可读性而分组):

   y:  ???? 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

再次,忽略重叠集:

   y:  ???? ???? P31-16 ??? ???? ???? ???? P15-0

y = y ^ (y >> 16)

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

return y & 1

    y:  ???? ???? 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,这正是我们想要的.

Answer 2

如果x只有1位,显然((x ^ (x >> 1)) & 1会计算奇偶校验(只是相互之间的x或位).

此模式可以扩展到更多位.

如果你有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位,您将获得问题中显示的代码.