問題タブ [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.
algorithm - 32ビット整数で設定されたビット数を数える方法は?
数値 7 を表す 8 ビットは次のようになります。
3 ビットが設定されます。
32 ビット整数の設定ビット数を決定するアルゴリズムは何ですか?
c - unsigned char の「1」ビットの数をカウントする C コード
C の unsigned char で 1 の数を返す C コードが必要です。明らかでない場合、なぜそれが機能するのかについて説明が必要です。32 ビットの数値のコードはたくさん見つかりましたが、unsigned char のコードはあまり見つかりませんでした。
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」アルゴリズムは次のように実装されています。
コメント: シャイナーのアルゴリズムのループ展開バージョンは次のようになります。
assembly - NASM:32ビット数のビット数が1に設定されていることをカウントします
私は32ビットの数値を持っていて、1ビットの数を数えたいと思っています。
私はこの擬似コードについて考えています:
より効率的な方法はありますか?
x86プロセッサでNASMを使用しています。
(私はアセンブラーを始めたばかりなので、externライブラリのコードを使用するように言わないでください。それらを含める方法すらわからないからです;))
( 32ビット整数のセットビット数を数える方法を見つけましたか?これには私の解決策も含まれています。他の解決策も投稿されていますが、残念ながら、アセンブラーでそれらをどのように書くかがわかりません)
c - コア 2 CPU (SSSE3) を使用したラージ バッファのビット ポップカウント
512 バイト以上の大きなバッファーでポップカウントする最速の方法を探しています。必要なアラインメントはすべて保証でき、バッファ サイズは常に 2 のべき乗です。バッファはブロック割り当てに対応するため、通常、ビットはすべて設定されているか、何も設定されていないか、バッファの「左」を優先してほとんどが設定されています。たまに穴。
私が検討したいくつかの解決策は次のとおりです。
私は最速のソリューションに興味があります.core2以降に属する32ビットx86チップセットで動作する必要があります。SSE と SIMD は非常に興味深いものです。次のクアッドコア CPU でテストします。
assembly - 設定されているビット数を数える
設定されている2進数のビット数を数えたい。たとえば、ユーザーは2進数で01100001である番号97を入力します。プログラムは、MIPSISAを使用して3ビットが設定されていることを示します。
これはCで実現できますが、アセンブリコードを使用して実現する方法がわかりません。
java - Long.bitCount の最適化
Long.bitCount() に対して膨大な数の呼び出しを行っているプログラムがあり、1 つの CPU コアで 33% のサイクルを使用しています。Sun JDK バージョンよりも高速に実装する方法はありますか?
私が試してみました:
- このアルゴリズム(これはまさにJDKが実装する方法だと思います)
- 2 8から 2 22までのさまざまなサイズのルックアップ テーブル(一度に数ビットを調べて結果を加算)
しかし、手動で展開されたループ (約 27% の CPU) を持つ 2 16エントリのルックアップ テーブル以上のことはできませんでした。
これを Java 用に最適化するには、どうすればよいでしょうか?
注:この質問はJava固有の最適化に関するものですが、この同様の(言語に依存しない)質問には他の多くのアルゴリズムがあります。
java - JavaのInteger.bitCountに相当する.NET?
Integer.bitCount(int)
JavaまたはLong.bitCount(long)
.NETFrameworkのどこかに似た方法はありますか?
(これらのJavaメソッドに慣れていない人のために)これは、次のようにも知られています。
- ハミング重み
- 人口数(
POPCNT
ハードウェアに実装されている場合によく呼び出されます)。
Webには たくさん の 実装 が ありますが、標準ライブラリの実装があるのではないかと思いました。
私はこれが、、またはにないことを知っていますがBitArray
、UInt32
おそらくBitConverter
暗号関数などのどこかに隠されたバージョンがあります。
sql - T-SQL でのハミング重み/母数カウント
BINARY(1024) フィールドのハミング重み/人口カウント/「1 ビットの数」を計算する高速な方法を探しています。MySQL には、そのようなことを行う BIT_COUNT 関数があります。T-SQL で同様の関数を見つけることができませんでしたか?
または、バイナリ データを別のタイプのフィールドに格納することをお勧めしますか?
何を言っているのかわからない場合は、ハミングの重みに関するウィキペディアの記事をご覧ください。