数値 7 を表す 8 ビットは次のようになります。
00000111
3 ビットが設定されます。
32 ビット整数の設定ビット数を決定するアルゴリズムは何ですか?
588639 次
63 に答える
942
これは、「ハミング ウェイト」、「ポップカウント」、または「横方向の追加」として知られています。
一部の CPU にはそれを実行するための単一の組み込み命令があり、他の CPU にはビット ベクトルで動作する並列命令があります。x86 のような命令popcnt(サポートされている CPU 上) は、単一の整数に対してほぼ確実に最速になります。他のいくつかのアーキテクチャには、サイクルごとにビットをテストするマイクロコード化されたループで実装された遅い命令がある場合があります (引用が必要です- ハードウェア popcount は、存在する場合、通常は高速です)。
「最適な」アルゴリズムは、使用している CPU と使用パターンによって異なります。
コンパイラーは、組み込み/組み込み関数にアクセスするための移植可能な方法として、コンパイルしている特定の CPU (たとえば、C++20std::popcount()や C++ ) に適した方法を知っている場合があります (この質問に関する別の回答を参照)。ただし、ハードウェア popcnt を持たないターゲット CPU に対するコンパイラのフォールバックの選択は、ユースケースに最適ではない可能性があります。または、使用している言語 (C など) では、CPU 固有の popcount がある場合にそれを使用できる移植可能な関数が公開されていない可能性があります。std::bitset<32>::count()
ハードウェア サポートを必要としない (または恩恵を受けない) ポータブル アルゴリズム
CPU に大きなキャッシュがあり、これらの操作をタイトなループで多数実行している場合、事前設定されたテーブル ルックアップ メソッドは非常に高速です。ただし、CPU がメイン メモリからテーブルの一部を取得しなければならない「キャッシュ ミス」が発生するため、問題が発生する可能性があります。(テーブルを小さく保つために、各バイトを個別に検索します。) 連続した範囲の数値の popcount が必要な場合、256 の数値のグループに対して下位バイトのみが変更されるため、これは非常に優れています。
バイトの大部分が 0 または大部分 1 であることがわかっている場合は、これらのシナリオに対応する効率的なアルゴリズムがあります。たとえば、ループ内で bithack を使用して最小セットをゼロになるまでクリアします。
非常に優れた汎用アルゴリズムは、「並列」または「可変精度 SWAR アルゴリズム」として知られる次のアルゴリズムだと思います。これを C に似た疑似言語で表現しました。特定の言語で機能するように調整する必要がある場合があります (たとえば、C++ では uint32_t を使用し、Java では >>> を使用します)。
GCC10 と clang 10.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 の場合:パフォーマンスのために整数に変換: 最初の行を次のように変更します。|0i = (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 ビット アキュムレータ ( SWAR = SIMD Within A Register ) で 16 の個別の加算が効果的に実行されます。のように(i & 0x55555555) + ((i>>1) & 0x55555555)。
次のステップでは、これらの 16x 2 ビット アキュムレータの奇数/偶数 8 個を取り、再度加算して、8x 4 ビットの合計を生成します。今回i - ...は最適化ができないため、シフトの前後にマスクするだけです。32 ビット定数をレジスターに別々に作成する必要がある ISA 用にコンパイルする場合、シフト前ではなく両方で同じ0x33...定数を使用することは良いことです。0xccc...
最後のシフトと加算のステップは(i + (i >> 4)) & 0x0F0F0F0F、4x 8 ビット アキュムレータに拡張されます。対応する入力ビットの 4 ビットすべてが設定されている場合、任意の 4 ビット アキュムレータの最大値は であるため、加算前ではなく加算後にマスクします。44+4 = 8 でも 4 ビットに収まるので、ニブル要素間のキャリーは では不可能ですi + (i >> 4)。
これまでのところ、これは SWAR 手法を使用したごく普通の SIMD であり、いくつかの巧妙な最適化が行われています。同じパターンをさらに 2 ステップ続けると、16 ビット カウントが 2 倍になり、32 ビット カウントが 1 倍になります。しかし、ハードウェア乗算が高速なマシンでは、より効率的な方法があります。
十分な数の「要素」が得られたら、魔法の定数を使用した乗算により、すべての要素を合計して最上位の要素にすることができます。この場合、バイト要素。乗算は左シフトと加算によって行われるため、 の乗算は にx * 0x01010101なりますx + (x<<8) + (x<<16) + (x<<24)。 私たちの 8 ビット要素は十分に幅が広く (そして十分に小さいカウントを保持) 、上位 8 ビットへのキャリーは生成されません。
これの 64 ビット バージョンは、0x0101010101010101 乗数を使用して 64 ビット整数で 8x 8 ビット要素を実行し、. で上位バイトを抽出できます>>56。したがって、追加の手順は必要なく、幅の広い定数だけです。これは、ハードウェア命令が有効になっていない__builtin_popcountll場合に、x86 システムでGCC が使用するものです。popcntこれにビルトインまたは組み込みを使用できる場合は、コンパイラにターゲット固有の最適化を行う機会を与えるために使用してください。
より広いベクトル用の完全な SIMD を使用 (例: 配列全体をカウント)
このビットごとの SWAR アルゴリズムは、単一の整数レジスタではなく、一度に複数のベクトル要素で実行されるように並列化でき、SIMD を使用するが使用可能な popcount 命令がない CPU で高速化できます。(たとえば、Nehalem 以降だけでなく、任意の CPU で実行する必要がある x86-64 コード。)
ただし、ポップカウントにベクトル命令を使用する最良の方法は、通常、変数シャッフルを使用して、各バイトの一度に 4 ビットのテーブル ルックアップを並行して行うことです。(4 ビットは、ベクトル レジスタに保持される 16 エントリ テーブルにインデックスを付けます)。
Intel CPU では、ハードウェア 64 ビット popcnt 命令は、SSSE3PSHUFBビット並列実装よりも約 2 倍優れたパフォーマンスを発揮しますが、それはコンパイラが適切に処理できる場合のみです。そうしないと、SSE が大幅に有利になる可能性があります。新しいコンパイラ バージョンでは、Intel でのpopcnt false 依存関係の 問題が認識されています。
- https://github.com/WojciechMula/sse-popcount SSSE3、AVX2、AVX512BW、AVX512VBMI、または AVX512 VPOPCNT の最先端の x86 SIMD ポップカウント。ベクトル全体で Harley-Seal を使用して、要素内の popcount を延期します。（アームネオンも）
- AVX-512 または AVX-2 を使用して大きなデータの 1 ビット (ポピュレーション カウント) をカウントする
- 関連: https://github.com/mklarqvist/positional-popcount - 複数の 8、16、32、または 64 ビット整数のビット位置ごとに個別のカウント。
vpternlogd(繰り返しになりますが、Harley-Seal を非常に優れたものにすることで、これが非常に得意な AVX-512 を含む x86 SIMDです。)
于 2008-09-20T19:05:22.550 に答える
240
一部の言語は、利用可能な場合は効率的なハードウェア サポートを使用できる方法で操作を移植可能に公開します。
例 (言語別の表から):
- C++ は
std::bitset<>::count()、または C++20を持っていますstd::popcount(T x) - Java は
java.lang.Integer.bitCount()(Long または BigInteger にも) - C# は
System.Numerics.BitOperations.PopCount() - Python には
int.bit_count()(3.10 以降)
ただし、すべてのコンパイラ/ライブラリが実際に HW サポートを利用できるわけではありません。(特に MSVC では、std::popcount を x86 popcnt としてインライン化するオプションがあっても、その std::bitset::count は常にルックアップ テーブルを使用します。これは将来のバージョンで変更されることが期待されます。)
移植可能な言語にこの基本的なビット操作がない場合は、コンパイラの組み込み関数も考慮してください。たとえば、GNU C では次のようになります。
int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);
最悪の場合 (単一命令の HW サポートがない場合)、コンパイラは関数の呼び出しを生成します (現在の GCC では、少なくとも x86 の場合、この回答のようにシフト/およびビットハックを使用します)。最良の場合、コンパイラはジョブを実行するための cpu 命令を発行します。*( or演算子と同様に、/GCC は利用可能な場合はハードウェアの乗算または除算命令を使用し、そうでない場合は libgcc ヘルパー関数を呼び出します。) またはさらに良いことに、オペランドがインライン化後のコンパイル時の定数である場合、定数伝播を実行できます。コンパイル時定数 popcount 結果を取得します。
GCC ビルトインは複数のプラットフォームで動作します。Popcount は x86 アーキテクチャでほぼ主流になっているため、今すぐビルトインの使用を開始することは理にかなっています。これにより、コンパイル時にハードウェア命令-mpopcntまたはそれを含むものをインライン化するために再コンパイルできます (例: https://godbolt.org/ z/Ma5e5a )。他のアーキテクチャでは何年もポップカウントが行われてきましたが、x86 の世界では、古い Core 2 や同様のビンテージ AMD CPU がまだ使用されています。
x86 では、 ( によっても暗示される) をpopcnt使用した命令のサポートを想定できることをコンパイラに伝えることができます。GCC x86 オプションを参照してください。 (または、コードで想定して調整する必要のある CPU) が適切な選択になる可能性があります。生成されたバイナリを古い CPU で実行すると、不正な命令エラーが発生します。-mpopcnt-msse4.2-march=nehalem -mtune=skylake-march=
ビルドするマシンに最適化されたバイナリを作成するには、 (gcc、clang、または ICC と共に) を使用します。-march=native
MSVC は x86popcnt命令の組み込み関数を提供しますが、gcc とは異なり、実際にはハードウェア命令の組み込み関数であり、ハードウェア サポートが必要です。
std::bitset<>::count()組み込みの代わりに使用する
理論的には、ターゲット CPU に対して効率的にポップカウントする方法を知っているコンパイラは、ISO C++ を通じてその機能を公開する必要がありますstd::bitset<>。実際には、一部のターゲット CPU では、場合によってはビットハック AND/シフト/ADD を使用したほうがよい場合があります。
ハードウェア popcount がオプションの拡張機能 (x86 など) であるターゲット アーキテクチャの場合、すべてのコンパイラがstd::bitset利用可能な場合にそれを利用するわけではありません。たとえば、MSVC にはpopcntコンパイル時にサポートを有効にする方法がなく、 (SSE4.2 を意味し、popcnt 機能を意味する) であっても、std::bitset<>::count常にtable lookup を使用します(更新: 以下を参照してください。これはMSVC のC++20は x86 を使用しますが、bitset<>::count はまだ使用できません。MSVC は、標準ライブラリ ヘッダーを更新して、利用可能な場合は std::popcount を使用することで修正できます。)/Ox /arch:AVXstd::popcountpopcnt
しかし、少なくともどこでも動作するポータブルなものを手に入れ、適切なターゲット オプションを備えた gcc/clang を使用すると、それをサポートするアーキテクチャのハードウェア ポップカウントを取得できます。
#include <bitset>
#include <limits>
#include <type_traits>
template<typename T>
//static inline // static if you want to compile with -mpopcnt in one compilation unit but not others
typename std::enable_if<std::is_integral<T>::value, unsigned >::type
popcount(T x)
{
static_assert(std::numeric_limits<T>::radix == 2, "non-binary type");
// sizeof(x)*CHAR_BIT
constexpr int bitwidth = std::numeric_limits<T>::digits + std::numeric_limits<T>::is_signed;
// std::bitset constructor was only unsigned long before C++11. Beware if porting to C++03
static_assert(bitwidth <= std::numeric_limits<unsigned long long>::digits, "arg too wide for std::bitset() constructor");
typedef typename std::make_unsigned<T>::type UT; // probably not needed, bitset width chops after sign-extension
std::bitset<bitwidth> bs( static_cast<UT>(x) );
return bs.count();
}
Godbolt コンパイラ エクスプローラで、gcc、clang、icc、および MSVC から asm を参照してください。
x86-64gcc -O3 -std=gnu++11 -mpopcntはこれを出力します:
unsigned test_short(short a) { return popcount(a); }
movzx eax, di # note zero-extension, not sign-extension
popcnt rax, rax
ret
unsigned test_int(int a) { return popcount(a); }
mov eax, edi
popcnt rax, rax # unnecessary 64-bit operand size
ret
unsigned test_u64(unsigned long long a) { return popcount(a); }
xor eax, eax # gcc avoids false dependencies for Intel CPUs
popcnt rax, rdi
ret
PowerPC64は以下を発行gcc -O3 -std=gnu++11します ( intarg バージョンの場合):
rldicl 3,3,0,32 # zero-extend from 32 to 64-bit
popcntd 3,3 # popcount
blr
このソースは x86 固有でも GNU 固有でもありませんが、少なくとも x86 (x86-64 を含む) を対象とする場合は、gcc/clang/icc でのみ適切にコンパイルされます。
また、単一命令 popcount を使用しないアーキテクチャに対する gcc のフォールバックは、一度に 1 バイトのテーブル ルックアップであることにも注意してください。これは、たとえば ARM にとって素晴らしいことではありません。
C++20 にはstd::popcount(T)
残念ながら、現在の libstdc++ ヘッダーif(x==0) return 0;では、最初に特殊なケースで定義されており、clang は x86 用にコンパイルするときに最適化されません。
#include <bit>
int bar(unsigned x) {
return std::popcount(x);
}
クラン 11.0.1 -O3 -std=gnu++20 -march=nehalem ( https://godbolt.org/z/arMe5a )
# clang 11
bar(unsigned int): # @bar(unsigned int)
popcnt eax, edi
cmove eax, edi # redundant: if popcnt result is 0, return the original 0 instead of the popcnt-generated 0...
ret
しかし、GCC はうまくコンパイルできます。
# gcc 10
xor eax, eax # break false dependency on Intel SnB-family before Ice Lake.
popcnt eax, edi
ret
-arch:AVX またはそれ以降を使用する (および で C++20 を有効にする)限り、MSVC でも問題なく動作します-std:c++latest。https://godbolt.org/z/7K4Gef
int bar(unsigned int) PROC ; bar, COMDAT
popcnt eax, ecx
ret 0
int bar(unsigned int) ENDP ; bar
于 2008-09-20T19:23:05.220 に答える
205
私の意見では、「最良の」解決策は、他のプログラマー（または2年後の元のプログラマー）が大量のコメントなしで読むことができる解決策です。すでに提供されている最速または最も賢いソリューションが必要な場合もありますが、私はいつでも賢さよりも読みやすさを好みます。
unsigned int bitCount (unsigned int value) {
unsigned int count = 0;
while (value > 0) { // until all bits are zero
if ((value & 1) == 1) // check lower bit
count++;
value >>= 1; // shift bits, removing lower bit
}
return count;
}
より高速にしたい場合（そして後継者を助けるためにそれをうまく文書化すると仮定して）、テーブルルックアップを使用できます：
// Lookup table for fast calculation of bits set in 8-bit unsigned char.
static unsigned char oneBitsInUChar[] = {
// 0 1 2 3 4 5 6 7 8 9 A B C D E F (<- n)
// =====================================================
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, // 0n
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, // 1n
: : :
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, // Fn
};
// Function for fast calculation of bits set in 16-bit unsigned short.
unsigned char oneBitsInUShort (unsigned short x) {
return oneBitsInUChar [x >> 8]
+ oneBitsInUChar [x & 0xff];
}
// Function for fast calculation of bits set in 32-bit unsigned int.
unsigned char oneBitsInUInt (unsigned int x) {
return oneBitsInUShort (x >> 16)
+ oneBitsInUShort (x & 0xffff);
}
これらは特定のデータ型サイズに依存しているため、それほど移植性はありません。ただし、パフォーマンスの最適化の多くは移植性がないため、問題にならない可能性があります。移植性が必要な場合は、読みやすいソリューションに固執します。
于 2008-09-21T01:14:03.287 に答える
103
Hacker's Delight より、p. 66、図 5-2
int pop(unsigned x)
{
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003F;
}
~20 程度の命令 (アーキテクチャに依存) で実行され、分岐はありません。
ハッカーの喜び は楽しいです！強くお勧めします。
于 2008-09-20T19:38:00.427 に答える
81
ルックアップ テーブルとポップカウントを使用しない最速の方法は次のとおりです。セットされたビットをわずか 12 回の操作でカウントします。
int popcount(int v) {
v = v - ((v >> 1) & 0x55555555); // put count of each 2 bits into those 2 bits
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // put count of each 4 bits into those 4 bits
return c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
これは、2 つの半分に分割し、両方の半分で設定されたビットの数をカウントしてからそれらを合計することで、設定されたビットの総数をカウントできるため機能します。パラダイムともDivide and Conquerいう。詳しく見ていきましょう..
v = v - ((v >> 1) & 0x55555555);
2 ビットのビット数は0b00、0b01または0b10です。これを 2 ビットで解決してみましょう。
---------------------------------------------
| v | (v >> 1) & 0b0101 | v - x |
---------------------------------------------
0b00 0b00 0b00
0b01 0b00 0b01
0b10 0b01 0b01
0b11 0b01 0b10
これが必要でした。最後の列には、2 つのビット ペアごとに設定されたビットの数が表示されます。2 ビット数が>= 2 (0b10)をand生成する0b01場合、そうでない場合は を生成し0b00ます。
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
このステートメントは理解しやすいはずです。最初の操作の後、2 ビットごとに設定されたビットのカウントが得られます。次に、4 ビットごとにそのカウントを合計します。
v & 0b00110011 //masks out even two bits
(v >> 2) & 0b00110011 // masks out odd two bits
次に、上記の結果を合計すると、セットされたビットの総数が 4 ビットになります。最後のステートメントは最もトリッキーです。
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
さらに分解してみましょう...
v + (v >> 4)
これは 2 番目のステートメントに似ています。代わりに、設定されたビットを 4 つのグループでカウントしています。以前の操作により、すべてのニブルにはセットされたビット数が含まれていることがわかっています。例を見てみましょう。byte があるとします0b01000010。これは、最初のニブルには 4 ビットが設定され、2 番目のニブルには 2 ビットが設定されていることを意味します。次に、それらのニブルを一緒に追加します。
0b01000010 + 0b01000000
最初のニブルで 1 バイトのセット ビット数が得られる0b01100010ため、数値内のすべてのバイトの最後の 4 バイトをマスクします (それらを破棄します)。
0b01100010 & 0xF0 = 0b01100000
これで、すべてのバイトにセットされたビットの数が含まれます。それらをすべて合計する必要があります。0b10101010トリックは、興味深い特性を持つ結果を掛けることです。数値が 4 バイトの場合、A B C Dこれらのバイトを持つ新しい数値になりますA+B+C+D B+C+D C+D D。4 バイトの数値には、最大 32 ビットを設定できます。これは として表すことができます0b00100000。
ここで必要なのは、すべてのバイトに設定されたすべてのビットの合計を持つ最初のバイトであり、 によって取得し >> 24ます。このアルゴリズムは単語用に設計されてい32 bitますが、単語用に簡単に変更でき64 bitます。
于 2013-04-12T19:14:12.370 に答える
62
たまたま Java を使用している場合は、組み込みメソッドInteger.bitCountがそれを行います。
于 2008-09-20T19:14:39.733 に答える
58
私は退屈し、3 つのアプローチを 10 億回繰り返して時間を計りました。コンパイラは gcc -O3 です。CPUは、第1世代のMacbook Proに搭載されているものです。
最速は次の 3.7 秒です。
static unsigned char wordbits[65536] = { bitcounts of ints between 0 and 65535 };
static int popcount( unsigned int i )
{
return( wordbits[i&0xFFFF] + wordbits[i>>16] );
}
2 位は同じコードですが、2 つのハーフワードではなく 4 バイトを検索します。約5.5秒かかりました。
3 位は、8.6 秒かかった少しいじる「横方向の加算」アプローチです。
4 位は GCC の __builtin_popcount() で、恥ずべき 11 秒です。
一度に 1 ビットずつカウントするアプローチは非常に遅く、完了するのを待つのに飽きてしまいました。
したがって、何よりもパフォーマンスを重視する場合は、最初のアプローチを使用してください。気にしても 64Kb の RAM を費やすほどではない場合は、2 番目の方法を使用してください。それ以外の場合は、読み取り可能な (ただし遅い) 1 ビットずつのアプローチを使用します。
少しいじるアプローチを使用したい状況を考えるのは難しいです。
編集: 同様の結果はこちら.
于 2008-09-25T02:46:32.720 に答える
38
unsigned int count_bit(unsigned int x)
{
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >> 16)& 0x0000FFFF);
return x;
}
このアルゴリズムについて説明します。
このアルゴリズムは、分割統治アルゴリズムに基づいています。8 ビット整数 213 (バイナリで 11010101) があると仮定すると、アルゴリズムは次のように機能します (毎回 2 つの隣接ブロックをマージします)。
+-------------------------------+
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | <- x
| 1 0 | 0 1 | 0 1 | 0 1 | <- first time merge
| 0 0 1 1 | 0 0 1 0 | <- second time merge
| 0 0 0 0 0 1 0 1 | <- third time ( answer = 00000101 = 5)
+-------------------------------+
于 2012-08-05T12:47:03.247 に答える
31
繰り返し2で除算しないのはなぜですか?
カウント = 0
n > 0 の間
もし (n % 2) == 1
カウント += 1
n /= 2
これが最速ではないことに同意しますが、「最高」はややあいまいです。「最高」には明快さの要素が必要だと私は主張します
于 2008-09-20T19:10:30.057 に答える
29
これは、マイクロアーキテクチャを知ることが役立つ質問の 1 つです。-O3 を使用して C++ インラインを使用してコンパイルされた gcc 4.3.3 の下で 2 つのバリアントのタイミングを計りました。関数呼び出しのオーバーヘッド、10 億回の反復を排除し、すべてのカウントの実行中の合計を維持して、コンパイラが重要なものを削除しないようにします。タイミングには rdtsc を使用します (正確なクロック サイクル）。
inline int pop2(符号なし x, 符号なし y)
{
x = x - ((x >> 1) & 0x55555555);
y = y - ((y >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
y = (y & 0x33333333) + ((y >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
y = (y + (y >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
y = y + (y >> 8);
x = x + (x >> 16);
y = y + (y >> 16);
(x+y) & 0x000000FF を返します。
}
変更されていない Hacker's Delight は 12.2 ギガサイクルかかりました。私の並列バージョン (2 倍のビット数をカウント) は、13.0 ギガサイクルで実行されます。2.4GHz Core Duo で両方を合わせて合計 10.5 秒経過。25 ギガサイクル = このクロック周波数で 10 秒強なので、タイミングが正しいと確信しています。
これは、このアルゴリズムにとって非常に悪い命令依存チェーンに関係しています。2 つの 64 ビット レジスタを使用することで、速度をほぼ 2 倍にすることができました。実際、私が賢く x+ya をもう少し早く追加すれば、いくつかのシフトを削ることができました。いくつかの小さな調整を加えた 64 ビット バージョンはほぼ均等になりますが、再び 2 倍のビット数をカウントします。
128 ビットの SIMD レジスタを使用すると、さらに 2 倍になり、SSE 命令セットにも巧妙なショートカットが含まれることがよくあります。
コードが特に透過的である必要はありません。インターフェイスはシンプルで、アルゴリズムは多くの場所でオンラインで参照でき、包括的な単体テストに適しています。これに出くわしたプログラマーは、何かを学ぶことさえあるかもしれません。これらのビット操作は、マシン レベルでは非常に自然です。
OK、微調整した 64 ビット バージョンをベンチに置くことにしました。この 1 つの sizeof(unsigned long) == 8 の場合
inline int pop2(unsigned long x, unsigned long y)
{
x = x - ((x >> 1) & 0x5555555555555555);
y = y - ((y >> 1) & 0x5555555555555555);
x = (x & 0x3333333333333333) + ((x >> 2) & 0x333333333333333);
y = (y & 0x3333333333333333) + ((y >> 2) & 0x333333333333333);
x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
y = (y + (y >> 4)) & 0x0F0F0F0F0F0F0F0F;
x = x + y;
x = x + (x >> 8);
x = x + (x >> 16);
x = x + (x >> 32);
x & 0xFF を返します。
}
それはほぼ正しいように見えます（ただし、慎重にテストしていません）。これで、タイミングは 10.70 ギガサイクル / 14.1 ギガサイクルになります。後の数字は 1280 億ビットを合計し、このマシンで経過した 5.9 秒に相当します。私は 64 ビット モードで実行しており、32 ビット レジスタよりも 64 ビット レジスタの方がわずかに優れているため、非並列バージョンはわずかに高速化されています。
ここで、もう少し OOO パイプライン処理が必要かどうか見てみましょう。これはもう少し複雑だったので、実際に少しテストしました。各項だけの合計は 64 で、すべてを合わせると 256 になります。
inline int pop4(unsigned long x, unsigned long y,
unsigned long u、unsigned long v)
{
列挙型 { m1 = 0x5555555555555555、
m2 = 0x3333333333333333、
m3 = 0x0F0F0F0F0F0F0F0F、
m4 = 0x000000FF000000FF };
x = x - ((x >> 1) & m1);
y = y - ((y >> 1) & m1);
u = u - ((u >> 1) & m1);
v = v - ((v >> 1) & m1);
x = (x & m2) + ((x >> 2) & m2);
y = (y & m2) + ((y >> 2) & m2);
u = (u & m2) + ((u >> 2) & m2);
v = (v & m2) + ((v >> 2) & m2);
x = x + y;
u = u + v;
x = (x & m3) + ((x >> 4) & m3);
u = (u & m3) + ((u >> 4) & m3);
x = x + u;
x = x + (x >> 8);
x = x + (x >> 16);
x = x & m4;
x = x + (x >> 32);
x & 0x000001FF を返します。
}
ちょっと興奮しましたが、いくつかのテストで inline キーワードを使用していないにもかかわらず、gcc が -O3 でインライン トリックを実行していることがわかりました。gcc にトリックをさせたところ、pop4() の 10 億回の呼び出しに 12.56 ギガサイクルかかりましたが、これは引数を定数式として折りたたんでいると判断しました。より現実的な数値は、さらに 30% 高速化するための 19.6gc のようです。テスト ループは次のようになり、gcc がトリックを実行するのを停止するのに十分なだけ各引数が異なることを確認します。
htime b4 = rdtsc();
for (unsigned long i = 10L * 1000*1000*1000; i < 11L * 1000*1000*1000; ++i)
sum += pop4 (i, i^1, ~i, i|1);
htime e4 = rdtsc();
8.17 秒で合計 2,560 億ビットが経過しました。16 ビット テーブル ルックアップでベンチマークされると、3200 万ビットで 1.02 秒になります。他のベンチはクロック速度を示していないため、直接比較することはできませんが、そもそも L1 キャッシュの悲劇的な使用法である 64KB テーブル エディションから抜け出したようです。
更新: さらに 4 つの重複した行を追加して pop6() を作成することにしました。22.8gc になり、合計 3840 億ビットが 9.5 秒経過しました。つまり、320 億ビットの 800 ミリ秒で、さらに 20% あります。
于 2009-10-02T21:34:54.937 に答える
27
ビット パターンを書き出すと、Hacker's Delight のビット操作が非常に明確になります。
unsigned int bitCount(unsigned int x)
{
x = ((x >> 1) & 0b01010101010101010101010101010101)
+ (x & 0b01010101010101010101010101010101);
x = ((x >> 2) & 0b00110011001100110011001100110011)
+ (x & 0b00110011001100110011001100110011);
x = ((x >> 4) & 0b00001111000011110000111100001111)
+ (x & 0b00001111000011110000111100001111);
x = ((x >> 8) & 0b00000000111111110000000011111111)
+ (x & 0b00000000111111110000000011111111);
x = ((x >> 16)& 0b00000000000000001111111111111111)
+ (x & 0b00000000000000001111111111111111);
return x;
}
最初のステップでは、偶数ビットを奇数ビットに追加し、2 つのビットの合計を生成します。他のステップでは、上位のチャンクを下位のチャンクに追加し、最終的なカウントが int 全体を占めるまで、チャンク サイズを 2 倍にします。
于 2013-12-20T06:55:35.740 に答える
23
2 32ルックアップ テーブルと各ビットを個別に反復処理することの間の満足のいく媒体の場合:
int bitcount(unsigned int num){
int count = 0;
static int nibblebits[] =
{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
for(; num != 0; num >>= 4)
count += nibblebits[num & 0x0f];
return count;
}
于 2008-09-22T03:55:59.800 に答える
19
これは で行うことができますO(k)。ここで、kは設定されたビット数です。
int NumberOfSetBits(int n)
{
int count = 0;
while (n){
++ count;
n = (n - 1) & n;
}
return count;
}
于 2014-01-14T12:53:05.003 に答える
17
それは最速または最良の解決策ではありませんが、私の方法で同じ質問を見つけ、考え、考え始めました。最後に、数学的な側面から問題を取得し、グラフを描画すると、このように実行できることに気付きました。それから、それが周期的な部分を持つ関数であることがわかり、周期の違いに気付く...だからどうぞ：
unsigned int f(unsigned int x)
{
switch (x) {
case 0:
return 0;
case 1:
return 1;
case 2:
return 1;
case 3:
return 2;
default:
return f(x/4) + f(x%4);
}
}
于 2012-10-19T12:31:03.940 に答える
10
探している関数は、2進数の「横和」または「人口カウント」と呼ばれることがよくあります。Knuthは、それについてFascicle 1A以前のpp11-12で説明しています（ただし、Volume 2、4.6.3-（7）に簡単な参照がありました）。
軌跡classicusは、ACMのCommunications、Volume 3（1960）Number 5、 page322のPeterWegnerの記事「バイナリコンピュータで1を数えるためのテクニック」です。彼はそこで2つの異なるアルゴリズムを提供します。1つは「スパース」であると予想される数（つまり、少数の数）に最適化され、もう1つは反対の場合に最適化されます。
于 2008-09-23T09:20:15.830 に答える
9
いくつかの未解決の質問:-
- 数が負の場合は？
- 数値が 1024 の場合、「反復的に 2 で割る」メソッドは 10 回反復します。
次のように、負の数をサポートするようにアルゴリズムを変更できます。
count = 0
while n != 0
if ((n % 2) == 1 || (n % 2) == -1
count += 1
n /= 2
return count
2番目の問題を克服するために、アルゴリズムを次のように書くことができます:-
int bit_count(int num)
{
int count=0;
while(num)
{
num=(num)&(num-1);
count++;
}
return count;
}
完全なリファレンスについては、次を参照してください。
http://goursaha.freeoda.com/Miscellaneous/IntegerBitCount.html
于 2010-05-07T04:51:57.037 に答える
8
より直感的な以下のコードを使用します。
int countSetBits(int n) {
return !n ? 0 : 1 + countSetBits(n & (n-1));
}
ロジック : n & (n-1) n の最後のセット ビットをリセットします。
PS : 興味深いソリューションではありますが、これは O(1) ソリューションではないことはわかっています。
于 2012-05-05T07:12:53.040 に答える
7
私は 1990 年頃に RISC マシン用の高速ビットカウント マクロを作成しました。高度な演算 (乗算、除算、%)、メモリ フェッチ (遅すぎる)、分岐 (遅すぎる) は使用しませんが、CPU に32 ビット バレル シフター (つまり、>> 1 と >> 32 は同じ量のサイクルを必要とします。) 小さい定数 (6、12、24 など) は、レジスターにロードするコストがかからない、または格納されると仮定します。一時的で、何度も再利用されます。
これらの仮定では、ほとんどの RISC マシンで約 16 サイクル/命令で 32 ビットをカウントします。15 命令/サイクルは、サイクル数または命令数の下限に近いことに注意してください。加数の数を半分に削減するには、少なくとも 3 つの命令 (マスク、シフト、演算子) が必要なように思われるため、log_2(32) = 5、5 x 3 = 15 命令は準下限です。
#define BitCount(X,Y) \
Y = X - ((X >> 1) & 033333333333) - ((X >> 2) & 011111111111); \
Y = ((Y + (Y >> 3)) & 030707070707); \
Y = (Y + (Y >> 6)); \
Y = (Y + (Y >> 12) + (Y >> 24)) & 077;
最初の最も複雑なステップの秘密は次のとおりです。
input output
AB CD Note
00 00 = AB
01 01 = AB
10 01 = AB - (A >> 1) & 0x1
11 10 = AB - (A >> 1) & 0x1
したがって、上記の最初の列 (A) を右に 1 ビットシフトし、AB から減算すると、出力 (CD) が得られます。3 ビットへの拡張も同様です。必要に応じて、上記のような 8 行のブール テーブルで確認できます。
- ドン・ギリーズ
于 2010-06-11T21:40:40.173 に答える
7
C++ を使用している場合、別のオプションはテンプレート メタプログラミングを使用することです。
// recursive template to sum bits in an int
template <int BITS>
int countBits(int val) {
// return the least significant bit plus the result of calling ourselves with
// .. the shifted value
return (val & 0x1) + countBits<BITS-1>(val >> 1);
}
// template specialisation to terminate the recursion when there's only one bit left
template<>
int countBits<1>(int val) {
return val & 0x1;
}
使用法は次のとおりです。
// to count bits in a byte/char (this returns 8)
countBits<8>( 255 )
// another byte (this returns 7)
countBits<8>( 254 )
// counting bits in a word/short (this returns 1)
countBits<16>( 256 )
もちろん、このテンプレートをさらに拡張して、さまざまなタイプを使用することもできますが (ビット サイズの自動検出も可能)、わかりやすくするために単純にしています。
編集：これはどのC++コンパイラでも機能するはずであり、ビットカウントに定数値が使用されている場合は基本的にループを展開するだけなので、これは良いことを言うのを忘れていました（言い換えれば、それが最速の一般的な方法であると確信していますあなたは見つけるでしょう）
于 2012-04-04T04:25:21.287 に答える
7
「最高のアルゴリズム」とはどういう意味ですか? ショートコードまたはファストコード？あなたのコードは非常にエレガントに見え、一定の実行時間があります。コードも非常に短いです。
しかし、コードサイズではなく速度が主な要因である場合、次の方法がより高速になる可能性があると思います。
static final int[] BIT_COUNT = { 0, 1, 1, ... 256 values with a bitsize of a byte ... };
static int bitCountOfByte( int value ){
return BIT_COUNT[ value & 0xFF ];
}
static int bitCountOfInt( int value ){
return bitCountOfByte( value )
+ bitCountOfByte( value >> 8 )
+ bitCountOfByte( value >> 16 )
+ bitCountOfByte( value >> 24 );
}
これは 64 ビット値では速くないと思いますが、32 ビット値では速くなる可能性があります。
于 2008-09-20T19:31:08.743 に答える
6
私は常にこれを競技プログラミングで使用していますが、書きやすく効率的です。
#include <bits/stdc++.h>
using namespace std;
int countOnes(int n) {
bitset<32> b(n);
return b.count();
}
于 2016-11-03T21:02:05.770 に答える
6
fortune ファイルの次の例が特に気に入っています。
#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define BX_(x) ((x) - (((x)>>1)&0x77777777)
- (((x)>>2)&0x33333333)
- (((x)>>3)&0x11111111))
可愛いから一番好き！
于 2008-09-23T01:29:53.683 に答える
6
入力サイズで分岐するバイト ビット カウントの事前計算されたテーブルを使用した高速な C# ソリューション。
public static class BitCount
{
public static uint GetSetBitsCount(uint n)
{
var counts = BYTE_BIT_COUNTS;
return n <= 0xff ? counts[n]
: n <= 0xffff ? counts[n & 0xff] + counts[n >> 8]
: n <= 0xffffff ? counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff]
: counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff] + counts[(n >> 24) & 0xff];
}
public static readonly uint[] BYTE_BIT_COUNTS =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};
}
于 2014-01-30T11:32:25.820 に答える
6
Java JDK1.5
Integer.bitCount(n);
ここで、n は 1 をカウントする数です。
もチェックして、
Integer.highestOneBit(n);
Integer.lowestOneBit(n);
Integer.numberOfLeadingZeros(n);
Integer.numberOfTrailingZeros(n);
//Beginning with the value 1, rotate left 16 times
n = 1;
for (int i = 0; i < 16; i++) {
n = Integer.rotateLeft(n, 1);
System.out.println(n);
}
于 2010-12-10T20:40:53.250 に答える
5
これは、任意のアーキテクチャで各アルゴリズムのベンチマークを実行できるポータブル モジュール ( ANSI-C ) です。
あなたのCPUは9ビットバイトですか？問題ありません :-) 現時点では、K&R アルゴリズムとバイト単位のルックアップ テーブルの 2 つのアルゴリズムが実装されています。ルックアップ テーブルは、K&R アルゴリズムより平均 3 倍高速です。誰かが「Hacker's Delight」アルゴリズムを移植可能にする方法を考え出すことができれば、遠慮なく追加してください。
#ifndef _BITCOUNT_H_
#define _BITCOUNT_H_
/* Return the Hamming Wieght of val, i.e. the number of 'on' bits. */
int bitcount( unsigned int );
/* List of available bitcount algorithms.
* onTheFly: Calculate the bitcount on demand.
*
* lookupTalbe: Uses a small lookup table to determine the bitcount. This
* method is on average 3 times as fast as onTheFly, but incurs a small
* upfront cost to initialize the lookup table on the first call.
*
* strategyCount is just a placeholder.
*/
enum strategy { onTheFly, lookupTable, strategyCount };
/* String represenations of the algorithm names */
extern const char *strategyNames[];
/* Choose which bitcount algorithm to use. */
void setStrategy( enum strategy );
#endif
.
#include <limits.h>
#include "bitcount.h"
/* The number of entries needed in the table is equal to the number of unique
* values a char can represent which is always UCHAR_MAX + 1*/
static unsigned char _bitCountTable[UCHAR_MAX + 1];
static unsigned int _lookupTableInitialized = 0;
static int _defaultBitCount( unsigned int val ) {
int count;
/* Starting with:
* 1100 - 1 == 1011, 1100 & 1011 == 1000
* 1000 - 1 == 0111, 1000 & 0111 == 0000
*/
for ( count = 0; val; ++count )
val &= val - 1;
return count;
}
/* Looks up each byte of the integer in a lookup table.
*
* The first time the function is called it initializes the lookup table.
*/
static int _tableBitCount( unsigned int val ) {
int bCount = 0;
if ( !_lookupTableInitialized ) {
unsigned int i;
for ( i = 0; i != UCHAR_MAX + 1; ++i )
_bitCountTable[i] =
( unsigned char )_defaultBitCount( i );
_lookupTableInitialized = 1;
}
for ( ; val; val >>= CHAR_BIT )
bCount += _bitCountTable[val & UCHAR_MAX];
return bCount;
}
static int ( *_bitcount ) ( unsigned int ) = _defaultBitCount;
const char *strategyNames[] = { "onTheFly", "lookupTable" };
void setStrategy( enum strategy s ) {
switch ( s ) {
case onTheFly:
_bitcount = _defaultBitCount;
break;
case lookupTable:
_bitcount = _tableBitCount;
break;
case strategyCount:
break;
}
}
/* Just a forwarding function which will call whichever version of the
* algorithm has been selected by the client
*/
int bitcount( unsigned int val ) {
return _bitcount( val );
}
#ifdef _BITCOUNT_EXE_
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* Use the same sequence of pseudo random numbers to benmark each Hamming
* Weight algorithm.
*/
void benchmark( int reps ) {
clock_t start, stop;
int i, j;
static const int iterations = 1000000;
for ( j = 0; j != strategyCount; ++j ) {
setStrategy( j );
srand( 257 );
start = clock( );
for ( i = 0; i != reps * iterations; ++i )
bitcount( rand( ) );
stop = clock( );
printf
( "\n\t%d psudoe-random integers using %s: %f seconds\n\n",
reps * iterations, strategyNames[j],
( double )( stop - start ) / CLOCKS_PER_SEC );
}
}
int main( void ) {
int option;
while ( 1 ) {
printf( "Menu Options\n"
"\t1.\tPrint the Hamming Weight of an Integer\n"
"\t2.\tBenchmark Hamming Weight implementations\n"
"\t3.\tExit ( or cntl-d )\n\n\t" );
if ( scanf( "%d", &option ) == EOF )
break;
switch ( option ) {
case 1:
printf( "Please enter the integer: " );
if ( scanf( "%d", &option ) != EOF )
printf
( "The Hamming Weight of %d ( 0x%X ) is %d\n\n",
option, option, bitcount( option ) );
break;
case 2:
printf
( "Please select number of reps ( in millions ): " );
if ( scanf( "%d", &option ) != EOF )
benchmark( option );
break;
case 3:
goto EXIT;
break;
default:
printf( "Invalid option\n" );
}
}
EXIT:
printf( "\n" );
return 0;
}
#endif
于 2011-03-29T08:04:29.253 に答える
4
32ビットかどうか？「コーディングのインタビューをクラックする」第 4 版演習 5.5 (第 5 章: ビット操作)を読んだ後、Java でこのメソッドを使用しました。最下位ビットが 1 増分countの場合、整数を右シフトします。
public static int bitCount( int n){
int count = 0;
for (int i=n; i!=0; i = i >> 1){
count += i & 1;
}
return count;
}
これは、どんなに高速であっても、0x33333333 定数のソリューションよりも直感的だと思います。「最適なアルゴリズム」の定義によって異なります。
于 2011-11-15T23:52:50.830 に答える
2
個人的に私はこれを使用します：
public static int myBitCount(long L){
int count = 0;
while (L != 0) {
count++;
L ^= L & -L;
}
return count;
}
于 2012-04-26T02:25:11.280 に答える
1
int bitcount(unsigned int n)
{
int count=0;
while(n)
{
count += n & 0x1u;
n >>= 1;
}
return count;
}
反復された「カウント」は、ビットの総数に比例して時間内に実行されます。while 条件のために、すべてのビットを単純にループし、わずかに早く終了します。1'S または設定されたビットがまばらで、最下位ビットの中にある場合に便利です。
于 2014-06-07T16:41:10.560 に答える
1
int countBits(int x)
{
int n = 0;
if (x) do n++;
while(x=x&(x-1));
return n;
}
またはまた：
int countBits(int x) { return (x)? 1+countBits(x&(x-1)): 0; }
于 2015-02-12T04:19:05.203 に答える
1
Java 8 または 9 では、単に呼び出すだけInteger.bitCountです。
于 2016-10-04T21:05:15.570 に答える
0
#!/user/local/bin/perl
$c=0x11BBBBAB;
$count=0;
$m=0x00000001;
for($i=0;$i<32;$i++)
{
$f=$c & $m;
if($f == 1)
{
$count++;
}
$c=$c >> 1;
}
printf("%d",$count);
ive done it through a perl script. the number taken is $c=0x11BBBBAB
B=3 1s
A=2 1s
so in total
1+1+3+3+3+2+3+3=19
于 2012-06-06T20:04:48.860 に答える
0
整数をバイナリ文字列に変換して数えるのはどうですか？
PHPソリューション：
substr_count( decbin($integer), '1' );
于 2016-02-04T11:45:31.550 に答える
0
参考になるかもしれないサンプルコードを以下に示します。
private static final int[] bitCountArr = new int[]{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
private static final int firstByteFF = 255;
public static final int getCountOfSetBits(int value){
int count = 0;
for(int i=0;i<4;i++){
if(value == 0) break;
count += bitCountArr[value & firstByteFF];
value >>>= 8;
}
return count;
}
于 2012-02-24T06:37:53.207 に答える
0
PHP で動作するものを次に示します (すべての PHP 整数は 32 ビット署名されているため、31 ビットです)。
function bits_population($nInteger)
{
$nPop=0;
while($nInteger)
{
$nInteger^=(1<<(floor(1+log($nInteger)/log(2))-1));
$nPop++;
}
return $nPop;
}
于 2012-02-24T14:16:47.773 に答える
0
少量のビットに対して適切に機能する単純な方法は、次のようになります (この例では 4 ビットの場合):
(i & 1) + (i & 2)/2 + (i & 4)/4 + (i & 8)/8
簡単な解決策として、少数のビットに対してこれを推奨する人はいますか?
于 2010-06-01T21:54:32.873 に答える
-1
あなたは次のようなことをすることができます：
int countSetBits(int n)
{
n=((n&0xAAAAAAAA)>>1) + (n&0x55555555);
n=((n&0xCCCCCCCC)>>2) + (n&0x33333333);
n=((n&0xF0F0F0F0)>>4) + (n&0x0F0F0F0F);
n=((n&0xFF00FF00)>>8) + (n&0x00FF00FF);
return n;
}
int main()
{
int n=10;
printf("Number of set bits: %d",countSetBits(n));
return 0;
}
参照してください：http：//ideone.com/JhwcX
動作は次のように説明できます。
まず、すべての偶数ビットが右にシフトされ、奇数ビットが追加されて、2つのグループのビット数がカウントされます。次に、2人のグループで作業し、次に4人のグループで作業します。
于 2012-06-21T13:34:47.647 に答える
-1
// How about the following:
public int CountBits(int value)
{
int count = 0;
while (value > 0)
{
if (value & 1)
count++;
value <<= 1;
}
return count;
}
于 2012-04-06T21:24:41.613 に答える
-2
次の関数を使用します。ベンチマークをチェックしていませんが、動作します。
int msb(int num)
{
int m = 0;
for (int i = 16; i > 0; i = i>>1)
{
// debug(i, num, m);
if(num>>i)
{
m += i;
num>>=i;
}
}
return m;
}
于 2013-05-29T09:16:30.363 に答える
-3
public class BinaryCounter {
private int N;
public BinaryCounter(int N) {
this.N = N;
}
public static void main(String[] args) {
BinaryCounter counter=new BinaryCounter(7);
System.out.println("Number of ones is "+ counter.count());
}
public int count(){
if(N<=0) return 0;
int counter=0;
int K = 0;
do{
K = biggestPowerOfTwoSmallerThan(N);
N = N-K;
counter++;
}while (N != 0);
return counter;
}
private int biggestPowerOfTwoSmallerThan(int N) {
if(N==1) return 1;
for(int i=0;i<N;i++){
if(Math.pow(2, i) > N){
int power = i-1;
return (int) Math.pow(2, power);
}
}
return 0;
}
}
于 2015-09-25T17:31:37.777 に答える