popcount

ちょっとわけあって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 > の中なのに。