そこで、uint32 内の 1 のビット数 (または count mod 2) をカウントできる一連の卑劣な一連のビット操作があるかどうかを確認しようとしています。
「明白な」方法は次のようになります。
uint32 count_1_bits_mod_2(uint32 word) {
uint32 i, sum_mod_2;
for(i = 0; i < 32; i++)
sum_mod_2 ^= word;
word >>= 1;
ループを使用せずに適切な sum_mod_2 を取得する「卑劣な」方法はありますか?
ビットをカウントする最速の方法は、「マジック ナンバー」を使用することです。
unsigned int v = 0xCF31; // some number
v = v - ((v >> 1) & 0x55555555); // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp
unsigned int c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
これは 9 を出力します ( ideone へのリンク)。
これには、32 ビットの数値に対して 12 の操作が必要です。ルックアップ ベースの方法と同じ数ですが、ルックアップ テーブルは必要ありません。
「最良の」方法は、コードが実行されているCPUアーキテクチャによって異なる場合があります。たとえば、Nehalem/Barcelonaで始まるIntel/AMD CPUは、整数レジスタの1ビット数を計算する「popcnt」命令をサポートしているため、わずか2つの命令（popcntおよびビット単位のANDと1）で値を計算できます。あなたが求める。
かなり新しいバージョンのGCC（または同様のサポートを持つ別のコンパイラ）を使用している場合は、その__builtin_popcount（）関数を使用して、「-mpopcount」または「-msse4.2」コンパイルを使用して人口カウントを計算できます。指定されたフラグはpopcnt命令を使用します。詳細については、このリンクを参照してください。例えば：
uint32_t parity = __builtin_popcount(x) & 1;
最も速いのは CPU の popcnt 命令を使用したもので、2 番目に近いのは SSSE3 コードです。最速のポータブルはビットスライス方式で、ルックアップテーブルが続きます: http://www.dalkescientific.com/writings/diary/archive/2011/11/02/faster_popcount_update.html
すべての場合と同様に、負荷をベンチマークする必要があります。次に、遅すぎる場合は最適化します。
AMD Phenom II X2 550 の場合、gcc 4.7.1 (を使用g++ -O3 popcnt.cpp -o popcnt -mpopcnt -msse2):
Bitslice(7) 1462142 米国; cnt = 32500610 Bitslice(24) 1221985 米国; cnt = 32500610 Lauradoux 2347749 米国; cnt = 32500610 SSE2 8 ビット 790898 us; cnt = 32500610 SSE2 16 ビット 825568 us; cnt = 32500610 SSE2 32 ビット 864665 us; cnt = 32500610 16 ビット LUT 1236739 us; cnt = 32500610 8 ビット LUT 1951629 us; cnt = 32500610 gcc popcount 803173 us; cnt = 32500610 gcc popcountll 7678479 us; cnt = 32500610 FreeBSD バージョン 1 2802681 us; cnt = 32500610 FreeBSD バージョン 2 2167031 us; cnt = 32500610 ウィキペディア #2 4927947 cnt = 32500610 ウィキペディア #3 4212143 cnt = 32500610 HAKMEM 169/X11 3559245 米国; cnt = 32500610 ナイーブ 16182699 私たち; cnt = 32500610 Wegner/Kernigan 12115119 米国; cnt = 32500610 アンダーソン 61045764 米国; cnt = 32500610 8x シフトして 6712049 us を追加。cnt = 32500610 32x シフトして 6662200 us を追加。cnt = 32500610
Intel Core2 Duo E8400 の場合、gcc 4.7.1 (g++ -O3 popcnt.cpp -o popcnt -mssse3は-mpopcntこの CPU ではサポートされていません)
Bitslice(7) 1353007 米国; cnt = 32500610 Bitslice(24) 953044 米国; cnt = 32500610 Lauradoux 534697 米国; cnt = 32500610 SSE2 8 ビット 458277 us; cnt = 32500610 SSE2 16 ビット 555278 us; cnt = 32500610 SSE2 32 ビット 634897 us; cnt = 32500610 SSSE3 414542 米国; cnt = 32500610 16 ビット LUT 1208412 us; cnt = 32500610 8 ビット LUT 1400175 us; cnt = 32500610 gcc popcount 5428396 us; cnt = 32500610 gcc popcountll 2743358 us; cnt = 32500610 FreeBSD バージョン 1 3025944 us; cnt = 32500610 FreeBSD バージョン 2 2313264 us; cnt = 32500610 ウィキペディア #2 1570519 cnt = 32500610 ウィキペディア #3 1051828 cnt = 32500610 HAKMEM 169/X11 3982779 米国; cnt = 32500610 ナイーブ 20951420 私たち; cnt = 32500610 ウェグナー/カーニガン 13665630 米国; cnt = 32500610 アンダーソン 6771549 米国; cnt = 32500610 8x シフトして 14917323 us を追加。cnt = 32500610 32x シフトして 14494482 us を追加。cnt = 32500610
Bitslice メソッドは、一度に複数 (7 または 24) のマシン ワードをカウントする並列メカニズムであるため、汎用関数としてはわずかな使いやすさしかありません。http://dalkescientific.com/writings/diary/popcnt.cpp の後:
static inline int popcount_fbsd2(unsigned *buf, int n)
{
int cnt=0;
do {
unsigned v = *buf++;
v -= ((v >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
v = (v + (v >> 4)) & 0x0F0F0F0F;
v = (v * 0x01010101) >> 24;
cnt += v;
} while(--n);
return cnt;
}
static inline int merging2(const unsigned *data)
{
unsigned count1,count2,half1,half2;
count1=data[0];
count2=data[1];
half1=data[2]&0x55555555;
half2=(data[2]>>1)&0x55555555;
count1 = count1 - ((count1 >> 1) & 0x55555555);
count2 = count2 - ((count2 >> 1) & 0x55555555);
count1+=half1;
count2+=half2;
count1 = (count1 & 0x33333333) + ((count1 >> 2) & 0x33333333);
count2 = (count2 & 0x33333333) + ((count2 >> 2) & 0x33333333);
count1+=count2;
count1 = (count1&0x0F0F0F0F)+ ((count1 >> 4) & 0x0F0F0F0F);
count1 = count1 + (count1 >> 8);
count1 = count1 + (count1 >> 16);
return count1 & 0x000000FF;
}
static inline int merging3(const unsigned *data)
{
unsigned count1,count2,half1,half2,acc=0;
int i;
for(i=0;i<24;i+=3)
{
count1=data[i];
count2=data[i+1];
//w = data[i+2];
half1=data[i+2]&0x55555555;
half2=(data[i+2]>>1)&0x55555555;
count1 = count1 - ((count1 >> 1) & 0x55555555);
count2 = count2 - ((count2 >> 1) & 0x55555555);
count1+=half1;
count2+=half2;
count1 = (count1 & 0x33333333) + ((count1 >> 2) & 0x33333333);
count1 += (count2 & 0x33333333) + ((count2 >> 2) & 0x33333333);
acc += (count1 & 0x0F0F0F0F)+ ((count1>>4) &0x0F0F0F0F);
}
acc = (acc & 0x00FF00FF)+ ((acc>>8)&0x00FF00FF);
acc = acc + (acc >> 16);
return acc & 0x00000FFFF;
}
/* count 24 words at a time, then 3 at a time, then 1 at a time */
static inline int popcount_24words(unsigned *buf, int n) {
int cnt=0, i;
for (i=0; i<n-n%24; i+=24) {
cnt += merging3(buf+i);
}
for (;i<n-n%3; i+=3) {
cnt += merging2(buf+i);
}
cnt += popcount_fbsd2(buf+i, n-i);
return cnt;
}
count = 0;
while (word != 0) {
word = word & (word-1);
count++;
}
ステートメント
word = word & (word-1);
ワードの最下位 1 ビットをクリアします。最終的に、1 ビットが不足します。
これはかなり理解しやすく、非常に効率的だと思います。
x = some number;
x ^= (x >> 1); // parity of every bit pair now in bits 0, 2, 4, ...
x ^= (x >> 2); // parity of every 4 bits now in bits 0, 4, 8, ...
x ^= (x >> 4); // ...etc
x ^= (x >> 8);
x ^= (x >> 16); // parity of all 32 bits now in bit 0
parity = x & 1;
cnt = 0;
while (word != 0) {
word = word & (word-1);
cnt++;
これにより、詳細については 1 ビットを削除できます。http://pgrtutorials.blogspot.in/p/bit-manipulation.htmlを参照してください。
すべての結果を事前に計算し、単純な配列検索を行います。単純な「偶数または奇数を数える」ブール値の結果については、ビット配列を作成できます。