11

パリティビットを計算するこのアルゴリズムを完全には理解していません。誰か詳しく説明してくれませんか?

次のコードは、「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;
}
4

2 に答える 2

22

最初に少し理論を説明します。

  • ビットのセットのパリティは、1 ビットの数が偶数の場合は偶数であり、1 ビットの数が奇数の場合は奇数です。

  • パリティ情報を次のようにエンコードします。

    • 1 --> セットのパリティが奇数
    • 0 --> セットのパリティは偶数

  • 2 ビットのセットのパリティは、XOR を使用して簡単に計算できます。
    b0 b1 --> P1-0
--------------------------
0 ^ 0 --> 0 --> 偶数パリティ
0 ^ 1 --> 1 --> 奇数パリティ
1 ^ 0 --> 1 --> 奇数パリティ
1 ^ 1 --> 0 --> 偶数パリティ
  • ビットのセット S のパリティは、 XORを使用してS1、2 つの互いに素なサブセット のパリティから計算できます。実際には： S2S = S1 UNION S2P(S) = P(S1) ^ P(S2)
    • S1とが同じパリティを持つ場合S2、つまり両方ともビット数が偶数または奇数の場合、それらの和集合Sはビット数が偶数になります。
    • S1とのパリティが異なる場合S2、 S のビット数は奇数になります。

が 32 ビットであると仮定すると、トリックを理解できるようになりましたunsigned int。2 ビットのサブセット (隣接する 2 つのビット) でビットをグループ化することから始めて、「再帰的に」パリティを計算し、次にそれらのサブセットでパリティ チェックを実行します。次に、計算されたばかりの 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の位置を持つビット セットのパリティを示すために表記法を使用しました。互いに素なサブセットを使用してパリティを計算する必要があるため、これらのパリティ値の 2 つのうち 1 つだけを使用します。他の値には意味がないことを示すために を付けます。したがって、次のようになります。mn?

   え：？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ことがわかります。これは、私たちが望んでいたものです。

于 2013-10-16T09:35:07.890 に答える
7

1ビットしかない場合x、明らか((x ^ (x >> 1)) & 1にパリティが計算されます（ビットを互いにxorするだけです）。

このパターンは、より多くのビットに拡張できます。

4 ビットの場合は、次のようになります (少なくとも、これは 1 つの方法です)。

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 に答える