さっくです。 友人に誘われてAtCoderの過去問を解いています。
結構悩んだ問題があったので紹介したいと思います。
-2進数を2進数と同じように定義します。
すなわち、あるn桁の-2進数がで表されるとき を10進数に直すと
となります。ここで、の各桁は0か1です。
具体的な例を上げてみましょう。 例えば-2進数11001は
です。
さてここからが問題で、 与えられた10進数の整数を -2進数に変換する方法を考えてください という内容でした。
以下、僕が解説を見てやんわり理解できた部分について説明しますので ネタバレが嫌な方はそっ閉じしてください
13(10進数)を例にとって考えてみましょう。 まず、13を2で割ったあまりは1です。 ですから、ここでとしないといけません。 なぜなら、
と、以降どれを1にしても2の倍数しか加算されません。
さて、の時点で1がわかったので、 以降で残りの12 ()を作らなければなりません。
では次に、について考えてみましょう。 12を4で割ったあまりは0です。 ですから、ここでです。 なぜなら、以後はどれを1にしても4の倍数が加算され、を1とすると4の倍数ではないものが加算されるからです。 としてしまうと、をどう作っても4の倍数にはなり得ません。
さて、が決まったので、以降で残りの12を作らなければなりません。
について考えてみましょう。 12を8で割ったあまりは4です。 ですから、ここでです。 なぜなら、以後はどれを1にしても8の倍数が加算されるからです。
=1が決まったので[tex:(-2)2=4]は使われることがわかりました。 残りの8(=12-4)を以降で作らなければなりません。
について考えてみましょう。 8を16で割ったあまりは8です。 ですから、ここでです。 なぜなら、以後はどれを1にしても16の倍数が加算されるからです。
が決まったので、-8は使われることになります。 残りの16(=8-(-8))を以降で作らなければなりません。
について考えてみましょう。 16を32で割ったあまりは16です。 ですから、ここでです。 なぜなら、以後はどれを1にしても32の倍数が加算されるからです。
が決まったので、16は使われることになります。 これで、残りがなくなりました。 計算終了です。
という結果が得られました。
もっとスマートなアルゴリズムもあるかと思いますが、 僕がやんわりと理解できた部分でできたのがこれでした。
実際、他の方のソースを見たらもっと単純なやり方があって感心しました。