24

バイナリ表現では、ハミング重みは 1 の数です。私はウェブに出くわし、それに対するO（1）の答えを見つけました：

v = v - ((v>>1) & 0x55555555);
v = (v & 0x33333333) + ((v>>2) & 0x33333333);
int count = ((v + (v>>4) & 0xF0F0F0F) * 0x1010101) >> 24;

しかし、私はアルゴリズムをよく理解しておらず、その説明をどこにも見つけることができません。誰か、特に最後の行について少し説明してもらえますか (*0x1010101 と >> 24 の意味)。

4

1 に答える 1

25

これは、「ポピュレーション」関数と呼ばれる、ビットをカウントするための分割統治戦略の一部です。この戦略の学術的な扱いは、1977 年の Reingold and Nievergelt に見出すことができます。

アイデアは、最初にペアごとにビットを合計し、次に 4 ごとに合計し、次に 8 ごとに合計するというものです。たとえば、ビットがある場合1011、最初のペア10は01ビットが 1 つあるため、2 番目のペアは 2 進数であり、ビットが 2 つある10ためになります。ここで重要な事実は次のとおりです。10 = 211

population(x) = x - (x/2) - (x/4) - (x/8) - (x/16) - ... etc.

あなたが持っている正確なアルゴリズムは、「HAKMEM」アルゴリズムとして知られているものの変形です (Beeler、Gosper、および Schroppel、1972 を参照)。このアルゴリズムは1を 4 ビット フィールドで並列にカウントし、次にこれらの合計を 8 ビットの合計に変換します。最後のステップは、これらの 4 バイトを で乗算して加算する操作0x01010101です。マスクは、0x0F0F0F0F合計以外の情報をマスクすることによって、4 方向のバイト合計を取得します。たとえば、8 方向フィールドが10110110であるとすると、 に等しい 5 ビットがあるため0101、 になります10110101。最後の 4 ビットのみが重要なので、最初の 4 ビットをマスクします。つまり、次のようになります。

10110101 & 0x0F = 00000101

Henry Warren 著の本 "Hacker's Delight" で、ビット数を数える際の細かい点に関する章全体を見つけることができます。

于 2013-03-05T20:34:51.447 に答える