はじめに
前回のメモの続きです。
ネタの起点はThe Art of Computer Programming。
trailing zeros
(08/26追記)
LSBの説明が間違っていたため修正しました。
@fujitanozomuさん、ご指摘ありがとうございます。
trailing zerosは右端から0が連続する数を10進数で表した数値です。
例えば、
10100000
-> 5
01001101
-> 0
です。
ビットマップのループ再訪
前回のメモで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)
これを敢えて使わない場合、次のようなアルゴリズムで実装できます。
ビットカウントによる方法
シンプルな方法としては、前回の記事で書いたビットカウントを使う方法があります。
最右の1ビットを抜き出したビット列から1を引くと、
末尾まで1ビットが連続するのでビットカウントした値がそのままtrailing zerosに。
00100000
-> -1 -> 00011111
-> ビットカウント -> 5
00000001
-> -1 -> 00000000
-> ビットカウント -> 0
(注)0だと正しい値にならないので別途考慮が必要
簡単ですが、Log(ビット長)のオーダになってしまうのが気になるところ。
De Brujin Sequenceによる方法
掛け算1回+シフト1回+配列アクセス1回で済ます方法があります。
流れ
De Brujin Sequenceという名のマジックナンバー00011101
を掛け算して
00100000
-> * 00011101 -> 10100000
00000001
-> * 00011101 -> 00011101
マジックナンバーの長さに応じて右シフトして(8 - log(8)ビット)
10100000
-> 5ビット右シフト -> 00000101
00011101
-> 5ビット右シフト -> 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=Go実装、
De Brujin Sequenceの数や他の値の例についてはChess Programming Wikiから引用。
ここまで書いたけど
trailing zerosはBMI1拡張命令のひとつ「tzcnt」命令として実装されてるので、
言語によってはライブラリが提供する関数で勝手に最適化されるかもしれません。
あと、De Brujinの読み方がわからない。。。
「ド・ブラン」「デ・ブルーイン」等々
どれが多数派なんでしょうね?
参考
De Bruijn Sequence
https://www.chessprogramming.org/De_Bruijn_Sequence
de Bruijn Graph を使った de novo アセンブリの発想がすごい件
http://hoxo-m.hatenablog.com/entry/20100930/p1