どのようにして一番右の1のビット位置を求めているのか？

一番右端の立っているビット位置を求める「ものすごい」コード - 当面C#と.NETな記録

「ものすごい」コードなのだけど、凄過ぎて自分には全くチンプンカンプン...。それでも、どの辺が凄いのか、ちゃんと理解したい。シンプルなコードから順を追って確かめてみた。

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;
}

一番右端の立っているビット位置を求める「ものすごい」コード - 当面C#と.NETな記録

rubyでシンプルに書く

全く利用価値はないのだけど、理解を深める為に、上記のコードをRubyで書き直してみた。
最も黒魔術的な 0x03F566ED27179461 をシフト操作する部分も、Rubyのハッシュを使えば省略できる。

# 一番右の1のビット位置を求める（1の右側に0がいくつあるか）
hash = 1
@table = {}
for i in (0..63)
  @table[hash] = i
  hash <<= 1
end

def trailing_zeros(x)
  return 64 if(x == 0)
    
  i = x & -x # 一番右の1のビットだけ残して、その他のビットは0にする
  @table[i]
end

p @table # @table => {1=>0, 2=>1, 4=>2, 8=>3, 16=>4, ... , 9223372036854775808=>63}
p trailing_zeros(8)  # 8.to_s(2)  => "1000" => 3
p trailing_zeros(10) # 10.to_s(2) => "1010" => 1

3つの手順
- @tableに2のn乗をキーに、1のビット位置を値とするハッシュを代入する。（2の63乗まで）

@table = {1=>0, 2=>1, 4=>2, 8=>3, 16=>4, ... , 9223372036854775808=>63}

- 値xは、x & -x を計算することで、一番右の1を残して、その他のビットは全て0に変換される。
- @tableハッシュで x & -x をキーにすれば、対応する値がビット位置になる。
以上の3手順が主要な処理で、こうやってみると、分かり易い。
答えをハッシュに保存して、キーで検索して、答えを求めているだけなのだ。

配列を使う時の問題

Rubyは相当人間寄りな言語で、ハッシュなんてものが使えるので、上記のようにシンプルに書ける。
もっとCPU寄りなC系言語では、ハッシュなんて存在しない。だから、配列を使う。
それでもRubyはずるくって、同様にシンプルに書けてしまうのだが、よく観察すると問題がある。

>> @table=[]
>> @table[1]=0
>> @table[2]=1
>> @table[4]=2
>> @table[8]=3
>> @table[16]=4
>> p @table
[nil, 0, 1, nil, 2, nil, nil, nil, 3, nil, nil, nil, nil, nil, nil, nil, 4]

配列の利用状態が飛び飛びになっている。もし、@table[9223372036854775808]=63 なんてやってしまったら、相当な無駄遣い。

だから、配列は無駄なく64個にすることを考えなくてはならない。

table = new int[ 64 ];

そして、1、2、4、8, ... , 9223372036854775808というキー値を、0から63に変換して利用することになる。
どのように変換するか、実はその部分が黒魔術で、0x03F566ED27179461というビット列（M系列と呼ばれている）を活用している。

M系列とは？

数式：Xn = Xn-p XOR Xn-qで表現される1ビットの周期的な数列
- 例：p=3、q=1、初期値001の場合...

X3 = X3-3 XOR X3-1
   = X0 XOR X2
   = 0 XOR 1
   = 1

- 上記のように順に計算していくと...

n	0	1	2	3	4	5	6	7	8	9	10	11	12	13
Xn	0	0	1	1	1	0	1	0	0	1	1	1	0	1

- 0011101を繰り返す

この数列をシフトしながら、3ビット（pビット）分ごとに取り出すと、0以外の全てのパターンを網羅すると言う不思議な特性がある。
- 例：p=3、q=1、初期値001の場合...

00111010011101
00111010011101
00111010011101
00111010011101
00111010011101
00111010011101
00111010011101

- - 参考ページ：（以下のページが大変参考になりました。感謝です！）
  - Ｍ系列乱数のはなし
  - Ｍ系列乱数生成法

2の累乗数列を順列に変換する

8ビットの2の累乗数列1、2、4、8、16、32、64、128、をM系列を利用して、順列に変換してみる。
p=3、q=1、初期値001が繰り返すM系列：0b0011101を利用する
000だけは繰り返しパターンから抜けてしまうが、先頭に0を追加して0b00011101とすることで、初回だけ000も取り出せる。

# 例：8を変換する場合
0b00011101 * 8 = 0b00011101000 # M系列に8をかけ算すると左に3ビットシフトする
0b00011101000 & 0xFF = 0b11101000 # 下位8ビットを取り出す
0b11101000 >> 5 = 0b111 # 右に5ビットシフトして、上位3ビットを取り出す。

つまり、0b00011101の太字の部分を取り出すことになる。
このようにして、8ビットの2の累乗数列を、重複の無い3ビットの順列に変換することができるのだ。
- 例：p=3、q=1、初期値001の場合...

  1 => 000111010011101
  2 => 000111010011101
  4 => 000111010011101
  8 => 000111010011101
 16 => 000111010011101
 32 => 000111010011101
 64 => 000111010011101
128 => 000111010011101

- 8ビットが、3ビットに圧縮されている！

変換テーブルを作って読み出す

圧縮された3ビットは、0b000から0b111まで、つまり、0から7まで連続している。
よって、配列を使う時の問題で懸念された飛び飛びの利用状態が解消できることになる。
そして、以下のような配列を作っておいて、圧縮された3ビットをインデックスとして読み出せば、ビット位置が求められる。

インデックス	ビット位置
0x000（0）	0
0x001（1）	1
0x010（2）	6
0x011（3）	2
0x100（4）	7
0x101（5）	5
0x110（6）	4
0x111（7）	3

上記は8ビットを3ビットに変換するM系列0b00011101（0x1D）だが、
64ビットを6ビットに変換するのが、0x03F566ED27179461というM系列になるのだ。
相変わらず実用的には無意味なRubyコードだが、理解のため書き直してみた。

# 一番右の1のビット位置を求める（1の右側に0がいくつあるか）
hash = 0x03F566ED27179461
@table = {}
for i in (0..63)
  @table[hash >> 58] = i
  hash <<= 1
  hash &= 0xFFFFFFFFFFFFFFFF # Rubyには符号無し64ビット型とか無いので強引に64ビットにした
end

def trailing_zeros(x)
  return 64 if(x == 0)
    
  y = x & -x # 一番右の1のビットだけ残して、その他のビットは0にする
  i = ((0x03F566ED27179461 * y) & 0xFFFFFFFFFFFFFFFF) >> 58
  @table[i]
end

p trailing_zeros(10)
p trailing_zeros(256)
p @table


# 実行結果...
#
# 10.to_s(2)  => "1010"
# trailing_zeros(10)  => 1
#
# 256.to_s(2) => "100000000"
# trailing_zeros(256) => 8
#
# @table => [0, 1, 59, 2, 60, 40, 54, 3, 61, 32, 49, 41, 55, 19, 35, 4, 62, 52, 30, 33, 50, 12, 14, 42, 56, 16, 27, 20, 36, 23, 44, 5, 63, 58, 39, 53, 31, 48, 18, 34, 51, 29, 11, 13, 15, 26, 22, 43, 57, 38, 47, 17, 28, 10, 25, 21, 37, 46, 9, 24, 45, 8, 7, 6]

結論

X & -Xを利用して、一番右の1のビットだけ残す。（賢い！）
上記で取得できる64ビット2の累乗値を、M系列を利用して6ビットに圧縮する。（凄い！）
配列を利用して、ビット位置を取得する。（高速！）

と、理解した。M系列を少しだけ理解できたことが最大の収穫！

あっ、こっちの方が分かり易いかも...。

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