Help us understand the problem. What is going on with this article?

ビット演算の高速化メモ2

はじめに

前回のメモの続きです。

ネタの起点はThe Art of Computer Programming

trailing zeros

(08/26追記)

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

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

10100000 -> 5
01001101 -> 0

です。

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

前回のメモx & -xx &= 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

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)

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away