問題タブ [hammingweight]

C++03 で 32 ビットまたは 64 ビットの整数が与えられた場合、正確に 1 ビットが設定されているかどうかを判断する効率的な方法は何ですか? (たとえば、値は正確に 1、2、4、8、16、32 などのいずれかです。) C++ 03 ライブラリ (または C++11) へのビルトインはありますか?いる？これを使用して、複数回発生する頻度が低くなる減衰メッセージに使用したいと思います。

私の仕事は、間隔 [1,10^16] の 1 ビットの数を計算することです。この場合、ループは明らかに使用できません。これにはアルゴリズムが存在すると聞いています。誰でも助けることができますか？

より一般的には、間隔 [1,n] 内の 1 ビットの数のアルゴリズムが適しています。

それが役立つ場合、間隔 [1,2^n-1]、n 正の整数の 1 ビットの数は n*2^(n-1) であると考えました。

特定のハミング重みで固定サイズの 2 進数のすべての順列を計算するアルゴリズムが必要です。たとえば、ハミングの重みが 2 で、バイナリ サイズが 4 の場合、次の出力があります。

C(n,r)このような組み合わせの数は、この例のように 6 で計算されC(4,2)ます。

数値を 0 から 2^n に増やすだけでこれを解決できることに注意して、カウントが問題ないかどうかを確認してください。ただし、これは迅速な解決策ではありません。C++ で bitset クラスを使用して問題を解決することを検討しており、N を増やす必要があります。

この問題には明らかな再帰アルゴリズムがあることを付け加えたいと思います。スタックオーバーフローのため、良い答えではありません。ゴスパーのハックからここで良い答えを受け取りました。入力をスケールアップする必要があり、後で MPI 実装を使用する可能性がありますが、スケーラブルなライブラリが必要です。unsigned int は十分に大きくないので、bitset のようなスケーラブルで高速なライブラリが必要です。ビットセット ライブラリに追加がないため、ソリューションはここでは適用できません。他の解決策はありますか？

以下は、整数に設定されたビットの量、つまりそのハミング重みを計算するためにどこかで拾ったアルゴリズムです（正確には、おそらくこの回答から忘れました）。

(たまたま PHP で便利に使用できましたが、これは実際にはどの言語でも
かまいません。) ひどく間違っていなければ、これは O(1) で実行されます。結局のところ、ブランチはありません。

ここに私が自分で書いたビットカウント関数がありますが、読みやすさは別として、私は劣っていると思います:

しかし、どのような点で劣っているのでしょうか。最初は「ループがあるので、これは線形時間で実行する必要がある」と考えていましたが、ループは入力のサイズにまったく依存しないことに気付きました。$i のサイズに関係なく、反復回数は変わりません。

私が疑問に思っているのはこれです：

• これら 2 つのアルゴリズムは、両方とも O(1) で実行できると本当に言えますか?
• もしそうなら、2つを区別する尺度はありますか? 何らかの形で最初のものの方が優れているはずです。