[解決済み] 32ビット整数のセットビットの数を数えるには？

質問内容

数字の7を表す8ビットは次のようになります。

00000111

3つのビットが設定されています。

32ビット整数のセットビットの数を決定するアルゴリズムは何ですか？

どのように解決するのですか？

これは「'」と呼ばれるものです。 ハミングウェイト '、'popcount' または 'sideways addition' と呼ばれる。

CPUの中には、それを行う命令を1つだけ内蔵しているものと、ビットベクタに作用する並列命令を持っているものがあります。 x86のような命令 popcnt (それがサポートされているCPUでは)単一の整数ではほぼ間違いなく最速でしょう。 他のアーキテクチャでは、1サイクルあたり1ビットのテストを行うマイクロコード化されたループで低速命令を実装している場合もあります ( 要引用 - ハードウェアのpopcountは、存在すれば通常高速です)。

最適な」アルゴリズムは、どのCPUを使用し、どのような使用パターンであるかによります。

コンパイラは、あなたがコンパイルしている特定のCPUに適した方法を知っているかもしれません、例えば。 C++20 std::popcount() または C++ std::bitset<32>::count() は、組み込み関数や組込み関数にアクセスするためのポータブルな方法として ( 別解 この質問について)。 しかし、ハードウェア popcnt を持たない CPU をターゲットとするコンパイラのフォールバックの選択は、あなたのユースケースにとって最適ではないかもしれません。 あるいは、あなたの言語(例えばC)は、CPU固有のpopcountがある場合、それを使用できるポータブルな関数を公開しないかもしれません。

HWサポートを必要としない（あるいは恩恵を受けない）ポータブルなアルゴリズム

CPUに大きなキャッシュがあり、タイトなループでこれらの操作を多数行っている場合、事前入力されたテーブル・ルックアップ方式は非常に高速になります。しかし、「キャッシュミス」によって、CPU がメインメモリからテーブルの一部をフェッチする必要があるため、この方法では問題が発生する可能性があります。 (テーブルを小さく保つために各バイトを別々に調べます) 連続した数値の範囲に対して popcount が必要な場合、256 の数値のグループに対して下位バイトだけが変更されます。 これはとても良いことです .

もし、バイトがほとんど0か、ほとんど1であることが分かっているなら、これらのシナリオに対して効率的なアルゴリズムがあります。例えば、バイサックで最低セットを0になるまでループでクリアします。

非常に優れた汎用アルゴリズムは、「並列」または「可変精度SWARアルゴリズム」と呼ばれる以下のものだと思います。私はこれをC言語風の疑似言語で表現しました。特定の言語で動作するように調整する必要があるかもしれません（例えば、C++ではuint32_tを、Javaでは>>>を使用します）。

GCC10とclang10.0はこのパターン/イディオムを認識し、利用可能な場合はハードウェアpopcntまたは同等の命令にコンパイルすることができ、両方の世界のベストを与えることができます。( https://godbolt.org/z/qGdh1dvKK )

int numberOfSetBits(uint32_t i)
{
     // Java: use int, and use >>> instead of >>. Or use Integer.bitCount()
     // C or C++: use uint32_t
     i = i - ((i >> 1) & 0x55555555);        // add pairs of bits
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);  // quads
     i = (i + (i >> 4)) & 0x0F0F0F0F;        // groups of 8
     return (i * 0x01010101) >> 24;          // horizontal sum of bytes
}

JavaScriptの場合。 整数に変換する と |0 パフォーマンス向上のため、最初の行を i = (i|0) - ((i >> 1) & 0x55555555);

このアルゴリズムは最悪ケースでの挙動が最も優れており、どのような使用パターンや値を投げても効率的に処理することができます。 (乗算を含むすべての整数演算が一定時間である通常のCPUでは、その性能はデータに依存しない。 単純な入力ではこれ以上速くならないが、それでもかなりまともだ)。

参考文献

• https://graphics.stanford.edu/~seander/bithacks.html
• https://en.wikipedia.org/wiki/Hamming_weight
• http://gurmeet.net/puzzles/fast-bit-counting-routines/
• http://aggregate.ee.engr.uky.edu/MAGIC/#Population%20Count%20(Ones%20Count)です。

このSWARバイサックの仕組み

i = i - ((i >> 1) & 0x55555555);

最初のステップは、奇数/偶数ビットを分離するためのマスキング、それらを並べるためのシフト、そして加算の最適化バージョンです。 これは、2ビットアキュムレータで16回の加算を効率的に行うものです ( SWAR = レジスタ内SIMD ). 例えば (i & 0x55555555) + ((i>>1) & 0x55555555) .

次のステップでは、16×2ビットのアキュムレータの奇数/偶数8を取り、再び加算して8×4ビットの合計を生成します。 このとき i - ... 今回は最適化ができないので、シフト前/シフト後のマスクだけを行っています。 同じ 0x33... の代わりに、2回とも定数 0xccc... 32ビット定数をレジスタで別々に構築する必要があるISA向けにコンパイルする場合、シフト前に定数を作成することは良いことです。

最後のシフトと加算のステップである (i + (i >> 4)) & 0x0F0F0F0F は4倍の8ビットアキュムレータに拡張されます。 これは 後 というのは、4ビットアキュムレータの最大値は 4 対応する入力ビットの4ビットがすべてセットされていた場合、です。 4+4=8 でも4ビットに収まるので、ニブル要素間のキャリーが不可能なのは i + (i >> 4) .

ここまでは、SWARの技術を使ったごく普通のSIMDに、少し賢い最適化を施しただけです。 同じパターンをもう2ステップ続けると、2x 16-bit カウント、1x 32-bit カウントとなります。 しかし、高速なハードウェア乗算を行うマシンでは、より効率的な方法があります。

十分な数の"elements"が揃ったら。 魔法の定数を使った乗算で、すべての要素を合計して一番上の要素にすることができます。 . この場合、バイト要素です。 乗算は左シフトと加算で行われるため の掛け算です。 x * 0x01010101 の結果は x + (x<<8) + (x<<16) + (x<<24) . 8ビットの要素は十分広いので（そして十分小さいカウントを保持しているので）、これによってcarryが発生することはありません。 への その上位8ビットの

64ビット版 は、64ビット整数の8×8ビット要素を0x0101010101倍して、その上位バイトを >>56 . つまり、余計な手間がかからず、定数が広くなるだけなのです。 これは、GCCが __builtin_popcountll x86システムにおいて、ハードウェアの popcnt 命令は有効ではありません。 もし、ビルトインやイントリンシックスを使用できるのであれば、そうしてコンパイラにターゲットに特化した最適化を行う機会を与えてください。

より広いベクトル（例：配列全体を数える）のためのフルSIMDで

このbitwise-SWARアルゴリズムは、1つの整数レジスタではなく、一度に複数のベクトル要素で行われるように並列化でき、SIMDを持つが使えるpopcount命令がないCPUでスピードアップすることができます。 (例えば、Nehalem以降だけでなく、あらゆるCPUで実行しなければならないx86-64のコードなど)。

しかし、ポップカウントにベクター命令を使用する最良の方法は、通常、可変シャッフルを使用して、各バイトの一度に4ビットのテーブルルックアップを並列に行うことです。 (4ビットはベクターレジスタに保持された16エントリーのテーブルをインデックスします)。

IntelのCPUでは、ハードウェアの64bit popcnt命令は、POPCENT命令よりも優れた性能を発揮します。 SSSE3 PSHUFB ビット並列実装 は約2倍の差がありますが、唯一 コンパイラが適切に動作する場合 . そうでない場合は、SSEが大きくリードすることになります。 新しいバージョンのコンパイラは popcnt false 依存性 インテルの問題 .

• https://github.com/WojciechMula/sse-popcount SSSE3、AVX2、AVX512BW、AVX512VBMI、または AVX512 VPOPCNT 用の最先端の x86 SIMD popcount です。 要素内のポップカウントを延期するために、ベクトル間でハーレーシールを使用する。 (また、ARM NEON)
• AVX-512またはAVX-2による大規模データでの1ビットカウント(人口カウント)
• に関連するものです。 https://github.com/mklarqvist/positional-popcount - 複数の8、16、32、64ビット整数の各ビット位置に対して個別のカウントを行う。 (繰り返しになりますが、AVX-512を含むx86 SIMDは、これが非常に得意で vpternlogd ハーレーシールを作る 非常に 良いですね)