32 ビット整数内の設定ビット数をカウントするにはどうすればよいですか?
https://stackoverflow.com/questions/109023
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
数字の 7 を表す 8 ビットは次のようになります。
00000111
3 つのビットが設定されます。
32 ビット整数の設定ビット数を決定するアルゴリズムとは何ですか?
解決
これは「」として知られています。ハミングウェイト'、'ポップカウント'、または'横加算'。
「最適な」アルゴリズムは、実際に使用している CPU と使用パターンによって異なります。
一部の CPU にはそれを実行する単一の組み込み命令があり、他の CPU にはビット ベクトルに作用する並列命令があります。並列命令 (x86 のような) popcnt, 、サポートされている CPU 上では、ほぼ確実に最速になります。他のアーキテクチャには、サイクルごとにビットをテストするマイクロコード化されたループを使用して実装された遅い命令が含まれている場合があります (要出典).
CPU に大規模なキャッシュがある場合、またはこれらの命令をタイトなループで多数実行している場合、事前に設定されたテーブル検索メソッドは非常に高速になります。ただし、CPU がメイン メモリからテーブルの一部をフェッチする必要がある「キャッシュ ミス」が発生するため、問題が発生する可能性があります。
バイトの大部分が 0 であるか、大部分が 1 であることがわかっている場合は、これらのシナリオに非常に効率的なアルゴリズムがあります。
非常に優れた汎用アルゴリズムは、「並列」または「可変精度 SWAR アルゴリズム」として知られる次のアルゴリズムだと思います。私はこれを C のような疑似言語で表現しましたが、特定の言語で機能するように調整する必要があるかもしれません (例:C++ では uint32_t を使用し、Java では >>> を使用します)。
int numberOfSetBits(int i)
{
// Java: use >>> instead of >>
// C or C++: use uint32_t
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
これは、これまでに説明したアルゴリズムの中で最も最悪の場合の動作が優れているため、使用パターンや投入される値に効率的に対処できます。
このビットごとの SWAR アルゴリズムは、SIMD を備えているが使用可能なポップカウント命令を持たない CPU での高速化のために、単一の整数レジスタではなく複数のベクトル要素で同時に実行されるように並列化できます。（例えば。Nehalem 以降だけでなく、任意の CPU で実行する必要がある x86-64 コード。)
ただし、ポップカウントにベクトル命令を使用する最良の方法は、通常、変数シャッフルを使用して、各バイトごとに一度に 4 ビットのテーブル ルックアップを並列に実行することです。(4 ビットは、ベクトル レジスタに保持される 16 エントリ テーブルをインデックスします)。
Intel CPU では、ハードウェア 64 ビットの Popcnt 命令は、 SSSE3 PSHUFB ビット並列実装 約 2 倍ですが、 コンパイラが正しく処理すれば. 。そうでなければ、SSE が大幅に先を行く可能性があります。新しいコンパイラ バージョンでは、 Popcnt の誤った依存関係 インテルの問題.
参考文献:
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)
他のヒント
コンパイラの組み込み関数も考慮してください。
たとえば、GNU コンパイラでは次のように使用できます。
int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);
最悪の場合、コンパイラは関数の呼び出しを生成します。最良の場合、コンパイラは同じジョブをより速く実行するために CPU 命令を発行します。
GCC 組み込み関数は複数のプラットフォームでも機能します。Popcount は x86 アーキテクチャで主流になるため、今すぐ組み込みを使い始めるのは理にかなっています。他のアーキテクチャは何年にもわたって人気があります。
x86 では、コンパイラーに、次のサポートを想定できることを伝えることができます。 popcnt との指示 -mpopcnt または -msse4.2 同じ世代に追加されたベクトル命令も有効にします。見る GCC x86 オプション. -march=nehalem （または -march= コードで想定して調整したい CPU は何でも構いません) が良い選択になる可能性があります。生成されたバイナリを古い CPU で実行すると、不正な命令フォルトが発生します。
バイナリをビルドするマシンに最適化するには、次を使用します。 -march=native (gcc、clang、または ICC を使用)。
MSVC は x86 の組み込みを提供します popcnt 命令, ただし、gcc とは異なり、実際にはハードウェア命令の組み込みであり、ハードウェアのサポートが必要です。
使用する std::bitset<>::count() 内蔵の代わりに
理論的には、ターゲット CPU のポップカウントを効率的に行う方法を知っているコンパイラーは、ISO C++ を通じてその機能を公開する必要があります。 std::bitset<>. 。実際には、ターゲット CPU によっては、ビットハック AND/shift/ADD を使用した方が良い場合があります。
ハードウェア ポップカウントがオプションの拡張子であるターゲット アーキテクチャ (x86 など) の場合、すべてのコンパイラに std::bitset 利用可能な場合はそれを利用します。たとえば、MSVC には有効にする方法がありません。 popcnt コンパイル時にサポートし、常に使用します テーブルルックアップ, 、 でもで /Ox /arch:AVX (これは SSE4.2 を意味しますが、技術的には SSE4.2 用の別の機能ビットがあります。 popcnt.)
しかし、少なくともどこでも動作するポータブルなものが得られ、適切なターゲット オプションを備えた 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();
}
見る gcc、clang、icc、および MSVC の asm Godbolt コンパイラ エクスプローラー上で。
x86-64 gcc -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
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
パワーPC64 gcc -O3 -std=gnu++11 放出します（ int 引数バージョン):
rldicl 3,3,0,32 # zero-extend from 32 to 64-bit
popcntd 3,3 # popcount
blr
このソースは x86 固有でも GNU 固有でもありませんが、gcc/clang/icc を使用した場合にのみ x86 用に適切にコンパイルされます。
また、単一命令ポップカウントを持たないアーキテクチャに対する gcc のフォールバックは、一度にバイト単位のテーブル ルックアップであることにも注意してください。これは素晴らしいことではありません たとえばARMの場合.
私の意見では、「最良の」ソリューションは、大量のコメントなしで別のプログラマ (または 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);
}
ただし、これらは特定のデータ型のサイズに依存しているため、移植性は高くありません。ただし、パフォーマンスの最適化の多くは移植可能ではないため、それは問題ではない可能性があります。移植性が必要な場合は、読みやすいソリューションにこだわると思います。
『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 程度の命令 (アーキテクチャに依存) で実行され、分岐はありません。
ハッカーの喜び は 楽しい！強くお勧めします。
ルックアップ テーブルを使用せずに、最も早い方法だと思います。 ポップカウント—以下です。わずか 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 つのグループとしてカウントします。これまでの操作のおかげで、すべてのニブルに設定されたビット数が含まれていることはわかっています。例を見てみましょう。バイトがあるとします 0b01000010. 。これは、最初のニブルには 4 ビットが設定され、2 番目のニブルには 2 ビットが設定されていることを意味します。次に、それらのニブルを一緒に追加します。
0b01000010 + 0b01000000
最初のニブルのバイト内の設定ビット数がわかります。 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 言葉。
Java を使用している場合は、組み込みメソッド Integer.bitCount そうします。
私は退屈して、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 ビットずつのアプローチを使用してください。
ビットをいじるアプローチを使用する状況を考えるのは困難です。
編集：同様の結果 ここ.
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)
+-------------------------------+
これは、マイクロアーキテクチャを知るのに役立つ質問の 1 つです。C++ インラインを使用して -O3 でコンパイルされた gcc 4.3.3 で 2 つのバリアントの時間を測定し、関数呼び出しのオーバーヘッドを排除し、10 億回の反復を実行しました。コンパイラーが重要なものを削除しないようにすべてのカウントの累計を保持し、タイミングには rdtsc を使用しました (クロックサイクルは正確です）。
inline int pop2(unsigned x, unsigned 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);
return (x+y) & 0x000000FF;
}
未修正の Hacker's Delight には 12.2 ギガサイクルかかりました。私の並列バージョン (2 倍のビット数をカウント) は 13.0 ギガサイクルで実行されます。2.4GHz Core Duo では両方を合わせて合計 10.5 秒が経過しました。25 ギガサイクル = このクロック周波数では 10 秒強なので、タイミングは正しいと確信しています。
これは命令の依存関係チェーンに関係しており、このアルゴリズムにとっては非常に悪いものです。64 ビット レジスタのペアを使用すると、速度を再びほぼ 2 倍にすることができました。実際、私が賢くて x+y をもう少し早く追加できれば、シフトをいくつか削ることができました。いくつかの小さな調整を加えた 64 ビット バージョンでは、ほぼ均等になりますが、ビット数は再び 2 倍になります。
128 ビット SIMD レジスタ、さらに 2 の係数、および SSE 命令セットには、多くの場合、賢いショートカットもあります。
コードが特に透明である必要があるわけではありません。インターフェイスはシンプルで、アルゴリズムはオンラインのさまざまな場所で参照でき、包括的な単体テストに適しています。これに遭遇したプログラマーは、何かを学べるかもしれません。これらのビット操作はマシン レベルでは非常に自然です。
OK、微調整した 64 ビット バージョンをベンチに置くことにしました。この場合、 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) & 0x3333333333333333);
y = (y & 0x3333333333333333) + ((y >> 2) & 0x3333333333333333);
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);
return x & 0xFF;
}
それはほぼ正しいようです（ただし、注意深くテストしているわけではありません）。現在、タイミングは 10.70 ギガサイクル / 14.1 ギガサイクルになります。この後の数値は合計 1,280 億ビットで、このマシンでの経過時間は 5.9 秒に相当します。非並列バージョンでは、64 ビット モードで実行しており、32 ビット レジスタよりも 64 ビット レジスタの方がわずかに優れているため、速度が少し向上します。
ここでもう少し OOO パイプラインが必要かどうかを見てみましょう。これはもう少し複雑なので、実際に少しテストしてみました。各項単独の合計は 64、すべての合計は 256 になります。
inline int pop4(unsigned long x, unsigned long y,
unsigned long u, unsigned long v)
{
enum { 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);
return x & 0x000001FF;
}
一瞬興奮しましたが、一部のテストでは inline キーワードを使用していないにもかかわらず、gcc が -O3 を使用してインライン トリックを実行していることがわかりました。gcc にトリックを実行させると、pop4() を 10 億回呼び出すと 12.56 ギガサイクルかかりますが、引数を定数式として折りたたんでいると判断しました。より現実的な数値は、さらに 30% 高速化するには 19.6gc と思われます。私のテストループは次のようになり、各引数が gcc のトリックを阻止するのに十分な違いがあることを確認します。
hitime b4 = rdtsc();
for (unsigned long i = 10L * 1000*1000*1000; i < 11L * 1000*1000*1000; ++i)
sum += pop4 (i, i^1, ~i, i|1);
hitime e4 = rdtsc();
合計 2,560 億ビットが 8.17 秒経過しました。16 ビット テーブル ルックアップのベンチマークでは、3,200 万ビットで 1.02 秒になります。他のベンチではクロック速度が示されていないため、直接比較することはできませんが、64KB テーブル エディションから鼻水を叩き出したように見えます。これは、そもそも L1 キャッシュの悲劇的な使用法です。
アップデート：そこで、さらに 4 つの重複行を追加して、pop6() を作成することにしました。22.8gc になり、9.5 秒の経過で合計 3,840 億ビットになりました。つまり、320 億ビットの場合、800 ミリ秒でさらに 20% になります。
なぜ反復的に 2 で割らないのでしょうか?
count = 0
while n > 0
if (n % 2) == 1
count += 1
n /= 2
これが最速ではないことには同意しますが、「最高」というのはやや曖昧です。ただし、「最高」には明確さの要素が必要だと私は主張します。
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 倍にします。
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;
}
これは最速の解決策でも最善の解決策でもありませんが、私なりに同じ疑問を見つけて、考え続けました。問題を数学的な側面から取得してグラフを描くと、それが周期的な部分を持つ関数であることがわかり、周期間の違いに気づくと、このようにできることについに気づきました...それでは、どうぞ:
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);
}
}
これは次の方法で実行できます O(k), 、 どこ k は設定されたビット数です。
int NumberOfSetBits(int n)
{
int count = 0;
while (n){
++ count;
n = (n - 1) & n;
}
return count;
}
探している関数は、2 進数の「横方向の合計」または「母数」と呼ばれることがよくあります。Knuth は、これについて pre-Fascicle 1A、pp11-12 で議論しています (ただし、第 2 巻、4.6.3-(7) に簡単な参照があります)。
の 古典の軌跡 これは、Peter Wegner の記事「バイナリ コンピュータで 1 を数えるテクニック」です。 ACM の通信, 、第 3 巻 (1960 年) 第 5 号、322 ページ. 。彼はそこで 2 つの異なるアルゴリズムを提供しています。1 つは「疎」であると予想される (つまり、1 の数が少ない) 数値に最適化されたもので、もう 1 つはその逆の場合に最適化されたものです。
いくつかの未解決の質問:-
- 数値が負の場合はどうなりますか?
- 数値が 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;
}
完全な参照については、以下を参照してください。
private int get_bits_set(int v)
{
int c; // c accumulates the total bits set in v
for (c = 0; v>0; c++)
{
v &= v - 1; // clear the least significant bit set
}
return c;
}
私は思います ブライアン・カーニハンの 方法も役立ちます...設定されたビットの数だけ反復が行われます。したがって、上位ビットのみが設定された 32 ビット ワードがある場合、そのワードはループを 1 回だけ通過します。
int countSetBits(unsigned int n) {
unsigned int n; // count the number of bits set in n
unsigned int c; // c accumulates the total bits set in n
for (c=0;n>0;n=n&(n-1)) c++;
return c;
}
1988 年に発行された C プログラミング言語第 2 版。(ブライアン W.カーニハンとデニス M.Ritchie) は、演習 2-9 でこれについて言及しています。2006 年 4 月 19 日、Don Knuth は私に、この方法は「CACM 3 (1960), 322 で Peter Wegner によって最初に発表されたものである」と指摘しました。(これもデリック・レーマーによって独自に発見され、1964 年にベッケンバックによって編集された本で出版されました。)
より直感的な以下のコードを使用します。
int countSetBits(int n) {
return !n ? 0 : 1 + countSetBits(n & (n-1));
}
ロジック:n & (n-1) は、n の最後に設定されたビットをリセットします。
追伸：興味深い解決策ではありますが、これが O(1) の解決策ではないことは承知しています。
「最良のアルゴリズム」とは何を意味しますか?ショートコードですか、それともファストコードですか?コードは非常にエレガントに見え、実行時間は一定です。コードも非常に短いです。
しかし、コードサイズではなく速度が主な要因である場合は、次の方が高速になると思います。
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 ビット値では高速になる可能性があります。
私は 1990 年頃に RISC マシン用の高速ビットカウント マクロを作成しました。高度な算術演算 (乗算、除算、%)、メモリ フェッチ (遅すぎる)、分岐 (遅すぎる) は使用しませんが、CPU に 32 ビット バレル シフタがあることを前提としています (つまり >> 1と >> 32 は同じ量のサイクルを要します。) 小さな定数 (6、12、24 など) はレジスタにロードするのにコストがかからないか、一時的に保存されて何度も再利用されることを前提としています。
これらの仮定により、ほとんどの RISC マシンでは約 16 サイクル/命令で 32 ビットをカウントします。加数の数を半分にするには少なくとも 3 つの命令 (マスク、シフト、演算子) が必要と思われるため、15 命令/サイクルはサイクルまたは命令の数の下限に近いことに注意してください。したがって、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
したがって、上記の 1 列目 (A) を右に 1 ビットシフトし、AB から減算すると、出力 (CD) が得られます。3 ビットへの拡張も同様です。必要に応じて、上記のような 8 行のブール値テーブルを使用して確認できます。
- ドン・ギリース
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++ コンパイラで動作し、ビット数に定数値が使用されている場合は基本的にループを展開するだけです。 (言い換えれば、これが最も速い一般的な方法であると確信しています)
私は、フォーチュン ファイルの次の例が特に気に入っています。
#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define BX_(x) ((x) - (((x)>>1)&0x77777777)
- (((x)>>2)&0x33333333)
- (((x)>>3)&0x11111111))
とても綺麗なので一番好きです！
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);
}
SIMD 命令 (SSSE3 と AVX2) を使用して配列内のビット数をカウントする実装を見つけました。__popcnt64 組み込み関数を使用する場合よりも 2 ～ 2.5 倍のパフォーマンスが向上します。
SSSE3のバージョン：
#include <smmintrin.h>
#include <stdint.h>
const __m128i Z = _mm_set1_epi8(0x0);
const __m128i F = _mm_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m128i T = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
uint64_t BitCount(const uint8_t * src, size_t size)
{
__m128i _sum = _mm128_setzero_si128();
for (size_t i = 0; i < size; i += 16)
{
//load 16-byte vector
__m128i _src = _mm_loadu_si128((__m128i*)(src + i));
//get low 4 bit for every byte in vector
__m128i lo = _mm_and_si128(_src, F);
//sum precalculated value from T
_sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, lo)));
//get high 4 bit for every byte in vector
__m128i hi = _mm_and_si128(_mm_srli_epi16(_src, 4), F);
//sum precalculated value from T
_sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, hi)));
}
uint64_t sum[2];
_mm_storeu_si128((__m128i*)sum, _sum);
return sum[0] + sum[1];
}
AVX2バージョン：
#include <immintrin.h>
#include <stdint.h>
const __m256i Z = _mm256_set1_epi8(0x0);
const __m256i F = _mm256_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m256i T = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
uint64_t BitCount(const uint8_t * src, size_t size)
{
__m256i _sum = _mm256_setzero_si256();
for (size_t i = 0; i < size; i += 32)
{
//load 32-byte vector
__m256i _src = _mm256_loadu_si256((__m256i*)(src + i));
//get low 4 bit for every byte in vector
__m256i lo = _mm256_and_si256(_src, F);
//sum precalculated value from T
_sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, lo)));
//get high 4 bit for every byte in vector
__m256i hi = _mm256_and_si256(_mm256_srli_epi16(_src, 4), F);
//sum precalculated value from T
_sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, hi)));
}
uint64_t sum[4];
_mm256_storeu_si256((__m256i*)sum, _sum);
return sum[0] + sum[1] + sum[2] + sum[3];
}
私は競技プログラミングでこれを常に使用していますが、記述が簡単で効率的です。
#include <bits/stdc++.h>
using namespace std;
int countOnes(int n) {
bitset<32> b(n);
return b.count();
}
設定されたビットをカウントするアルゴリズムは多数あります。でも、速いのが一番良いと思います！詳細は次のページで確認できます。
私はこれをお勧めします:
64 ビット命令を使用した 14、24、または 32 ビット ワードに設定されたビットのカウント
unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
// option 1, for at most 14-bit values in v:
c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;
// option 2, for at most 24-bit values in v:
c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL)
% 0x1f;
// option 3, for at most 32-bit values in v:
c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) %
0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
この方法を効率的に行うには、モジュラス除算が高速な 64 ビット CPU が必要です。最初のオプションでは 3 つの操作のみが必要です。2 番目のオプションには 10 がかかります。3 番目のオプションには 15 が必要です。
入力サイズに応じて分岐する、事前に計算されたバイト ビット数のテーブルを使用した高速 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
};
}
これは、任意のアーキテクチャ上で各アルゴリズムのベンチマークを実行できるポータブル モジュール ( 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
32ビットかどうか？「」を読んだ後、Javaでこのメソッドを思いつきました。コーディング面接を突破する「第 4 版演習 5.5 (第 5 章:ビット操作)。最下位ビットが 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 を使用するソリューションよりも直感的だと思います。それは「最良のアルゴリズム」の定義によって異なります。
