Population count

code:pseudo

ans = 0

for i in 0..word_size {

++ans

}

}

return ans

ビット列のうち、1が立っている場所の数を数える

CPU命令

x86 (POPCNT extension) POPCNT, (AVX512_POPCNTDQ) VPOPCNT(32bit*16, 64bit*8), (AVX512_BITARG) VPOPCNT (8bit*64, 16bit*32)

Arm (A32) VCNT(q) (8bit*8or16), (A64) CNT (8bit*8or16)

SIMDだと全体のpopcountではなくワードごとにpopcountを取ることが多いみたい？

ソフトウェア実装

code: c++

uint32_t popcount(uint32_t x) {

x = ((x >> 1) & 0x55555555) + (x & 0x55555555); // step 1

x = ((x >> 2) & 0x33333333) + (x & 0x33333333); // step 2

x = ((x >> 4) & 0x0f0f0f0f) + (x & 0x0f0f0f0f); // step 3

x = ((x >> 8) & 0x00ff00ff) + (x & 0x00ff00ff); // step 4

x = ((x >> 16) & 0x0000ffff) + (x & 0x0000ffff); // step 5

return x;

}

2^kビットごとのpopcountを持っていると、2^(k+1)ビットごとのpopcountはシフト、ビットマスク、加算で実現できる

これを再帰的に繰り返すことでワード全体のpopcountが求められる。

もう少し最適化すると、

code: c++

uint32_t popcount(uint32_t x) {

x = x - ((x >> 1) & 0x55555555); // step 1

x = ((x >> 2) & 0x33333333) + (x & 0x33333333); // step 2

x = ((x >> 4) + x) & 0x0f0f0f0f; // step 3

x = (x >> 8) + x; // step 4

x = ((x >> 16) + x) & 0x000000ff; // step 5

return x;

}

step1: ビット列xyは2*x+yなので、ここからxを引いてやればx+yになる。

これは1ビット右シフトしてからビットマスクでyのビットを消せばよい。

step3: 2^iビットのpopcountの最大値はi+1ビットあれば表現できる。

したがって、i+1 <= 2^iならば足し算が2^iビット以内に収まるため、ビットマスクをとってから加算をするのではなく、加算をした後にビットマスクを取れば十分である。

step 4,5: 32ビットのpopcountは8ビット以内に収まるため、最後にマスクを取ればよい

乗算を許せば最後の2stepは一度にできて、

code: c++

uint32_t popcount(uint32_t x) {

x = x - ((x >> 1) & 0x55555555);

x = ((x >> 2) & 0x33333333) + (x & 0x33333333);

x = ((x >> 4) + x) & 0x0f0f0f0f;

x = (x * 0x01010101) >> 24; // step 4,5

return x;

}

ハードウェア実装

ソフトウェア実装のうち、ビットマスクは不要で、加算器も2^iビットごとに用意すれば、その間で桁上げする必要はない。

後半の和のビット数も線形でしか増えない。

wallace tree的なことをすると遅延を減らせそうな気もする。詳しい人教えて！