5

私はセットビットカウント問題の解決策を探しています（2進数が与えられた場合、セットされたビット数を効率的にカウントする方法）。

ここで、 http: //graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive、いくつかのメソッドを見つけました。

ルックアップテーブルメソッドはどうですか？バイナリ表現/数値のどのプロパティがそれを機能させるのか理解していません。

static const unsigned char BitsSetTable256[256] = 
{
#   define B2(n) n,     n+1,     n+1,     n+2
#   define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
#   define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
   B6(0), B6(1), B6(1), B6(2)
};

unsigned int v; // count the number of bits set in 32-bit value v
unsigned int c; // c is the total bits set in v

// Option 1:
c = BitsSetTable256[v & 0xff] + 
   BitsSetTable256[(v >> 8) & 0xff] + 
   BitsSetTable256[(v >> 16) & 0xff] + 
   BitsSetTable256[v >> 24]; 

// Option 2:
unsigned char * p = (unsigned char *) &v;
c = 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];
}

BitsSetTable256特に、最初はその定義がわかりません。なぜこれらの量B2、B4、...を定義するのですか？後で使われないようです。

バイナリ表現に関する詳細なドキュメントを教えていただけますか？

ありがとう！

4

1 に答える 1

7

定義は、パターンごとにテーブルを形成することです。それらは再帰マクロであり、B6はB4を使用し、B4はB2を使用します。B6（0）は次のように分類されます。

B4(0), B4(1), B4(1), B4(2)

B4（0）は次のように分割されます。

0, 1, 1, 2

シーケンスの最初の数個は次のようになります。

// 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11
   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3

ご覧のとおり、これらはテーブル内の各インデックスに設定されているビット数です。

アルゴリズムの残りの部分では、数値を8ビットのチャンクに分割し、各チャンクに設定されているビット数を合計します。これが、これらの行の内容です（オプション1またはオプション2のいずれかを使用しますが、両方は使用しません）。 ：

// Option 1:
c = BitsSetTable256[v & 0xff] + 
    BitsSetTable256[(v >> 8) & 0xff] + 
    BitsSetTable256[(v >> 16) & 0xff] + 
    BitsSetTable256[v >> 24]; 

// Option 2:
unsigned char * p = (unsigned char *) &v;
c = 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];
}

BitsSetTable256を生成する別の方法です。コンパイル時ではなく実行時にテーブルを生成します（これはマクロ定義が行うことです）。

PS十分に最近の（SSE4）x86をターゲットにしている場合は、POPCNT命令を使用できます。

于 2012-10-02T05:06:55.110 に答える