一番右端の立っているビット位置を求める「ものすごい」コード - 当面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 のときに表題どおりの問題として考えるといくつを返すの？ってことになるので、

[belgianbeer]

この手のアルゴリズムは色々あって面白い

[kazusap]

みてれぅ：[C#] 一番右端の立っているビット位置を求める「ものすごい」コード"2009-07-04 - 当面C#と.NETな記録"

[kamonama]

一番右端の立っているビット位置を求める, Hacker's delight

[noazoh]

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

[petite_blue]

64ビット乗算

[saz_go]

すごい

[tanakaBox]

M系列の周期を全て網羅しておけばいいと。案外応用範囲が広そう。1+1=0の世界は深いぜ。

[naga_sawa]

ビット演算マジック

[rin51]

crazy!

[kennak]

マスク

[cho45]

すごい。わくわくする

[suzak]

0x03F566ED27179461UL

[p_chopin]

面白い。

[y_r]

斜め読みじゃ理解できん...

[ka-wara]

マジックナンバー

[xenoma]

高度な遊びだなあ

[hiroyukim]

ほげ

[youhey]

むつかしい、チンプンカンプン

[asm-orz]

(x & -x)で立っている中で一番右端のbitだけ立たせられるのかメモメモ

[NetPenguin]

これはすごい！

[mohayonao]

0x03F566ED27179461

[kaduki_tomo]

なんじゃこりゃ。

[mohno]

今は乗算命令速いからなあ。（今は知らないが）Intel CPU のビット処理はマイクロコードで劇遅。

[sleepy_yoshi]

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

[mujin]

(y*...>>58)じゃなくて(.../y&63)はダメ？理屈としては分かるけど((y*0x03F566ED27179461UL)>>58)これ自体がテーブルとして機能してるので若干二度手間な感が…。ここだけ(or抜き)で完結する方法がありそう。

[Beno]

"x & -x は Hacker's delight にある、立っている一番右端のビットだけ残して0にしてしまう黒魔術" とりあえずこれだけ覚えておいて残りは後で読み直そう。

[oooooooo]

(y * 0x03F566ED27179461UL ) >> 58

[tsucchi1022]

ビット演算。一番右端の立っているビット位置を求める

[comogly]

謎の"0x03F566ED27179461UL"

[osi7]

黒魔術久しぶりに見たな