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

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  

うーむ。

おおいしつかさ

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