BST(1)

ビット演算超魔術(その1)

短いコードのために、必ず書かなければならない部分のバイト数を確認しておく。
main(n){}9バイト
for(;;)8バイト
scanf("%d",&n);15バイト
printf("%d %d\n",a,b);22バイト
これだけでもすでに54バイトある。
最初のインプットは入力データの数だから読み飛ばさないといけないので、数値を一つだけ読み飛ばすテクニックgets()を使うとして60バイト。ということは10バイト弱で解(しかも2つも！)を求めなければならない。forループがscanfのための1回でなければ、とても70バイト(現在は69バイト)もの超ミジカー(ﾟДﾟ)なコードは書けないのだ。

ということはインプットの値から直に答えが計算できるはずだ。
前回書いたいくつかの例を、注意深く見ていくことにする。

まず、入力が8のときは出力が1と15
これを2進数で表すと

0001 ... 1
1000 ... 8
1111 ... 15

入力が12のときは出力が9と15だから

1001 ... 9
1100 ... 12
1111 ... 15

さらに、入力が10のときについて調べてみると

1001 ... 9
1010 ... 10
1011 ... 11

のようになっている。これでもなんとかなりそうだが、もう少し大きな値だとさらにわかりやすい。
入力が312のときは出力は305と319になる。

100110001 ... 305
100111000 ... 312
100111111 ... 319

小さい方の答えは、入力値の最下ビットから調べて初めて1が出てきたところと最下ビットを入れ替えただけだ。また、大きいほうの答えは最下ビットから初めて1が現れるところまでの0をすべて1に置き換えたものになっている。

この操作がビット演算で可能ならば、非常に短いコードが書けるということになる。