#第２３回[Minus binary numeral system]#

[五反田さんからの出題]
-2011～2011の間の数が1つ入力されます。
その数に対して-2進数に変換した正の数を出力してください。

ちなみに-2進数とは、
一桁目が(-2)の0乗の位
二桁目が(-2)の1乗の位
三桁目が(-2)の2乗の位
・・・というように表される数のことです。

例えば、
10=(-2)^1*1+(-2)^0*0=-2
111=(-2)^2*1+(-2)^1*1+(-2)^0*1=3
というように１０進数変換出来ます。

同じように1100000101111という数字は
(-2)^12+(-2)^11+(-2)^5+(-2)^3+(-2)^2+(-2)^1+(-2)^0
=4096-2048-32-8+4-2+1=2011
というように表されます。

-100001100101という数字も2011を表すのですが、今回はマイナス符号を付ける必要はありません。

[入力 |例1]
-2011

[出力 |例1]
100001100101

[入力 |例2]
3

[出力 |例2]
111

[入力 |例3]
0

[出力 |例3]
0

[入力 |例4]
2011

[出力 |例4]
1100000101111

[入力 |例5]
-64

[出力 |例5]
11000000

[期間]
3/19(土)22:00 ～ 3/26(土)21:59

[hr]
=結果=

投稿数３件(２人）

１位 (90B)
pes さん
s;main(a){scanf("%d",&s);for(a+=!s;s;s=-(s&-2)/2)a=2*a|s&1;for(;a-1;a/=2)putchar(a%2+48);}

2位 (98B)
matsu さん
n;main(t){~scanf("%d",&n)?t=log2(abs(n)),t=(32<<t-t%2)/3,t^=n+t:0;t<2?:main(t/2);putchar(t%2+48);}

＊１位１番乗り
pes さん

[hr]
出題者のコード (78B)
五反田さん
main(n,t){scanf("%d",&n);t=n/-2;n<0&&t*2+n&&t++;t&&main(t);putchar(48+n+t*2);}

[hr]
Code Golf に興味が出てきたら、コミュニティ「Code Golf を楽しもう」まで！
初心者歓迎、参戦＆観戦いつでもお待ちしています！
http://dixq.net/forum/viewforum.php?f=52

第２４回の出題・投稿受付は pes さんです。

[hr]

ご、後日編集でもいいから解説を...お願い...したいです...
今回は全く投稿しなかったからなあ...

さぁ、回答者各位頼んだ ＿ﾉ乙(､ﾝ､)＿

こんなに短くなる問題だったんですかこれ…。

あと、第24回の問題も投稿しておいたので、皆さんぜひやってみてください！
問題文の不備等あればご指摘ください。

> pes さん
面白い問題ですね！
正解が２つだけでもＯＫとなると、どの数字を選ぶべきか迷います (╹◡╹;

ところで、悔しいのでmain再帰にしてみたらだいぶ短くなりました。70Bです。
私の方針は以下のとおりです。

・現在の値aを表す-2進数の最下位ビットは，aの2進数表示の最下位ビットと同じ(a&1)なので，これをsに持っておく
・aのマイナス2進数表示を1ビット右にシフトしてできる値をbとすると，a = -2*b+sとなるので，b=(a-s)/-2
・このbを次のaとして，a=0になるまで再帰的に最下位ビットを求めていく。

提出コードはmain再帰の発想が出なかったので、計算したビットを整数に持っておき…という感じです。

（2011/3/27 8:40追記）
もうちょっと頑張って64Bになりました。中身は70B版の方が分かりやすいと思います。

他の二人のコードが読めない…
pesさんも五反田さんもすごすぎます…

身も蓋もないのですが、自分のコードはこのページを参考にしました。
http://mathworld.wolfram.com/Negabinary.html

このページによると、-2進数は次の式で表せるようです（原理がわかってないので、解説はできません…）
Negabinary[n_Integer] := Module[
{t = (2/3)(4^Floor[Log[4, Abs[n] + 1] + 2] - 1)},
IntegerDigits[BitXor[n + t, t], 2]
]

この式を、intへキャストした時の切り捨てやビットシフトを利用して書いたものが
t=log2(abs(n)),t=(32<<t-t%2)/3,t^=n+t
この部分です。

例題にあるように、10進数の"3"は-2進数では"111"になるのですが、
上の式に"3"を入れると"7"が得られます。
後はそれを2進数に直せば答えが出るようです。

pesさんのラストコードが簡潔で凄いです・・・そして納得。
今回に限らずここ最近のコードは読むのも大変ですね。
そして私は参加できるほどのコードが書けません。orz

> pes さん
main 再帰は五反田さんのお家芸みたいなもんですからー (╹◡╹
Oh... きれいなコードになりましたね。

> matsu さん
なんでしょう、そのびっくりな式はｗ
なるほど Negabinary という言葉があったのですか。

> kimuchi さん
最近は回答者のレベルが上がってるもんで（´ω｀;;;
今週は久しぶりにシンプルな問題ですね！
とんでもないコードを作る余地は無い…はず…？

解説ありがとうございました。
いろいろな解き方ができる興味深い問題でした。五反田さんに拍手！

参加&考えてくれた皆さんありがとうございました。
一瞬だけでもpesさんに勝てたのは嬉しかったです。

次回もなかなか面白そうですね、頑張りましょう。

自分のコードに関しては、書いたのが3週間近く前なので、すでに何をやっているのか自分でも意味不明な状態に・・・・。

結果発表トピックの感想戦の記録を更新しておきました。