問題タブ [hammingweight]

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

3 ビットが設定されます。

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

C の unsigned char で 1 の数を返す C コードが必要です。明らかでない場合、なぜそれが機能するのかについて説明が必要です。32 ビットの数値のコードはたくさん見つかりましたが、unsigned char のコードはあまり見つかりませんでした。

ビット文字列として解釈される MATLAB uint32 が与えられた場合、文字列に含まれる非ゼロ ビットの数を効率的かつ簡潔にカウントする方法は何ですか?

ビットをループする実用的で単純なアプローチがありますが、それは私のニーズには遅すぎます。(std::bitset count() を使用した C++ 実装はほぼ瞬時に実行されます)。

さまざまなビット カウント手法をリストしている非常に優れたページを見つけましたが、簡単な MATLAB 風の方法があることを願っています。

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

更新 #1

Brian Kernighan アルゴリズムを次のように実装しました。

パフォーマンスは依然として悪く、4096^2 の重み計算を計算するのに 10 秒以上かかります。std::bitset の count() を使用する私の C++ コードは、これを 1 秒未満の時間で実行します。

アップデート #2

これまでに試した手法の実行時間の表を次に示します。追加のアイデアや提案があれば更新します。

コメント: MATLAB の dec2bin() 関数は、実装が非常に不十分なようです。実行速度が非常に遅いです。

コメント: 「Naive bitget loop」アルゴリズムは次のように実装されています。

コメント: シャイナーのアルゴリズムのループ展開バージョンは次のようになります。

私は32ビットの数値を持っていて、1ビットの数を数えたいと思っています。

私はこの擬似コードについて考えています：

より効率的な方法はありますか？

x86プロセッサでNASMを使用しています。

（私はアセンブラーを始めたばかりなので、externライブラリのコードを使用するように言わないでください。それらを含める方法すらわからないからです;））

（ 32ビット整数のセットビット数を数える方法を見つけましたか？これには私の解決策も含まれています。他の解決策も投稿されていますが、残念ながら、アセンブラーでそれらをどのように書くかがわかりません）

512 バイト以上の大きなバッファーでポップカウントする最速の方法を探しています。必要なアラインメントはすべて保証でき、バッファ サイズは常に 2 のべき乗です。バッファはブロック割り当てに対応するため、通常、ビットはすべて設定されているか、何も設定されていないか、バッファの「左」を優先してほとんどが設定されています。たまに穴。

私が検討したいくつかの解決策は次のとおりです。

• GCCの__builtin_popcount
• ビットスライスpopcount_24words
• カウント ビット セット、ブライアン カーニハンのやり方

私は最速のソリューションに興味があります.core2以降に属する32ビットx86チップセットで動作する必要があります。SSE と SIMD は非常に興味深いものです。次のクアッドコア CPU でテストします。

設定されている2進数のビット数を数えたい。たとえば、ユーザーは2進数で01100001である番号97を入力します。プログラムは、MIPSISAを使用して3ビットが設定されていることを示します。

これはCで実現できますが、アセンブリコードを使用して実現する方法がわかりません。

Long.bitCount() に対して膨大な数の呼び出しを行っているプログラムがあり、1 つの CPU コアで 33% のサイクルを使用しています。Sun JDK バージョンよりも高速に実装する方法はありますか?

私が試してみました：

• このアルゴリズム（これはまさにJDKが実装する方法だと思います）
• ^{2 8}から 2 ²²までのさまざまなサイズのルックアップ テーブル(一度に数ビットを調べて結果を加算)

^{しかし、手動で展開されたループ (約 27% の CPU) を持つ 2 16}エントリのルックアップ テーブル以上のことはできませんでした。
これを Java 用に最適化するには、どうすればよいでしょうか?

注：この質問はJava固有の最適化に関するものですが、この同様の（言語に依存しない）質問には他の多くのアルゴリズムがあります。

Integer.bitCount(int)JavaまたはLong.bitCount(long).NETFrameworkのどこかに似た方法はありますか？

（これらのJavaメソッドに慣れていない人のために）これは、次のようにも知られています。

• ハミング重み
• 人口数（POPCNTハードウェアに実装されている場合によく呼び出されます）。

Webには たくさん の 実装 が ありますが、標準ライブラリの実装があるのではないかと思いました。

私はこれが、、またはにないことを知っていますがBitArray、UInt32おそらくBitConverter暗号関数などのどこかに隠されたバージョンがあります。

BINARY(1024) フィールドのハミング重み/人口カウント/「1 ビットの数」を計算する高速な方法を探しています。MySQL には、そのようなことを行う BIT_COUNT 関数があります。T-SQL で同様の関数を見つけることができませんでしたか?

または、バイナリ データを別のタイプのフィールドに格納することをお勧めしますか?

何を言っているのかわからない場合は、ハミングの重みに関するウィキペディアの記事をご覧ください。