1の数を整数で数える最も効率的な方法は何ですか？

Question

可能性の重複：32ビット符号なし整数を考えると
Best algorithm to count the number of set bits in a 32-bit integer?

、我々はそのバイナリ表現における非ゼロのビットの数をカウントします。それを行う最速の方法は何ですか？

私はこれをN〜10^10回したいと思っています。

注：現在のCPUのアーキテクチャのため、大きなルックアップテーブルを使用することは通常はお勧めできません。外部メモリを見なければならない巨大な配列を使うよりもローカルで計算する方がはるかに高速です

Answer 1

実際にはいくつかのオプションがあります。

8ビット値のルックアップテーブルを使用して、符号なし整数値から4バイトすべてを並列に実行し、その結果を合計することができます。これもかなりパラレル化が可能です（マルチコアでもSSE3/4でも役立つかもしれません）。

また、ブライアン・カーニハンのソリューションで行くことができます。

unsigned int v;    // count the number of bits set in v 
unsigned int c;    // c accumulates the total bits set in v 
for (c = 0; v; c++) 
{ 
    v &= v - 1;    // clear the least significant bit set 
} 

そして（モジュロ演算は本当に速いがあるだろうとして、64ビットマシン上で）私はいくつかの時間前にどこかで見つかった最後の可能な方法は次のとおりです。

unsigned int v;  // count the number of bits set in v 
unsigned int c;  // c accumulates the total bits set in v 

c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f; 
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f; 
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;