6

少し前の就職の面接中に、ビットベクトル構造 (符号なし整数や long など) の正の (つまり、「1」に設定された) ビットの数を計算するように求められました。私のソリューションは、C# ではかなり単純でした。

int CountBits(uint input)
{
   int reply = 0;
   uint dirac = 1; 
   while(input != 0)
   {
      if ((input & dirac) > 0) reply++;
      input &= ~dirac;
      dirac<<=1;
   }
   return reply;
}

次に、シフトを使用せずにタスクを解決するように求められました。明示的なもの (「<<」や ">>" など) も暗黙的なもの (2 を掛けるなど) もありません。2 の潜在的な行 (0、1、2、4、8、16 など) を使用した「ブルート フォース」ソリューションも機能しません。

誰かがそのようなアルゴリズムを知っていますか?

私が理解している限り、それは入力ビットベクトルのサイズに依存しない多かれ少なかれ一般的なアルゴリズムの一種であるべきです。他のすべてのビット演算と数学関数が許可されます。

4

3 に答える 3

13

x & (x-1)しばらく考えてみると、最後1に整数でクリアされるというハックがあります。残りは些細なことです。

于 2011-11-20T10:48:13.770 に答える
1

アンソニーブレイクが説明したのと同じように、しかしもう少し読みやすいと思います。

uint32_t bitsum(uint32_t x)
{
    // leafs (0101 vs 1010)
    x = (x & 0x55555555) + ((x >> 1) & 0x55555555);

    // 2nd level (0011 vs 1100)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);

    // 3rd level (nybbles)
    //x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
    x = (x & 0x07070707) + ((x >> 4) & 0x07070707);

    /*
    // 4th level (bytes)
    //x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
    x = (x & 0x000f000f) + ((x >> 8) & 0x000f000f);

    // 5th level (16bit words)
    //return (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
    return (x & 0x0000001f) + ((x >> 16) & 0x0000001f);
    */
    // since current mask of bits 0x0f0f0f0f
    // result of summing 0f + 0f = 1f
    // x * 0x01010101 will produce
    // sum of all current and lower octets in
    // each octet
    return (x * 0x01010101) >> 24;
}
于 2011-11-20T15:25:05.883 に答える
1

一部のプロセッサには、人口カウント命令があります。そうでない場合、これが最速の方法だと思います（32ビットの場合）：

int NumberOfSetBits(int i) {
  i = i - ((i >> 1) & 0x55555555);
  i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
  return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

完全な説明については、このリンクを参照してください: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

シフトなしでそれを行うことに関しては、ルックアップ テーブルを使用することが最良の答えになると思います。

int NumberOfSetBits(int i) {
  unsigned char * p = (unsigned char *) &i;
  return BitsSetTable256[p[0]] + BitsSetTable256[p[1]] + 
     BitsSetTable256[p[2]] + BitsSetTable256[p[3]];
}

// To initially generate the table algorithmically:
BitsSetTable256[0] = 0;
for (int i = 0; i < 256; i++) {
  BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
}
于 2011-11-20T10:51:18.667 に答える