TarZの日記: 【話題騒然】n=2^aで、入力nに対応するaを求めるコード 5
ちょっと話題になっているコードのネタ。
問題 : n = 2^a で、nに対応するaを求めたい。(a は 1~9 の値をとる)
ただし、なるべくループやlogは用いず、軽くてコンパクトなコードとしたい。例えば、
n=512 → a=9
n=256 → a=8
:
n=2 → a=1
関連/.J日記 cheekcatさん okkyさん
この問題の初出は、私が知る限り2chプログラム板のビット演算スレッドだ。(ここは私も出入りしている)
私がぱっと思いつくのはこんな方法。ちなみにこの方法は、ビット演算7回と判断4回、判断のための直値4つ、出力値のための直値8つを使用する。
a = (n & 0xff00 ? 8 : 0) | (n & 0xf0f0 ? 4 : 0) | (n & 0xcccc ? 2 : 0) | (n & 0xaaaa ? 1 : 0);
異常値が入力されたかどうかチェックしたいなら、さらにこう付け加える。この場合、512, 256, ... 2以外の値が入力された場合は -1 を返す。なお、式を見やすくするため、演算上は不要なカッコを追加している。
a = ( (n & 0x03fe) && !(n & (n-1)) ) ? (n & 0xff00 ? 8 : 0) | (n & 0xf0f0 ? 4 : 0) | (n & 0xcccc ? 2 : 0) | (n & 0xaaaa ? 1 : 0) : -1;
さて、ここまでは、ビット演算の心得のある人ならば誰でも思いつくような、最も平易な回答の一つだろう。2chでは、判断を使わないもの等、もうちょっとヒネったビット演算を使ったやり方も出ている。
これに対し、あちこちで話題になったのは、ハッシュを使った方法だ。
a = "\1\2\3\010\6\4\011__\7\5"[n*0x5300000>>28];
これは、最初の問題を「特定のスパース配列をどのように効率よく(最小サイズで)管理するか」という問題とみなし、この場合(だけ)に対応する完全最小ハッシュ関数を導き出している。(無効な値'_'が2つあるから、ほんとは「最小」じゃないんだけど)
この方法だと、乗算1回, 演算のための直値1つ, ビットシフト1回, ハッシュテーブル11(+終端1)バイト、インデックスメモリ参照1回で済む。
このハッシュ関数はこのケースだけで役に立ち、他の場面での応用はほとんどできない。つまり、仕様変更等には非常に弱い。加えて、入力値チェックと組み合わせないと、セグメント例外やその他の好ましくない動作を引き起こしかねない脆弱なコードだ。(このケースでは、テーブルサイズを16バイトに増やせば問題はないが)
ただ、入力と出力の関係がきっちりと決まっていて仕様変更がないと判っているのであれば、(そして、コードサイズと速度が求められる用途、あるいは趣味のコーディングとしてであれば)こんな方法でもアリだと思う。
さて、これが正しく動くことは検証できるのだが、このハッシュ関数をどのように見つけたのか、という点がよく解らない。おそらく、「ディオファントス方程式に一般解は存在しない」のと同じように、一般的な解法はないのではないかと思うのだけど、どうだろう。
試行錯誤でも意外と簡単だった(?) (スコア:1)
"\0\1\2\4\x9\3\6\xd\xa\5\xb\7\xf\xe\xc\x8"[n * 0x9af0000 >> 28]
# ただし、演算は32bits符号無し整数。異常値でも配列をはみ出さないが結果も異常値。
Re:試行錯誤でも意外と簡単だった(?) (スコア:1)
# 見やすくするために、テーブルはバイナリじゃなくてchar化しました。
うーむ、やっぱり試行錯誤しか見つける手段はないんでしょうかねえ。
Re:試行錯誤でも意外と簡単だった(?) (スコア:1)
# 手計算とは言え、どーしてそんな派手に...。インデクスと値が逆になってるとは思ったけどそうでもなさそうだし。
もっと汎用的に、例えばC++のテンプレートメタプログラミングでビット数指定して生成したりできないかなー。とか思ってみたりする。
いや、多分これは簡単に求められる。 (スコア:1)
で、多分このことに気がつけば、あとは簡単かと。
.
話を簡単にするために、<<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:いや、多分これは簡単に求められる。 (スコア:1)
おそらく、与えられたビットパターンが任意となると一般的な解法はなさそうですが、今回のケースでは規則性があるので(0000,0001,0010,...)、なにか一般的な解き方がありそうな気がします。