O（1）でのハミング重みの計算

Question

バイナリ表現では、ハミング重みは1の数です。私は、ウェブ上に来て、そこにO（1）の答えを見つけました：

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

は、しかし、私はかなりのアルゴリズムを理解していないとどこにもそれについての説明を見つけることができません。誰かがそれをちょっと説明してください。特に最後の行（0x1010101、次に>> 24の意味）？

Answer 1

これは、「集団」機能と呼ばれるビットを数えるための分裂征服戦略の一部です。この戦略の学術的な扱いは、Reingold and Nievergelt、1977に見いだすことができます。

最初にビットをペアごとに合計し、次に4通り、次に8通りなどを合計します。たとえば、ビットが1011の場合、最初のペア10は1ビットあり、2番目のビットは10になるため01になります。10 = 2はバイナリで2ビットあり、11には2ビットあります。 （Beeler氏、GosperとSchroppel、1972を参照）

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

あなたが持っている正確なアルゴリズムは「HAKMEM」アルゴリズムとして知られているものの変形である：ここでの基本的な事実があることです。このアルゴリズムは、並列に4ビットフィールドの1をカウントし、これらの合計は8ビットの合計に変換されます。最後のステップは、0x01010101を乗算することによって、これらの4バイトを加算する操作です。 0x0F0F0F0Fマスクは、合計でない情報をマスクすることによって、4バイトの合計を取得します。たとえば、8桁のフィールドが10110110であるとすると、0101に等しい5ビットがあり、したがって10110101があります。唯一の最後の4ビットは重要であるので、我々はすなわち、最初の4つをマスク：

10110101 & 0x0F = 00000101 

あなたはヘンリー・ウォーレンの著書「ハッカーのディライト」のビットを数えるの特徴点の章全体を見つけることができます。