一番右端の立っているビット位置を求める「ものすごい」コードのていねいな説明

id:siokoshou:20090704 のはてブのコメント見てるとわからないってコメントが結構あるので、もう一度がんばって説明してみます。まあわかったところで得はないかもしれませんw

public static int GetNumberOfTrailingZeros( long x )
{
    if ( x == 0 ) return 64;

    ulong y = ( ulong ) ( x & -x );
    int i = ( int ) ( ( y * 0x03F566ED27179461UL ) >> 58 );
    return table[ i ];
}

static int[] table;

table = new int[ 64 ];
ulong hash = 0x03F566ED27179461UL;
for ( int i = 0; i < 64; i++ )
{
    table[ hash >> 58 ] = i;
    hash <<= 1;
}

まずはTarZさんが見つけた謎の数 0x03F566ED27179461 の説明から。これを2進表現すると
0000 0011 1111 0101 0110 0110 1110 1101 0010 0111 0001 0111 1001 0100 0110 0001
です。この数は 6bit の 000000 から 111111 まですべてのビットパターンが現れる不思議な数。このような数(01の数列)を De Bruijn sequence と呼ぶそうです。はてブコメントや参照であげたリンク先ではM系列とも呼ばれているようです。M系列が何かわかりませんがw

左から 6bit を切り出してみると 000000。次に先頭 1bit を飛ばして次の 6bit を見ると 000001。今度は 2bit ずらして 6bit を見ると 000011。
図にします。長いので一部省略。すべてのパターンは TarZさんのところ参照

[0] 0000001111110......010001100001
[1] 0000001111110......010001100001
[2] 0000001111110......010001100001
[3] 0000001111110......010001100001
[4] 0000001111110......010001100001
[5] 0000001111110......010001100001
:
[60] 0000001111110......010001100001(00000)
[61] 0000001111110......010001100001(00000)
[62] 0000001111110......010001100001(00000)
[63] 0000001111110......010001100001(00000)

左の[]内の数はずらしたビット数です。
最後のほうは 6bit ないので後ろに0を補ってあげて 6bit にします。このように 1bit ずつずらしながら切り出したときに 000000 から 111111 まで、すべてのパターンが出現しています。重複もありません。この長ーいビットのどこかでスパッと切って、そこから 6bit 見ると、切る場所が違えば必ず異なるビットパターンが出てきます。逆に 6bit のビットパターンがあれば、どこから切り出した値か一意に決まります。すごい!
6bit で表現できる数の範囲は 2の6乗 = 64 なので 0〜63 です。切り出したビットパターンを10進表現にしてみると

[0] 000000 = 0
[1] 000001 = 1
[2] 000011 = 3
[3] 000111 = 7
:
[61] 001000 = 8
[62] 010000 = 16
[63] 100000 = 32

000000 から 111111 の全パターンが出現しているということは、0〜63 の 6bit で表現できるすべての数があらわれているってことです。これは「[]内の数(ずらしたビット数) 0〜63」と「ビットパターンの 0〜63」が一対一に対応する表と考えることができます。

0 … 0
1 … 1
2 … 3
3 … 7
:
61 … 8
62 … 16
63 … 32

これをテーブルに入れておきます。「table[ビットパターン]=ずらした数」として作ります。
table[0]=0, table[1]=1, table[3]=2, table[7]=3,... table[8]=61, table[16]=62, table[32]=63
こうしておくと、int n = table[ 6bit のビットパターン] として、どこから切り出したのか求めることができます。


テーブルの正体がわかったので計算のほうを見ていきます。
x & -x。これを計算すると立っている一番右端のビットだけ残して0になります。-x のように符号を反転するには「ビットを反転して+1」という操作が行われます。2の補数表現ってやつです。4bit 幅で例をあげると 1 は 0001、-1 は 1111 です。1 の符号を反転してみると 0001 のビットを反転して 1110、+1 すると 1111 で -1 になりました。逆もやってみると -1 は 1111。1111 のビットを反転すると 0000、+1 して 0001。1 になりました。
では、x & -x を 00100100 を例にやってみます。

00100100 反転すると
11011011 +1すると
11011100 最初の 00100100 と AND を取ると
00000100

反転して+1した値と元の値を比べると、立っている右端のビットだけが共通して立っているのがわかります。賢い!
これで y = x & -x は立っている右端の 1bit だけ 1 で残りのビットは 0 になりました。1bit だけ立っている数、つまり 1,2,4,8,16... 2 の n 乗の値となりました。
C# を知らない人向けに補足しておくと long は符号付き 64bit 整数、ulong は符号なし 64bit 整数、int は符号付き 32bit 整数です。

最後。( y * 0x03F566ED27179461UL ) >> 58。ここで唐突に話はかわって、2倍するって bit で考えるとどんな操作でしょう?

1 * 2 = 2 → 0001 * 2 = 0010
2 * 2 = 4 → 0010 * 2 = 0100
3 * 2 = 6 → 0011 * 2 = 0110

2 倍することは bit でみると左に 1bit シフトすることです。左シフトすると右から 0 が詰め込まれていきます。あふれたビットは捨てられます。4倍だとどうでしょう?

1 * 4 = 4 → 0001 * 4 = 0100
2 * 4 = 8 → 0010 * 4 = 1000

2bit 左シフトです。8倍は?1*8=8なので 3bit 左シフトです。
このように 2 の n 乗倍は n ビット左シフトすることに相当します。Windows の電卓ででも試してみてください。
話を戻すと、3F566ED27179461 に 2 の n 乗である y をかけるのは、左に n ビットシフトしているわけです。これにより、y の立っているビット位置によって上位 6bit に出てくるビットパターンがそれぞれ違うものになります。だんだん話が見えてきました。n ビット左にシフトしたときの結果の上位 6bit を見てみます。[]内はシフトした数 n です。
[0] 00000011... 0bit シフト
[1] 00000111... 1bit シフト
[2] 00001111... 2bit シフト
[3] 00011111... 3bit シフト
:
[61] 00100000... 61bit シフト
[62] 01000000... 62bit シフト
[63] 10000000... 63bit シフト
さっきのビットパターンが上位 6bit に出てきました。この 6bit があればテーブルから n が求められます。ついでと言ってはなんだけど、左シフトしたことで目的の 6bit より左のビットが消えました。
この 6bit より右のビットも邪魔です。なので、64bit から 6bit だけが残るように、64 - 6 = 58bit 右にシフトします。符号なし整数を使っているので、右シフトでは 1001 >> 2 = 0010 のように上位には 0 が入ります。下位 58bit は消えてしまったので、これで目的の 6bit のビットパターンだけが 0〜63 の数として得られました。
まとめると ( y * 0x03F566ED27179461UL ) >> 58 は、2 の n 乗である y をかけることで左に n ビットシフトし、その結果の上位 6bit だけを残すために右に 58bit シフトします。
これでビットパターンが得られたので、この数でテーブルを引けば何ビット左にシフトしたか、つまり右から何番目のビットが立っていたかという答えが得られます。ビットパターン 000000 が出てきたら table[0]=0 で 0bit 目(最下位)が立っていた、000111 が出てきたら table[000111=7]=3 で (0はじまりで)3bit 目が立っていた、100000 が出てきたら table[100000=32]=63 つまり一番上のビットが立っていたというわけです。

これであなたも De Bruijn sequence 初級!


おまけ。テーブル使わずに全ビットパターンが順に出てくる数列はないのかと考えてみる。

[0] 000000 = 0
[1] _000001 = 1
[2] __000010 = 2
[3] ___000011 = 3

0,1,2まではいいけど、3で無理ですね。おしまい。