PKU1023

うむむ、http://www.4dm.org/ShortCoding/index.php?POJ1023を見てビット演算で楽勝じゃんとか思って適当に書き書き。
しかし、逆に長くなってしまったorz
うーん、ビット演算を使える形に持っていくのにバイト数を結構使ってしまう。

問題の詳しい内容は上のURLを参照してもらうとして。
えーと、とりあえず、Fun Numberはビット毎に重みの正負がバラバラなやつです。
重みの正負がビットによってバラバラと言えば-2進数です。
ようするにFun Numberは-2進数の一般化とも言えます。
で、実は-2進数と2進数に対する『ハッカーのたのしみ』の変換方法は、
Fun Numberと2進数の変換として一般化できます。
id:kurimura:20070228

char*p;
_int64 n,m;
main(x,v){
  for(gets(v);~scanf("%d%s%I64d",&x,p=v,&n);
      printf(m/2-~n/2>>x-1?"Impossible\n":"%0*s\n",x,_i64toa(n+m^m,v,2)))
    for(m=0;*p;)
      m=m*2|*p++/2&1;
}

入力 -> pnを2進数に変換 -> オーバーフロー判定 -> 入力をFun Numberに変換 -> 表示
という形になっています。
ただ、このコードではオーバーフローの判定を微妙にイカサマしています。
本来は(m/2-~n/2>>x-1)は(m+n>>x)で十分なのですがm+nが64bitに収まらないため、

    m+n    >> x
 ≒ (m+n)/2 >> x-1
 ≒ m/2+n/2 >> x-1
 ≒ m/2-~n/2>> x-1

と変形して通しました。
最下位1bitの情報を捨ててるのでイカサマコードです。
しかもn/2を-~n/2にして無理やり通しています。
イカサマなしなら、A+B == (A&B)*2+(A^B)を活用して(m&n)+(m^n)/2 >> x-1としたほうが良いかな。