パスワードを忘れた？ アカウント作成
Close
32053 journal

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

日記 by TarZ

　ちょっと話題になっているコードのネタ。

問題 : 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バイトに増やせば問題はないが）
　ただ、入力と出力の関係がきっちりと決まっていて仕様変更がないと判っているのであれば、（そして、コードサイズと速度が求められる用途、あるいは趣味のコーディングとしてであれば）こんな方法でもアリだと思う。

　さて、これが正しく動くことは検証できるのだが、このハッシュ関数をどのように見つけたのか、という点がよく解らない。おそらく、「ディオファントス方程式に一般解は存在しない」のと同じように、一般的な解法はないのではないかと思うのだけど、どうだろう。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

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

  • 16bits版。あんまりちゃんと検証してないので間違ってるかも知れんが。
    "\0\1\2\4\x9\3\6\xd\xa\5\xb\7\xf\xe\xc\x8"[n * 0x9af0000 >> 28]
    # ただし、演算は32bits符号無し整数。異常値でも配列をはみ出さないが結果も異常値。
    • 　惜しい！　ハッシュ関数はほぼ正解ですが、テーブルが違いそうです。"0125396bf48ae7dc" とすればいけそう。

      # 見やすくするために、テーブルはバイナリじゃなくてchar化しました。

      #define get_a(n) ("0125396bf48ae7dc"[n * 0x9af0000u >> 28])
      int main(){ int i; for(i=1 ; i<=15 ; i++){ unsigned int n=(1<<i); printf("%d : %c\n", n, get_a(n) ); } return 0;}

      2 : 1
      4 : 2
      8 : 3
      16 : 4
      32 : 5
      64 : 6
      128 : 7
      256 : 8
      512 : 9
      1024 : a
      2048 : b
      4096 : c
      8192 : d
      16384 : e
      32768 : f


      　うーむ、やっぱり試行錯誤しか見つける手段はないんでしょうかねえ。
      シェア
      親コメント
  • 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の教祖様

    • v を表現するビットパターン( たとえば v=3 なら 0000 0001 0010 0011 ) の全てのビットパターンを内包する最小のビット列は何か? を求めればよい
      　お、まさしくここがキモですね。

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

物事のやり方は一つではない -- Perlな人