ビット演算>ビットカウント

条件分岐使わないmax祭りが収まったみたいなので、通常進行に戻って、ビット演算の記事を淡々と書いていこう。
で、今回はビットカウントですよ。

ビットカウントは、与えられた整数を2進数表記した時の1の数を返すものだ。

bitCount(0) = 0
bitCount(1) = bitCount(2) = bitCount(4) = … bitCount(0x80000000) = 1
bitCount(0b1010) = 2
bitCount(0b1111) = 4

という感じだ。

さて、読者はこの int bitCount(unsigned int bits) を何通りの方法で記述できるだろうか?
なお、unsigned int は長いので、以下では typedef unsigned int uint; が定義済みとしてコードを記述する。

ループとマスクを使う方法

int bitCount(uint bits) {
    int cnt = 0;
    for(uint mask = 1; mask != 0; mask<<=1) {
        if( (bits & mask) != 0 )
            ++cnt;
    }
    return cnt;
}

上記コードは、ずっと前に紹介済みだ。
ビット判定をするマスクを 1 から 0x80000000 まで左シフトしながら回し、論理積演算によりビットが1であればカウンターを+1している。
基本の基本なので理解していない人はもう一度基礎を勉強しなおそう。

 if 文無しで、ループを使う方法

int bitCount(uint bits) {
    int cnt = 0;
    for(; bits != 0; bits>>=1) {
        cnt += bits & 1;
    }
    return cnt;
}

今度のコードは前節のものに似ていて、ビット数分ループをするのは同じだが、論理積を行うマスクは 1 固定にし、その代わり引数の方を右シフトしている。論理積の結果は 0 or 1 なので、それをそのままカウンターに足し込んでいるので、if 文を使っていない。

前節の方法は bits が符号付きでも大丈夫だが、この方法は unsigned でないとダメなので、そこんとこは注意して欲しい。

ひとつずつビットを落としていく方法

int bitCount(uint bits) {
    int cnt = 0;
    while( bits != 0 ) {
        ++cnt;
        bits &= bits - 1;       // 一番右の1を0にする
    }
    return cnt;
}

おもしろいことに、bits & bits – 1 を計算すると、2進数表記で一番右の1が0になる(0bxx..x100..0 → 0xbxx..x000..0)。例:0xff → 0xfe, 0x58 → 0x50
1を引くと 0bxx..x100..0 → 0xbxx..x011..1 となり、一番右の1から右のビットが反転する。
X & X = x, x & ~X = 0 という性質があるために、一番右の1が0になるとういわけだ。
ご理解いただけたであろうか?

分割統治法を使った O(Log2 N) な方法

int bitCount(uint bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);    //  2bitごとに計算
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);    //  4bitごとに計算
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);    //  8bitごとに計算
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);    //  16ビットごとに計算   
    return (bits & 0x0000ffff) + (bits >> 16);    //  32ビット分を計算   
}

今度は、いかにもビット演算を使った、という方法。

この方法はビット順序反転のところでも出てきたテクニックとある意味いっしょだ。
処理を2ビットごと、4ビットごと、8ビットごと、16ビットごと、というように処理ビット数を倍々にしていく。
ループで処理を行うとビット数に比例した処理回数が必要だが、この方法なら Log2 N に抑えることが出来る。
分割統治法とも呼ばれる。

 8ビット毎にテーブルを引く方法

int bitCount(uint bits) {
    static int table[256] = {0};
    if( table[1] == 0 ) {
        for (int i = 0; i < 256; ++i) {
             table[i] = bitCount(i);
         }
     }
     return table[bits&0xff] +
                table[(bits>>8)&0xff] +
                table[(bits>>16)&0xff] +
                table[(bits>>24)&0xff];
}

最後に8ビットごとにビットカウントのテーブルを作り、それを引くという方法も書いておく。
テーブルはあらかじめ作っておいてもいいのだが、それが面倒なので、static な配列とし、最初に呼ばれた時に他の関数を利用して初期化するようにした。

 演習問題:

  1. 本稿で紹介したコードが正しく動作することを確認しなさい。
  2. 本稿で紹介した以外の方法を考えなさい。