2

ループを含まず (ビット操作のみ)、大きな定数を使用しない、ワード内のビットをカウントするルーチンを作成する必要があります。

int x = 0xFFFFFFFF;
x += (~((x >> 1) & 0x55555555)+1);
x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
x = (((x >> 4) + x) & 0x0F0F0F0F);
x += (x >> 8);
x += (x >> 16);
return(x & 0x0000003F);

これはビットいじりハックで見つけましたが、使用できる最大の定数は 0xFF です...それ以外の方法でこれを行う方法がわかりません。

ありがとうございます。

4

3 に答える 3

4

COUNTS[16]たとえば、0 から 15 までの数値のバイナリ表現で設定されたビット数である定数配列を使用できます。次に、次のようにします。

static inline int byte_count (int x) {
  static const int COUNTS[16] = { 0, 1, 1, 2, 1, /* fill in the rest manually */ };
  return COUNTS[x & 15] + COUNTS[x >> 4];
}

int count(int x) {
  return byte_count(x >> 24) + byte_count((x >> 16) & 255) + byte_count((x >> 8) & 255) + byte_count(x & 255);
}

255 を超えるループや定数はありません。

于 2012-04-10T16:36:18.057 に答える
3

アルゴリズムの使用:

int x = 0xFF;
x |= (x << 8);  // x = 0xFFFF
x |= (x << 16); // x = 0xFFFFFFFF

そして残りのコード - 動作する場合。

再帰的な解決策:

int foo ( int x )
{
    if ( x == 0 )
        return 0;
    return (x & 1) + foo ( x/2 );
}
于 2012-04-10T16:34:12.117 に答える