x86_64でpopcnt / tzcnt / lzcntする【ビット演算テクニック Advent Calendar 2016 5日目】

• これはビット演算テクニック Advent Calendar 2016 5日目の記事です

最初はもう少し別のことを書こうと思っていたのですが、時間がなくなってしまったので諦めました。みんな大好きpopcntの話をします。

popcnt (tzcnt / lzcnt) とは?

レジスタ内で1の立っているビットの数を数える命令です。

popcnt(0x00) == 0
popcnt(0x01) == 1
popcnt(0x55) == 4
popcnt(0xffffffff) == 32

といった具合です。最近の多くのプロセッサにはこれを計算する命令が実装されています。

ついで tzcnt / lzcnt も紹介しておきます。それぞれ、レジスタ内で LSb / MSb から連続する0の個数を数えます。以下に、64bitのレジスタに対し発行した場合の例を示します。

tzcnt(0x01) == 0
tzcnt(0x04) == 2
tzcnt(0x00) == 64
lzcnt(0x01) == 63
lzcnt(0x04) == 61
lzcnt(0x00) == 64

x86_64 で使う

これらの命令を x86_64 環境で使うにはどうすれば良いか、簡単にまとめます。

そもそもどう書けばこの命令に落ちるの?

gcc系の C / C++ 環境を想定します。それ以外の環境でビット演算をやりたいという人はいないと思うので... (MSVCの人はごめんなさい)

gccのintrinsicsを使う

いわゆる #include <x86intrin.h> するやつです。Intel Intrinsics Guide によると、_popcnt64、_mm_popcnt_u64、_tzcnt_u64、_mm_tzcnt_64 などがあるようです。_mmのプレフィクスつきの方は {gcc, clang} on {linux, mac} でコンパイルが通らないようで、msvcもしくはicc独自のものなのかもしれません。(確認はしていません) コンパイルする際に-march=nativeオプションを与えれば、その環境でそれらの命令が使える場合、いい感じにやってくれます。

#include <x86intrin.h>

uint64_t popcnt(uint64_t n)
{
    return(_popcnt64(n));
}

uint64_t tzcnt(uint64_t n)
{
    return(_tzcnt_u64(n));
}

uint64_t lzcnt(uint64_t n)
{
    return(_lzcnt_u64(n));
}

gccのinline assemblyを使う

uint64_t popcnt(uint64_t n)
{
    uint64_t res;
    __asm__( "popcntq %1, %0" : "=r"(res) : "r"(n) );
    return(res);
}

のように書く方法もあります。しかし、コンパイラの最適化が効かなくなるので可能なら避けた方が良さそうです。

自分の環境では使えないよ...😢

popcntはNehalem以降、tzcnt / lzcntはHaswell以降のプロセッサにしか実装されていません。これらの演算をサポート外のプロセッサ上でどうしても使いたい場合は、利用可能な演算の組み合わせに落とす方法を考えます。

popcnt

よく知られたテクニックを使いましょう。

uint64_t popcnt(uint64_t n)
{
    uint64_t c = 0;
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555);
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333);
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f);
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff);
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff);
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff);
    return(c);
}

tzcnt

popcnt命令が利用可能な場合は、

uint64_t tzcnt(uint64_t n)
{
    return(popcnt(~n & (n - 1)));
}

とするのが良さそうです。

また、x86_64 (x86) には、tzcntとほぼ同様の命令bsf (bit scan forward) が実装されています。tzcntとの違いは入力レジスタの値が0の場合の出力が未定義となっている点です。というわけでpopcnt命令すら利用できない場合は、

uint64_t tzcnt(uint64_t n)
{
    if(n == 0) {
        return(64);
    } else {
        int64_t res;
        __asm__( "bsfq %1, %0" : "=r"(res) : "r"(n) );
        return(res);
    }
}

とします。

lzcnt

tzcntと異なり、上手い演算でpopcntに帰着させることはできません。常にbsr (bit scan reverse) 命令に帰着します。

uint64_t lzcnt(uint64_t n)
{
    if(n == 0) {
        return(64);
    } else {
        int64_t res;
        __asm__( "bsrq %1, %0" : "=r"(res) : "r"(n) );
        return(63 - res);
    }
}

環境の差異を考えるのは面倒ですね...

ヘッダファイルにまとめました。 -march=nativeつきでご利用ください。

まとめ

• 最近のx86_64プロセッサでは、popcnt / tzcnt / lzcnt命令が実装されている。
• 使える場合は#include <x86intrin.h>と-march=nativeを組み合わせれば大体良い感じになる。
• サポートされていないプロセッサでは、ごにょごにょする。

明日はYSRKENさんの連珠の話だそうです。連珠ってなに...?