一番右端の立っているビット位置を求める「ものすごい」コードのていねいな説明 - 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[

[sugawara1991]

割り込みとかのイベントフラグからハンドラ求める場合なら、インデックス化時の参照が省略できてハンドラテーブルも常識的なサイズにできてキャッシュにも優しい。予めハンドラ登録時にハッシュ使っておくのねん

[noazoh]

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

[karronoli]

すげー ビット演算マジックだわー

[pneumaster]

理解できん

[paella]

コメント欄にある「その他の魔法の数字」も興味深い

[yujiorama]

自然言語で説明

[Naruhodius]

∑(｡･д･｡)b ﾅﾙﾎﾃﾞｨｳｽ!

[Layzie]

解説を見てもさっぱり分かりそうにないが、ブクマ

[rawkranz]

ビット演算。Ｍ系列や2の補数周り

[tkawa]

わかりやすい

[pknight]

完全に理解できました。ありがとう。

[mujin]

現実を無視してよければy^6を掛ければいい。/理論値はともかくオーバーヘッドの分こっちのHacker's delightの方が速そうな気がする。http://www.nminoru.jp/~nminoru/programming/bitcount.html