「【話題騒然】n=2^aで、入力nに対応するaを求めるコード」記事へのコメント

いや、多分これは簡単に求められる。

[okky (2487)]

get_a マクロを次のものに置き換えてみてください。動くはずです。

#define get_a(n) ("0125396bf48ae7dc"[(( n * 0x9afu )& 0xFFFF) >> 12])

実はこのコード、int が 32bit であることを仮定しています。つまりオリジナルは実は

#define get_a(n) ("0125396bf48ae7dc"[(( n * 0x9af0000u )& 0xFFFFFFFF) >> 28])

と等価です。32bit int を仮定することで巧妙にビットマスクを１つ隠しているわけです。 64bit int マシン上では動きません。

で、多分このことに気がつけば、あとは簡単かと。

.

話を簡単にするために、<<12　のほうで議論しましょう。

0x09af というのは2進数に直すと 0000 1001 1010 1111 です。これに 2^a を掛けるというのはようするに << a するのと同じ。その後、下16bitだけを残すようにマスクして、さらに右に 12 bit 残すのですから、a=9 の場合でも

0000 1001 1010 1111
010 1111 xxxx xxxx x ( <<9 )
yyyy yyyy yyyy 0101 ( >> 12 )

のように4ビットが残るだけです。

『a の値が 0 から v の範囲になるように』すると言うことは、00000 から始まって v を表現するビットパターン( たとえば v=3 なら 0000 0001 0010 0011 ) の全てのビットパターンを内包する最小のビット列は何か? を求めればよい、と言うことになります。あとは a の値ごとに必要な部分が切り出されるように、マスクとこの値を右にシフトする量を求めます。

最後にマスクが不要になるように「定数」部分の数字を決め(左にいくつかシフトすればよい),
その分右にシフトする数字も大きくする。

このままだと「順番どおり」にはビットパターンは出てこないので、数字を元に戻すように表を1つよういすればよい。

.

多分これ、「与えられたビットパターンを最小のビット列に詰め込む方法」とかいう有名な問題を応用しているだけだと思います。『ビット列に詰め込んだ結果』さえ得られれば、あとは O(1) で求められるのではないか、と。

ただし「与えられたビットパターンを最小のビット列に詰め込む」方法自体は NPじゃなかったかしら(ちゃんと覚えていない)。

--
fjの教祖様

Re:いや、多分これは簡単に求められる。

[TarZ (28055)]

v を表現するビットパターン( たとえば v=3 なら 0000 0001 0010 0011 ) の全てのビットパターンを内包する最小のビット列は何か? を求めればよい

　お、まさしくここがキモですね。

　おそらく、与えられたビットパターンが任意となると一般的な解法はなさそうですが、今回のケースでは規則性があるので(0000,0001,0010,...)、なにか一般的な解き方がありそうな気がします。