1

これは、 number に設定されたビット数をカウントする小さなプログラム (14 行のプログラム)です。

入出力 --> 0-->0(0000000)、5-->2(0000101)、7-->3(0000111)

int CountBits (unsigned int x)
{
  static unsigned int mask[] = { 0x55555555,
      0x33333333,
      0x0F0F0F0F,
      0x00FF00FF,
      0x0000FFFF
      } ;

      int i ;
      int shift ; /* Number of positions to shift to right*/
      for (i =0, shift =1; i < 5; i ++, shift *= 2)
              x = (x & mask[i ])+ ( ( x >> shift) & mask[i]);
      return x;
}

誰かがここで使用されているアルゴリズムを説明できますか/なぜこれが機能するのですか?

4

1 に答える 1

12

Ian Ashdown によるこの投稿では、より詳細に説明しています。

フリード数は数列のメンバーであり、数列の N 番目の数自体は、右から左へ 2* N 1 の後に 2 *N 0 が続き、2**N 1 が続くという無限のシーケンスです。最初の数値は次のとおりです。

...0101010101010101
...0011001100110011
...0000111100001111
...0000000011111111
...

16 ビットのワード サイズの場合、4 つの「B 定数」があります。

B[1] = 0101010101010101
B[2] = 0011001100110011
B[3] = 0000111100001111
B[4] = 0000000011111111

それが、これらの数字mask[]です。ビット パターン0x55555555の16 進数1010101010101010101010101010101表現です。

アルゴリズム自体はこれを行います：

  1. 隣接するビットを数値 (0 または 1) として解釈し、それらを加算します。結果は、2 ビット (つまり 0 から 3) で表現できる数値です。
  2. 隣接するビットのペアを数値 (0 から 3) として解釈し、それらを加算します。結果は 4 ビット (つまり 0 ～ 15) で表すことができます。
  3. 隣接する4 ビットのグループを数値 (0 から 15) として解釈し、それらを加算します。結果は 8 ビット (つまり 0 ～ 255) で表すことができます。

...など、必要なビット数と同じ幅の結果が得られるまで。

上記のバイナリ マスクを使用して、いくつかの数字を紙の上で手で試してみることをお勧めします。そうすると、そのコードで表現されているアルゴリズムの感触がつかめるかもしれません。

于 2013-11-06T06:04:29.667 に答える