これは、「ポピュレーション」関数と呼ばれる、ビットをカウントするための分割統治戦略の一部です。この戦略の学術的な扱いは、1977 年の Reingold and Nievergelt に見出すことができます。
アイデアは、最初にペアごとにビットを合計し、次に 4 ごとに合計し、次に 8 ごとに合計するというものです。たとえば、ビットがある場合1011
、最初のペア10
は01
ビットが 1 つあるため、2 番目のペアは 2 進数であり、ビットが 2 つある10
ためになります。ここで重要な事実は次のとおりです。10 = 2
11
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" で、ビット数を数える際の細かい点に関する章全体を見つけることができます。