ビット演算の高速化（trailing zeros）

# はじめに

[前回のメモ](https://qiita.com/phdax/items/3064de264c7933bab2f5)の続きです。

ネタの起点は[The Art of Computer Programming](https://www.amazon.co.jp/dp/4048678817)。

# trailing zeros

（08/26追記）

LSBの説明が間違っていたため修正しました。
@fujitanozomuさん、ご指摘ありがとうございます。

**trailing zeros**は右端から0が連続する数を10進数で表した数値です。
例えば、

`10100000` -> 5
`01001101` -> 0

です。

# ビットマップのループ再訪

[前回のメモ](https://qiita.com/phdax/items/3064de264c7933bab2f5)で`x & -x`と`x &= x - 1`を組み合わせて、立っているビットのみループさせてみました。

```
01011000
↓
f(00001000)
f(00010000)
f(01000000)
```
しかし、受け手の関数としてはビットマップよりもインデックス値のほうが扱いやすいことが多いと思います。
そこで上の処理を

```
01011000
↓
f(3)
f(4)
f(6)
```
このように変える方法 ＝ trailing zerosの計算 が必要になります。
標準的なプログラミング言語では、ライブラリが次のような関数を用意していますが...

```
# Java
Long.numberOfTrailingZeros(long bits)
```

これを敢えて使わない場合、次のようなアルゴリズムで実装できます。

# ビットカウントによる方法

シンプルな方法としては、[前回の記事](https://qiita.com/phdax/items/3064de264c7933bab2f5)で書いたビットカウントを使う方法があります。

最右の1ビットを抜き出したビット列から1を引くと、
末尾まで1ビットが連続するのでビットカウントした値がそのままtrailing zerosに。

`00100000` -> -1 -> `00011111` -> ビットカウント -> 5
`00000001` -> -1 -> `00000000` -> ビットカウント -> 0

(注)0だと正しい値にならないので別途考慮が必要

簡単ですが、Log(ビット長)のオーダになってしまうのが気になるところ。

# De Brujin Sequenceによる方法

掛け算１回＋シフト１回＋配列アクセス１回で済ます方法があります。

## 流れ

**De Brujin Sequence**という名のマジックナンバー`00011101`を掛け算して
`00100000` -> * 00011101 -> `10100000`
`00000001` -> * 00011101  -> `00011101` 

マジックナンバーの長さに応じて右シフトして（8 - log(8)ビット）
`10100000` -> ５ビット右シフト -> `00000101`
`00011101` -> ５ビット右シフト -> `00000000`

あらかじめ作った参照表をみると

|ビットパターン(下3桁)|trailing zeros|
|---|---|
|000|0  |
|001|1  |
|010|6  |
|011|2  |
|100|7  |
|101|5  |
|110|4  |
|111|3  |

`00000101` -> 5
`00000000` -> 0

と計算できます。

## 解説

**De Brujin Sequenceはグレイコードの圧縮表現です。**
例えば、8ビットのDe Brujin Sequenceは3桁のグレイコードをつなげたものになっています。

`00011101`に対して、先頭から順番に3桁ずつ切り取る＝5ケタの右シフト演算をすると
`000` `001` `011` `111` `110` `101` `010` `100` `000`
となっていて、**8ビットの中に0〜7を折りたたむことが可能です。**

つまり最右の1ビットをDe Brujin Sequenceに掛ける（8ビット）ということは、

|De Brujin Sequence|最右の1ビット|De Brujin Sequence x 最右の1ビット|先頭から3桁切り取る|
|---|---|---|---|
|00011101|00000001|00011101|000|
|00011101|00000010|00111010|001|
|00011101|00000100|01110100|011|
|00011101|00001000|11101000|111|
|00011101|00010000|11010000|110|
|00011101|00100000|10100000|101|
|00011101|01000000|01000000|010|
|00011101|10000000|10000000|100|

**最右の1ビットをグレイコード＝0〜7にマッピングする**、ということと同じです。

あとはインデックスにグレイコード、値にtrailing zerosを対応させた配列を作っておけばOK。

|ビットパターン(下3桁)|trailing zeros|
|---|---|
|000|0  |
|001|1  |
|010|6  |
|011|2  |
|100|7  |
|101|5  |
|110|4  |
|111|3  |


掛け算が高速に実行できるのであれば、ビットカウントを使うより効率的です。
ちなみに、GoのTrailingZeros関数はDe Brujin Sequenceで実装されています。

Goのbitsパッケージ（ソースコード）
https://golang.org/src/math/bits/bits.go?s=3946:3972#L103

## ビット長ごとのDe Brujin Sequence

8ビットの場合を例にとりましたが、16ビット、32ビット、64ビット版は次の通りです。

|ビット長|De Brujin Sequence|右シフト長|
|---|---|---|
|8  |0x1D または 0x17|5  |
|16 |0x0D2F など16種|12 |
|32 |0x077CB531 0x077BE629 など2048種|27  |
|64 |0x03F79D71B4CA8B09 0x022FDD63CC95386D など 67108864種|58  |

32ビットの値はGo実装、
64ビットの値は[The Art of Computer Programming](https://www.amazon.co.jp/dp/4048678817)＝Go実装、
De Brujin Sequenceの数や他の値の例については[Chess Programming Wiki](https://www.chessprogramming.org/De_Bruijn_Sequence)から引用。


# ここまで書いたけど
trailing zerosはBMI1拡張命令のひとつ「tzcnt」命令として実装されてるので、
言語によってはライブラリが提供する関数で勝手に最適化されるかもしれません。


あと、De Brujinの読み方がわからない。。。
「ド・ブラン」「デ・ブルーイン」等々
どれが多数派なんでしょうね？

# 参考

De Bruijn Sequence
https://www.chessprogramming.org/De_Bruijn_Sequence

Goのbitsパッケージで参照されている論文
[Leiserson, Charles E., Harald Prokop, and Keith H. Randall. "Using de Bruijn sequences to index a 1 in a computer word." Available on the Internet from http://supertech. csail. mit. edu/papers. html 3.5 (1998)]( http://supertech.csail.mit.edu/papers/debruijn.pdf)

de Bruijn Graph を使った de novo アセンブリの発想がすごい件
http://hoxo-m.hatenablog.com/entry/20100930/p1