ちょっとわけあってpopcountを調べてた。
以前から、
ビットを数える・探すアルゴリズムを参考に
int numofbits5(long bits)
{
bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}
とかやってたわけです。この計算の意味は、
- 1行目で、2ビットずつを足しこみ2ビット単位で1が立っているビット数を計算
- 2行目は2ビット値×16個を、4ビット値×8個へreduction演算
- 3行目は4ビット値×8個を、8ビット値×4個へreduction演算
- 4行目は8ビット値×4個を、16ビット値×2個へreduction演算
- 5行目は16ビット値×2個を、32ビット値×1個へreduction演算
です。次に、
marisa-trie の PopCount を改良しましたを見ると、
explicit PopCount(UInt64 x) : value_() {
// 格好良いコードにするより，野暮ったいコードの方が速くなりました．
x = (x & 0x5555555555555555ULL) + ((x & 0xAAAAAAAAAAAAAAAAULL) >> 1);
x = (x & 0x3333333333333333ULL) + ((x & 0xCCCCCCCCCCCCCCCCULL) >> 2);
x = (x & 0x0F0F0F0F0F0F0F0FULL) + ((x & 0xF0F0F0F0F0F0F0F0ULL) >> 4);
// x += x << 8; x += x << 16; x += x << 32; とするより高速になりました．
x *= 0x0101010101010101ULL;
value_ = x;
}
と4行目5行目を最適化しています。
計算中の値は、4行目の段階で8ビット値になっており、64ビットのpopcountの最大値は64で8ビットに収まります。
そのため、8ビット値×8個を一気に8ビット値×1個へreduction演算できるなら、そのほうが良いわけです。
x *= 0x0101010101010101ULLは、
x = x << 56 + x << 48 + x << 40 + x << 32
x << 24 + x << 16 + x << 8 + x << 0;
を計算しているので、xの上位8ビットに求める値が入っています。
また、1行目は、
(x & 0x55555555) + (x >> 1 & 0x55555555)
= (x & 0x55555555) + (x >> 1 & 0x55555555) + (x >> 1 & 0x55555555) - (x >> 1 & 0x55555555)
= (x & 0x55555555) + (x & (0x55555555 << 1)) - (x >> 1 & 0x55555555)
= x - (x >> 1 & 0x55555555)
なので最適化でき、3行目も、計算結果の8ビット中の1の数が最大8で4ビットに収まり桁あふれしないので、
(x & 0x0f0f0f0f) + (x >> 4 & 0x0f0f0f0f)
= x + (x >> 4) & 0x0f0f0f0f
と最適化できます。最終的に以下のコードとなります。
int numofbits5(unsigned long bits)
{
bits = bits - (bits >> 1 & 0x55555555);
bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
bits = bits + (bits >> 4) & 0x0f0f0f0f;
bits = bits * 0x01010101;
return bits >> 24;
}
ここまで考えて、Google先生に聞くと、
既出だったｗ
うう、Blogger先生が勝手に&表記に変換する……。< pre > の中なのに。
