Hatena::ブログ(Diary)

当面C#と.NETな記録 このページをアンテナに追加 RSSフィード

2009/7/4 (土)

[] 一番右端の立っているビット位置を求める「ものすごい」コード  一番右端の立っているビット位置を求める「ものすごい」コードを含むブックマーク  一番右端の立っているビット位置を求める「ものすごい」コードのブックマークコメント

一番右端の立っているビット位置(RightMostBit)を求めるコードで速いのないかなーと探していたら、ものっっっすごいコードに出会ってしまったのでご紹介。2ch のビット演算スレで 32bit 値のコードに出会って衝撃を受けて、その後 64bit 値版のヒントを見つけたのでコードを書いてみました。

この問題は ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか (Google book search で原著 Hacker's delight が読めたのでそれで済ませた) で number of trailing zeros (ntz) として紹介されています。bit で考えたときに右側に 0 がいくつあるかを数えるもの。1 だと 0、2 だと 1、0x80 なら 7、12 なら 2 といったぐあい。0 のときに表題どおりの問題として考えるといくつを返すの?ってことになるので、問題を正確にするために ntz として 64 を返すことにしたんだと思います。すぐに思いつくのがループで 1bit ずつ見ていく方法ですよね。高速化する方法はおもいつきますか?Hacker's delight ではバイナリーサーチを使ってて、見たときはスゲーと思ったんだけど、このコードの前では色あせて見えます(^^;

ちなみに環境依存してよいなら x86/x64 に bsf (VC++ なら http://msdn.microsoft.com/en-us/library/wfd9z0bb.aspx) ってのがあります。bsf では 0 のときの戻り値は未定義です。

問題の説明はここまでにして、コードの紹介です。Hacker's delight のコードより4〜5倍速く(5-13より4〜5倍、5-15より1.2〜1.3倍)、そして、イミフ加減が半端じゃない!これ一つで 64bit 値以下のすべての値に対応できます。

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

table は以下のようにして求めます。

static int[] table;

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

意味わかりますか?w

x & -x は Hacker's delight にある、立っている一番右端のビットだけ残して0にしてしまう黒魔術。使える場面が多いので覚えておくと便利です。いろんな値を入れてためしてみてください。

その後、完全ハッシュを使って数(2^n)を数(0〜63)に変換してるわけです。0のときの if 文が目障りですが、0のとき呼ばないなど don't care であれば省いてもOKです。省くと 0 のときに 0 が返ってきます。bit1 最下位ビットが立っているときも 0 なので区別できません。64bit 値の右端のビット位置をあらわすには、0の場合も含めると65通りの答えが必要で、もし65をあまり越えないコンパクトなハッシュ値を作れると if が不要になります。あってもこっちのほうが速い可能性はありますが。

このコードは 2ch のビット演算スレ0x03 の 71 と 80 で知りました。

http://pc12.2ch.net/test/read.cgi/tech/1226143920/

80 から解説の引用の引用。

周期2^p-1ビットの列があって、そこからpビットを切り出すと、オール0以外のすべてのパターンが現れる

p=3の場合のM系列は例えばこう。
0011101
↓ (周期2^3-1=7で同じパターンの繰り返し)
001110100111010011101...
上の桁から3ビットを切り出すと、
001 (1)
_011 (3)
__111 (7)
___110 (6)
____101 (5)
_____010 (2)
______100 (4)

1〜7まで全部出るだろ。これに000だけ追加すればおk。
これだけだと順番がバラバラなので、テーブルと組み合わせる。
(中略)
ビット溢れによるマスクなども組み合わせているが。

そして、TarZさんの見つけた値 0x03F566ED27179461 を使ったのが上のコードです。

http://slashdot.jp/~TarZ/journal/448559

0x03F566ED27179461 =

0000 0011 1111 0101 0110 0110 1110 1101 0010 0111 0001 0111 1001 0100 0110 0001。

以下引用。

このビット列について、6文字を切りだす作業を1文字目から順に行っていくと、以下の通りになる。
2つ目のパターンでsortしてみると、000001から111111まで、すべてのパターンが出現していることが確認できる。
さらにこれに000000を加えればすべて揃うことになる。なんと素晴らしい!

    1    000001
    2    000011
    3    000111
以下略

すごい!すごすぎる!この値はどうやって求めたんだろう?

( y * 0x03F566ED27179461UL ) >> 58 の部分についてもうちょっと書いておくと、y は 2 の n 乗の値、つまり 1, 2, 4, 8,... で掛け算することによって 0x03F566ED27179461 を左シフトすることになります。y が 1 ならシフトなし、2 なら 1bit シフト、4 なら 2bit シフトといったぐあい。これによって桁あふれを起こし、上位の桁を消します(追記。このとき y の値によって何ビット左シフトするか変わるので、y の値によって上位 6bit のビットパターンが変わります)。最後に 58bit (58=64-6) 右シフトして上位 6bit のビットパターンを下位に移動し(下位 bit をマスク)、テーブルを引きます。このとき符号付き整数を使うと符号拡張されてしまい、さらに下位 6bit の AND を取る必要がありますが ulong を使うことでこの手間を回避しています。

参考リンク

英語での解説もみつけました。

おまけ。この問題を解く IEEE754 の float を使ったハックがありますが、それの 64bit版 C# コードも書いてみました。上のコードの10倍ほど遅くなってしまいました><

禁断の unsafe 使えば速いかも?

public static int FloatHack2( long v )
{
    if ( v == 0 ) return 64;

    v = v & -v;

    if ( v == -9223372036854775808 ) return 63;

    float f = ( float ) v;
    var bits = BitConverter.GetBytes( f );
    uint n = BitConverter.ToUInt32( bits, 0 );
    int r = ( int ) ( ( n >> 23 ) - 0x7f );
    return r;
}


(7/6追記) たくさんのアクセスありがとうございます。こんなマニアックな話題なのにまさかのホットエントリー入りに驚いてますw

本当に速いの?ってはてブのコメントに答えると、環境依存してよければ x86 には bsf という機械語があって一命令でカウントできます。x64 の 64bit であれば bsfq。環境依存なしならこのコードは私の知る限り最速です。K8 では bsf よりこっちを使ったほうがよいそうです。詳しくはコメント参照。64回ループするのに比べると手元の環境では10倍程度速いです。速さにこだわっているわけは一つ前の日記あたり。もっと速いのあれば教えてください。上には上がいる!かも?

ちなみに Hacker's delight は機械語にすると何命令実行することになるとか論じてる本ですw 分岐や割り算をできるだけ避けるような、そういう世界。

はてブのわからないってコメントに答えて丁寧に説明してみました。でもわからなくてもいいと思うw

  • 編集履歴
    • 2009/7/6 ( y * 0x03F566ED27179461UL ) >> 58 の説明をちょっと直してみた。リンク1件追加。追記追加。
    • 2009/7/7 「Hacker's delight のコードより4〜5倍速く」だった部分を修正。

山田 剛@CSA山田 剛@CSA 2009/07/05 00:31 コンピュータチェスの実装用に、ビット操作を最大限に使う 'bitboard' というテクニックが広く使われていますが、ここでも、長いビット列を乗算によってハッシュアドレッシング可能な短いビット列に変換するテクニックが知られています。

http://chessprogramming.wikispaces.com/Magic+Bitboards

タテやナナメのビット列を無理やりヨコに倒しています。

この方面の黒さ加減も相当なものですが、コンピュータチェスやコンピュータ将棋くらいでしか使えないのが残念。何かのアルゴリズムに応用できないですかね…。

siokoshousiokoshou 2009/07/05 10:42 おー、bitboardってそういうものなんですね。ビット演算スレやwikipediaからリンクがあるのは気づいてたけど見てなかったです。
そして、↑のコードってそこが出所っぽいですw
http://chessprogramming.wikispaces.com/BitScan#DeBruijnMultiplation
ここに数が違うけど同じアルゴリズムのコードがありました。

このマジックナンバーのことを、オランダの数学者 Nicolaas de Bruijn にちなんで De Bruijn sequence と呼ぶそうです。
http://chessprogramming.wikispaces.com/De+Bruijn+sequence
下のほうにあるグラフを拡張していく方式でこの数列を見つけることができるっぽいですね。

プライベートナンバーが欲しい人のためのジェネレーターもあるw ○○専用 De Bruijn sequence!
http://chessprogramming.wikispaces.com/De+Bruijn+Sequence+Generator

このwikiによると、P4 や K8 の bsf はだいぶ遅いようですね。特にK8だとほかのプロセッサのリソースもブロックしてしまうから、↑のコードのほうがいいみたい。

↑のコードの32bitフレンドリーバージョンものってた。
http://chessprogramming.wikispaces.com/BitScan#MattTaylorsFoldingtrick
これもわけわかw

TarZTarZ 2009/07/07 00:50  /.Jの古い日記エントリに、はてブがいくつかついたのでびっくりしました。(んー、その2chコメントも見覚えが…確かビット演算スレ0x02のときに…)

 6ビット版のあのビット列は、試行錯誤で出したものではなくて、M系列の生成式で出したものです。

 「なぜM系列になるか?」といった数学的な裏づけになると少々こみいった話になりますが、とりあえず生成式が判れば、それをちょろっとコードを書けばビット列を得ることはできます。
 残念ながらWeb上では、生成式について詳細に解説された日本語コンテンツは少なそうです。すでにリンクを挙げられている英語コンテンツか、興味がおありでしたら信号処理などの教科書に載っていると思います。

 ゴロム定規とかM系列などは、その性質が興味深いだけでなく、思わぬところで応用できたりするのでなかなか面白いものです。

siokoshousiokoshou 2009/07/07 11:22 おぉぉTarZさん!! 6ビットの数ありがとうございます。後生大事に使わせていただきます。
2chのコメントは演算スレ0x02にあったものが0x03にコピペされてて、これ読んでようやく理解できました。それまではさっぱりわからず頭の上が???だらけでしたw
なるほどー、信号処理ですか。学生のころ苦手だったところだったり(^^;
本当におもしろい数ですね。一つの数にこれだけスゲーって盛り上がるとは思いもしませんでした。
ゴロム定規、M系列調べてみます。↑のコメントで山田さんもおっしゃってますが、ほかに応用ってどんなのがあるんでしょう?

TarZTarZ 2009/07/08 01:37  「ほかの応用」というよりは、どちらかというとM系列の本来の(?)使われ方になるのですが、コンピュータのプログラム関係では、周期の長い擬似乱数列生成が有名かと思います。ここから白色雑音生成などに利用でき、比較的軽い回路や処理で作れるので、信号処理の分野ではよく利用されます。
 私の専門ではないので詳しくは知りませんが、3G携帯電話の通信基盤(基地局〜端末)などでも使われているのではないでしょうか。

 ということで、M系列は(特に工学系の)学生さんにはおなじみの道具ではないかと思いますが、あのような応用があるとは思いもしませんでしたねえ。私も、M系列の話が出てきて初めて、昔の教科書をひっくり返したくらいでして。

http://chessprogramming.wikispaces.com/ のサイトは知らなかったので参考になります。ちょっと読んでみているところですが、De Bruijn sequenceは、M系列に最初から0を付与してある感じ。

siokoshousiokoshou 2009/07/08 14:22 > ここから白色雑音生成などに利用でき、比較的軽い回路や処理で作れるので、信号処理の分野ではよく利用されます。
なるほどー!ずいぶん前に、こんな安いチップでどうやってホワイトノイズ作ってるの?って疑問に思ったことがあったんですが、これで簡単に作れるんですね!ほほーう。
どちらかというとハードよりの応用が多いようですね。とても勉強になります。ありがとうございます。
> http://chessprogramming.wikispaces.com/ のサイト
ここ、おもしろいですよねw ちょっとはまってますw ふざけたことを大真面目に追求してるのがいい感じ!

KooniesKoonies 2009/07/08 21:24 どうも、興味深い話題ありがとうございます。
NLZについて何かないかなとずっと思っていたので参考になりました。
一応0x03F566ED27179461ULの生成コード書いてみました
http://d.hatena.ne.jp/Koonies/20090708/nlz3

siokoshousiokoshou 2009/07/09 00:15 おぉ!すばらしい。どうやらM系列は01の列で、De Bruijn sequenceは01に限らないって感じなのかな?
ダイクストラもDe Bruijn sequenceを求めるコードを書いたそうです。って記事を和田先生が書いている。二重の意味でびっくりな記事を見つけました。
http://parametron.blogspot.com/2009/04/dijkstra.html

CGI の De Bruijn sequenceジェネレーターだそうで。
http://www.hakank.org/comb/debruijn.cgi

De Bruijn sequenceのスゴイ応用w 一番下のビデオ
http://chessprogramming.wikispaces.com/De+Bruijn+sequence

KooniesKoonies 2009/07/09 00:27 M系列は触ったことがあったのでそれなりに理解できましたが
De Bruijn sequenceですか。
新しい課題ありがとうございます(笑

2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 09 | 11 | 12 |
2007 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 08 | 09 | 10 | 12 |
2009 | 01 | 03 | 04 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 07 |
2011 | 04 | 07 | 10 |
2012 | 04 | 12 |
2013 | 08 |
2014 | 03 | 08 |
2017 | 09 |