ビットカウントする高速アルゴリズムをPythonで実装しながら詳しく解説してみる

# ビットカウントとは

整数を二進数表示した時、0と1の組み合わせになります。
例えば、十進数の `21` を2進数表示した場合、 `0001 0101` のようになります。

この時、 `0001 0101` に含まれる1の数を数えることを**ビットカウント**と言います。

`0001 0101` の場合、立っているビット数は **3** ですね。

なんてことなさそうな計算ですが、実は、**超高速なアルゴリズム**があります。
今回は、このアルゴリズムに触れ、感動した私がそれを解説してみることにします。

# ビットカウントのアルゴリズム

チェスや将棋、オセロのようなボードゲームのAIでは、盤面を**Bitboard**というバイナリで表現することが多いです。
例えば、ある列の駒の数を数える場合、その列に対応するビット列を取り出し、立っているビット数を取得する必要があります。

強いAIを作るためには、高速な計算が必要となります。
全体のビット数分のループを回さずに、**少ない手数でビットカウントできるアルゴリズムがあれば嬉しい**ですね。

英語では、 **population count**とか**popcount**と呼ばれる有名な問題の一つで、非常に効率的なアルゴリズムが見つかっています([Wiki 英語版: Hamming_weight](https://en.wikipedia.org/wiki/Hamming_weight))。

例えば、将棋ソフト強豪として有名な **Apery**でも高速なアルゴリズムが使われています ([ソースコード](https://github.com/HiraokaTakuya/apery/blob/master/src/common.hpp#L199)) 。

# この記事でやりたいこと
以前、[Aperyのソースコード](https://github.com/HiraokaTakuya/apery/blob/master/src/common.hpp#L199)を読んだ時に **popcount** のアルゴリズムを知り、感動しました。
この記事では、Pythonで実際に **popcount** アルゴリズムを実装した上で、その中身を**できるだけ詳しく解説**していきます。

読んだ人に同じように感動してもらおう、というのがこの記事の目的です！

### Pythonを使った理由
超高速なアルゴリズムをわざわざ遅いスクリプト言語であるPythonで実装することに違和感がある人もいるかもしれません。
今回は、**アルゴリズムの理解**に焦点を当てており、計算速度については気にしていません。計算速度の限界に挑戦したい方は、このアルゴリズムを知った後、C++などの高速な言語で実装してみてください。

# 前置きはいいから実装見せてよ

## popcountを実装

```python
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
```

## 計算例

```python
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整数のように分けて捉える
- ビット数を数えるのは実質一行目のみでやっているので、ここで何やってるかを知る

## アルゴリズムの流れ
1. 立っているビット数を計算したい64bit整数を32組の2bit整数にわける
2. その2bit整数自体を、立っているビット数を表す2bit整数に変換する
3. 立っているビット数が32組分できる
3. それらを合計していき、最終的に64bit整数にする


ちなみに、64bitをループで回してビットカウントした場合、どんなに効率的にやっても10倍近く遅くなってしまいます。

## 1行目

```python
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組に対して同時に行います。
この操作がまさに以下のように表現できます。

```python
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`のビットを全体に右に１ビットずらしたものなので、

```python
(x >> 1) & 0x5555555555555555
```

は、`x >> 1` の偶数番目(2,4,6...番目)のみを残す演算になります。
つまり、この演算は **xの奇数番目(1,3,5...番目)のビットのみを抜き出し、右に一つずらしたもの** を計算していることにほかなりません。


## 2行目

```python
x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
```

`0x3` は2進数表示すると、 `0b0011` です。
察しの良い方は気付かれたかもしれないですが、今度は**4bit整数**の組に分けます。

第一項では、4bit整数のうち、下位2bitのみを取り出しています。
第二項では、4bit整数のうち、上位2bitのみを取り出し、下位2bitに持ってきています。

合計すれば、**もともと4bitで立っていたビット数の合計が4bit整数の値**になりますね。

1行目で求めた2bit整数は最大2となるものでしたので、2行目では最大4になります。
**4bit整数の下位３ビット**で立っているビット数が表現できます。

## 3行目

```python
x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
```

続いては、8bitごとに計算していきます。
`x + (x >> 4)` の下位４ビットに立っていたビット数が入ります。
ただし、上位４ビットはもう必要ないので、 `0x0f = 0b0000_1111` でマスクします。

8bit整数で立っているビット数を表現しているわけですが、最大でも8が表現できれば十分なので、下位４ビットあれば十分です。


## 4〜7行目 

```python
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アルゴリズム

```python
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 (英語)](https://www.chessprogramming.org/Bitboards) などを参照してみてください。

# 参考資料

- [x86_64でpopcnt / tzcnt / lzcntする【ビット演算テクニック Advent Calendar 2016 5日目】](https://qiita.com/ocxtal/items/01c46b15cb1f2e656887)
- [Python 3でpopcountを計算する](https://nixeneko.hatenablog.com/entry/2018/03/04/000000)
- [ビットを数える・探すアルゴリズム](http://www.nminoru.jp/~nminoru/programming/bitcount.html)
- [Stockfish ソースコード](https://github.com/kobolabs/stockfish/blob/master/bitcount.h)