ビットカウントとは
整数を二進数表示した時、0と1の組み合わせになります。
例えば、十進数の 21 を2進数表示した場合、 0001 0101 のようになります。
この時、 0001 0101 に含まれる1の数を数えることをビットカウントと言います。
0001 0101 の場合、立っているビット数は 3 ですね。
なんてことなさそうな計算ですが、実は、超高速なアルゴリズムがあります。
今回は、このアルゴリズムに触れ、感動した私がそれを解説してみることにします。
ビットカウントのアルゴリズム
チェスや将棋、オセロのようなボードゲームのAIでは、盤面をBitboardというバイナリで表現することが多いです。
例えば、ある列の駒の数を数える場合、その列に対応するビット列を取り出し、立っているビット数を取得する必要があります。
強いAIを作るためには、高速な計算が必要となります。
全体のビット数分のループを回さずに、少ない手数でビットカウントできるアルゴリズムがあれば嬉しいですね。
英語では、 population countとかpopcountと呼ばれる有名な問題の一つで、非常に効率的なアルゴリズムが見つかっています(Wiki 英語版: Hamming_weight)。
例えば、将棋ソフト強豪として有名な Aperyでも高速なアルゴリズムが使われています (ソースコード) 。
この記事でやりたいこと
以前、Aperyのソースコードを読んだ時に popcount のアルゴリズムを知り、感動しました。
この記事では、Pythonで実際に popcount アルゴリズムを実装した上で、その中身をできるだけ詳しく解説していきます。
読んだ人に同じように感動してもらおう、というのがこの記事の目的です！
Pythonを使った理由
超高速なアルゴリズムをわざわざ遅いスクリプト言語であるPythonで実装することに違和感がある人もいるかもしれません。
今回は、アルゴリズムの理解に焦点を当てており、計算速度については気にしていません。計算速度の限界に挑戦したい方は、このアルゴリズムを知った後、C++などの高速な言語で実装してみてください。
前置きはいいから実装見せてよ
popcountを実装
def popcount(x):
'''xの立っているビット数をカウントする関数
(xは64bit整数)'''
# 2bitごとの組に分け、立っているビット数を2bitで表現する
x = x - ((x >> 1) & 0x5555555555555555)
# 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
x = x + (x >> 8) # 16bitごと
x = x + (x >> 16) # 32bitごと
x = x + (x >> 32) # 64bitごと = 全部の合計
return x & 0x0000007f
計算例
popcount(0b0) # -> 0
popcount(0b1) # -> 1
popcount(0b111) # -> 3
popcount(0b1010111010010101) # -> 9
補足：Pythonでのビット演算や数値表現
Pythonでも他の言語と同様に、右シフト >> や、AND演算 & などが使えます。
数値を16進数表示で定義したいときは、 0xa7 のように 0x をつけます。
2進数の場合は 0b101 のように 0b をつけます。
また、Pythonには組み込み関数で整数の表現方法を簡単に変えることができます。
整数を整数を2進数表示するときは bin(x) 、 16進数表示するときは hex(x) が使えます。
これらの出力は、 "0x2f" のような文字列になります。
popcountアルゴリズムの解説
理解するためのポイント
- 16進数を2進数に置き換えてみる
- 64bit整数をそのまま扱うのではなく、2bit整数、4bit整数のように分けて捉える
- ビット数を数えるのは実質一行目のみでやっているので、ここで何やってるかを知る
アルゴリズムの流れ
- 立っているビット数を計算したい64bit整数を32組の2bit整数にわける
- その2bit整数自体を、立っているビット数を表す2bit整数に変換する
- 立っているビット数が32組分できる
- それらを合計していき、最終的に64bit整数にする
ちなみに、64bitをループで回してビットカウントした場合、どんなに効率的にやっても10倍近く遅くなってしまいます。
1行目
x = x - ((x >> 1) & 0x5555555555555555)
この操作は、64bit整数を32組の2bit整数に分けるという考え方を用いています。
2bit整数に適用してみる
よりシンプルな例を見てみるのが良いでしょう。
2bit整数の場合の計算例は次のようになります。表の数値は 2進数表示です。
x |
x >> 1 |
(x >> 1) & 0b01 |
x - ((x >> 1) & 0b01) |
←の10進数表示 |
|---|---|---|---|---|
| 00 | 00 | 00 | 00 | 0 |
| 01 | 00 | 00 | 01 | 1 |
| 10 | 01 | 01 | 01 | 1 |
| 11 | 01 | 01 | 10 | 2 |
上の表を見ると分かるように、2bit整数の立っているビット数を計算できています。
64bit整数の場合、2bit整数でやったことと同様のことを32組に対して同時に行います。
この操作がまさに以下のように表現できます。
x = x - ((x >> 1) & 0x5555555555555555)
つまり、popcountの一行目がやっていることは、
64bit整数を2bitずつの組にわけ、その組の立っているビット数をその2bitで表現している
ということになります。
2bitごとに立っているビット数が求められたので、あとはそれを合計すればpopcountできることになります。
実は、これ以降の行では、32組の2bit整数を合計する演算をするだけです。
（注） 0x555... って何？
16進数の 0x5 は、2進数表示すると、 0b0101 になります。
0x5555555555555555 は16進数の5が16個並んでいます。
これは、2進数だと 0101010101... が合計64個並ぶものと等しくなります。
(x >> 1) は、xのビットを全体に右に１ビットずらしたものなので、
(x >> 1) & 0x5555555555555555
は、x >> 1 の偶数番目(2,4,6...番目)のみを残す演算になります。
つまり、この演算は xの奇数番目(1,3,5...番目)のビットのみを抜き出し、右に一つずらしたもの を計算していることにほかなりません。
2行目
x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
0x3 は2進数表示すると、 0b0011 です。
察しの良い方は気付かれたかもしれないですが、今度は4bit整数の組に分けます。
第一項では、4bit整数のうち、下位2bitのみを取り出しています。
第二項では、4bit整数のうち、上位2bitのみを取り出し、下位2bitに持ってきています。
合計すれば、もともと4bitで立っていたビット数の合計が4bit整数の値になりますね。
1行目で求めた2bit整数は最大2となるものでしたので、2行目では最大4になります。
4bit整数の下位３ビットで立っているビット数が表現できます。
3行目
x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
続いては、8bitごとに計算していきます。
x + (x >> 4) の下位４ビットに立っていたビット数が入ります。
ただし、上位４ビットはもう必要ないので、 0x0f = 0b0000_1111 でマスクします。
8bit整数で立っているビット数を表現しているわけですが、最大でも8が表現できれば十分なので、下位４ビットあれば十分です。
4〜7行目
x = x + (x >> 8) # 16bitごと
x = x + (x >> 16) # 32bitごと
x = x + (x >> 32) # 64bitごと
return x & 0x0000007f
各行でマスクせず、下位ビットに立っているビット数を集めていきます。
0x0000007f でマスクする理由
64bit整数の立っているビット数は 0~64 までを取り得ます。
64は、2進数で 0100 0000 なので、7bitあれば表現できます。
したがって、出力される値としては、下位7bitのみが値を持つものとなるはずですね。
下位7bitが全て1である16進数は 7f です。
7f でマスクすれば、64bit整数の中でも下位7bitのみが値を持つものをreturnできます。
（再掲） popcountアルゴリズム
def popcount(x):
'''xの立っているビット数をカウントする関数
(xは64bit整数)'''
# 2bitごとの組に分け、立っているビット数を2bitで表現する
x = x - ((x >> 1) & 0x5555555555555555)
# 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
x = x + (x >> 8) # 16bitごと
x = x + (x >> 16) # 32bitごと
x = x + (x >> 32) # 64bitごと = 全部の合計
return x & 0x0000007f
まとめ
正直、普段のプログラミングで、ビットカウントを実装する必要がある人はほとんどいないと思います。
需要はなさそう・・・、と思いつつ書いてみましたがいかがでしたでしょうか？
とはいえ、ビット演算を勉強すると、整数の内部表現の理解が深まったり、高速なアルゴリズムを知ることができたり、メリットがたくさんあります。
この記事を読んで、ビット演算って案外面白そうと思っていただければ幸いです！
ビット演算を使うと、強いAIが作れる可能性があります。ボードゲームのソフトを作ってみたい人は、チェスのプログラミングのサイトのChess Programming Wiki (英語) などを参照してみてください。