問題タブ [hammingweight]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票する
63 に答える
588639 参照

algorithm - 32ビット整数で設定されたビット数を数える方法は?

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

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

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

0 投票する
8 に答える
29303 参照

c - unsigned char の「1」ビットの数をカウントする C コード

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

0 投票する
9 に答える
9539 参照

matlab - matlabでハミング重みを効率的に計算する

ビット文字列として解釈される 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

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

p>


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

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

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

0 投票する
9 に答える
12624 参照

assembly - NASM:32ビット数のビット数が1に設定されていることをカウントします

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

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

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

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

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

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

0 投票する
4 に答える
8708 参照

c - コア 2 CPU (SSSE3) を使用したラージ バッファのビット ポップカウント

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

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

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

0 投票する
5 に答える
8424 参照

assembly - 設定されているビット数を数える

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

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

0 投票する
8 に答える
5366 参照

java - Long.bitCount の最適化

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

私が試してみました:

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

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


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

0 投票する
4 に答える
3045 参照

java - JavaのInteger.bitCountに相当する.NET?

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

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

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

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

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

0 投票する
4 に答える
1759 参照

sql - T-SQL でのハミング重み/母数カウント

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

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

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