一番左端の立っているビット位置を求めるすんごいコード(NLZ)

c言語 雑記

昨日、先輩に2009-07-04を教えてもらった。
何だか分からないが凄いコードだ。
僕的にはNTZ（右端のビット位置を求める）より32bitのNLZ（左端を..）の方が色々と利用できる場面があるのでそっちに使えないのか考えてみた。

ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか
ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか
posted with amazlet at 09.07.07
ジュニア,ヘンリー・S. ウォーレン
エスアイビーアクセス
売り上げランキング: 16618
おすすめ度の平均: 5.0
5 ビットの楽しみ
5 たのしみ？　たしなみ？
5 ちゃんと読むと得した気分になれます
5 最後の頑張りに効きます
5 Hackっていうのは、こういうコトさ
Amazon.co.jp で詳細を見る


一応説明しておくとNLZは32bitの値を2進で表示したとき一番左からの0の個数。
0x80000000なら0、0x08000000なら4、8なら24で、1なら31という具合。

まず、ここで紹介されているリンクにあった下記のコードを使えばいけそう。

PM 11:41 【話題騒然】n=2^aで、入力nに対応するaを求めるコード

これM系列を利用すると簡単に拡張できそうだ。

ということで、32bit対応版
a = ("\0\1\2\xf\x1d\3\x17\x10\x1e\x1b\4\6\xc\x18\x8\x11"
"\x1f\xe\x1c\x16\x1a\5\xb\7\xd\x15\x19\xa\x14\x9\x13\x12")
[0x5763e69U * n >> 27];

【話題騒然】n=2^aで、入力nに対応するaを求めるコード | Tellur52の日記 | スラド


NTZの場合は(x & -x)で右端のビットを残して残りをクリア出来るが、NLZはそんな簡単な方法もないのでHacker's Delightのflp2を使って一番近い2のN乗の値に切り下げてから渡すようにする。
（ちなみにHacker's Delightの公式ホームページからコード集の圧縮ファイル(HDcode.zip)がダウンロード出来るのでご参考に！）

unsigned flp2(unsigned x) {
   x = x | (x >> 1);
   x = x | (x >> 2);
   x = x | (x >> 4);
   x = x | (x >> 8);
   x = x | (x >>16);
   return x - (x >> 1);
}


で、上記２つのコードを合体。

unsigned nlzM(unsigned x) {
   if (x == 0) { return 32; }
   x = x | (x >> 1);
   x = x | (x >> 2);
   x = x | (x >> 4);
   x = x | (x >> 8);
   x = x | (x >>16);
   return 31 - ("\0\1\2\xf\x1d\3\x17\x10\x1e\x1b\4\6\xc\x18\x8\x11"
                "\x1f\xe\x1c\x16\x1a\5\xb\7\xd\x15\x19\xa\x14\x9\x13\x12")
               [0x5763e69U * (x - (x >> 1)) >> 27];
}


これを使えば一発で32bit値の正規化（8 << nlzM(8) → 0x80000000）が出来てしまう。
整数とか固定小数点→浮動小数点数への変換とか色々使えそう。
だけど問題は、職場でこのコードが受け入れられるか、だなぁ。<追記>
解説書きました→今朝書いたNLZのコードについてのメモ。 - Koonies/こりゃいいな！