De Bruijn sequence を列挙するコード - 当面C#と.NETな記録
いろいろとコメントをいただいているうちに De Bruijn sequence がわかってきました。初めは数学的な背景には興味がなかったんだけど、De Bruijn sequence をすべて列挙する問題が最近遊んでいるデータマイニングの頻出集合を求める問題とそっくりなことに気づいて、ちょっと練習がてらコードを書いてみました。かのダイクストラもコード書いて遊んでみたんなら自分もちょっと遊んでみようかなと。求めてどうするかは知りませんｗ De Bruijn sequence の詳しい説明はこちら http://chessprogramming.wikispaces.com/De+Bruijn+sequence 深さ優先探索をする再帰によるバックトラックの簡単なコードです。De Bruijn sequence は爆発的な勢いで解の数が増えていくので小さい数字で動かしてみてください。解の数は |
一番右端の立っているビット位置を求める「ものすごい」コード - 当面C#と.NETな記録
一番右端の立っているビット位置(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 のときに表題どおりの問題として考えるといくつを返すの？ってことになるので、
一番右端の立っているビット位置を求める「ものすごい」コードのていねいな説明 - 2009-07-06 - 当面C#と.NETな記録
id:siokoshou:20090704 のはてブのコメント見てるとわからないってコメントが結構あるので、もう一度がんばって説明してみます。まあわかったところで得はないかもしれませんｗ 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[
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
