ビットカウントアルゴリズムの時間を計測してみた

Tsukasa OISHI

32ビットの2進数の中に存在する1の数をいかにして数えるか。というビットカウントの問題が 「ビューティフルコード (THEORY/IN/PRACTICE)」に載っています。あきらかに分割統治法が速いというのは予測がつくのですが(O(log n)だから)、実際に速度を計測してみました。

int main(void) {
    unsigned int base = 0;
    for (base = 0; base < 33554432; base++) {
        count(base);
    }
    return 0;
}

このcount関数をそれぞれのパターンで変えて計測します。

1.愚直にフルループ
まっさきに思いつく素直な方法。当然、遅いです。

unsigned int count(unsigned int x) {
    int i;
    int pop = 0;
    for (i = 0; i < 32; i++) {
        if (x & 1) pop = pop + 1;
        x = x >> 1;
    }
    return pop;
}

計測結果

/a.out  5.10s user 0.01s system 100% cpu 5.110 total

2.ループカウントをやめる
ループカウントという無駄な処理をやめて、さらに上位の0ビット分はループしません。

unsigned int count(unsigned int x) {
    int pop = 0;
    while(x) {
        pop = pop + (x & 1);
        x = x >> 1;
    }
    return pop;
}

計測結果

./a.out  2.69s user 0.00s system 99% cpu 2.700 total

3.ビットが立っている数だけループする
x & (x-1)が、xの最下位の1ビットを0にした数になることを利用します。

unsigned int count(unsigned int x) {
    int pop = 0;
    while(x) {
        pop = pop + 1;
        x = x & (x - 1);
    }
    return pop;
}

計測結果

./a.out  1.73s user 0.01s system 99% cpu 1.740 total

4.分割統治法を使う
シンプルに2ビットずつ16の部分に分割して並列処理的にカウントする。

unsigned int count(unsigned int x) {
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0f0f0f0f;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}

計測結果

./a.out  0.48s user 0.00s system 100% cpu 0.480 total

分割統治法の圧勝ですね。ビューティフルコードにはもうひとつ、HAKMEMメモ第169項のアルゴリズムが載っていたのだけど、これがいまひとつまだ理解できていません。頭が悪くなってきていることを実感する今日この頃です。

unsigned int count(unsigned int x) {
    unsigned int n;
    n = (x >> 1) & 033333333333;
    x = x - n;
    n = (n >> 1) & 033333333333;
    x = x - n;
    x = (x + (x >> 3)) & 030707070707;
    return x % 63;
}

計測結果

./a.out  0.49s user 0.01s system 99% cpu 0.500 total

うーむ。