Counting 1 bits.

Go 標準ライブラリの中に符号なし整数をビット列と見たとき、 1 のビットを数える関数がある。この実装がなかなか膝打ちのアイデアで面白い。なおここで紹介するアイデアは "Hacker's Delight" 第5章に詳しく書かれている。

例

以下の 16 bit の数を考える。

1 の数は 8 個ある。 数え上げのナイーブな実装として、 16 回ループを回し 1 のビットを見つけたらカウンタをインクリメントすることを思いつく。 これだと計算量は O(n)となる。 しかし、分割統治法を使うことで O(log(n)) にすることができる。すごい。

分割統治法

肝となる考えは「大きな問題を部分的な問題へ分割し、部分問題の結果をもとに大きな問題を解決する」ということだ。 16 個のビットを一度に計算するのではなく、より小さいビット幅で計算することを考える。

再び例にもどる。

はじめに 2 ビット幅ずつ見てみよう。 見やすいよう下図のように 7 個の仕切りを追加する。

仕切りにより 8 個の 2 ビットのペアが出来た。 仕切られた空間をここでは 部屋 と呼ぶことにする。つまり上図では 8 個の 2 ビット幅の部屋がある。

次に各部屋ごとにビットの数を計算しよう。各部屋の計算結果を 2 進数で格納すると下図になる。

（左から 1、2、3 つ目の部屋にはそれぞれ 1 個、0 個、2 個の 1 があることを表す）

同様に 4 ビット幅、8 ビット幅、16 ビット幅と、ビット幅を倍にして 1 の個数を求め続ける。これらの操作により下図のようになる。

最後部屋を見ると求めたかった 1 の個数 0b1000、つまり 8 が得られた。

実装

例えば 2つの 2 ビット幅の部屋から、4 ビット幅の部屋を求めることを考える。 これは左の部屋を右に 2 ビットシフトし右の部屋の値と足し合わせれば良い。

実装上の注意として、不要な値を無視するために 00110011 ... のビットマスクを使用する。

以下のコードはGo標準ライブラリにある、64ビットの符号なし整数の 1 の数を数える関数 OnesCount64 である。 （一部簡略化した形で引用した。）

const m0 = 0x5555555555555555 // 01010101 ...
const m1 = 0x3333333333333333 // 00110011 ...
const m2 = 0x0f0f0f0f0f0f0f0f // 00001111 ...

func OnesCount64(x uint64) int {
    x = x>>1&m0 + x&m0
    x = x>>2&m1 + x&m1
    x = (x>>4 + x) & m2
    x += x >> 8
    x += x >> 16
    x += x >> 32
    return int(x) & (1<<7 - 1)
}

ここまでくれば関数の各行から、ビットの幅を倍にして部屋の値を求めている操作が想像できるだろう。 なお標準ライブラリのコードでは 8 ビットシフトからマスクを取らない。 これは uint64 の 1 の数は高々 64 = 2⁶ 個 であり、最終行の 1<<7-1 のマスクで 7 ビット目以降は無視できるからである。

参考資料

• Go 標準ライブラリ
• Hacker's Delight