10進数から-2進数（マイナス２進数）への変換

さっくです。友人に誘われてAtCoderの過去問を解いています。

結構悩んだ問題があったので紹介したいと思います。

-2進数を2進数と同じように定義します。

すなわち、あるn桁の-2進数 $S$ が $S_{n-1} ... S_2 S_1 S_0$ で表されるとき $S$ を10進数に直すと

$S_{n-1}\times(-2)^{n-1}+...+S_2\times(-2)^2+S_1\times(-2)^1+S_0\times(-2)^0$

となります。ここで、 $S$ の各桁は0か1です。

具体的な例を上げてみましょう。例えば-2進数11001は

$[11001]_{-2}=(-2)^4+(-2)^3+(-2)^0=16+(-8)+1=9$

です。

さてここからが問題で、与えられた10進数の整数 $N$ を -2進数に変換する方法を考えてくださいという内容でした。

以下、僕が解説を見てやんわり理解できた部分について説明しますのでネタバレが嫌な方はそっ閉じしてください

13（10進数）を例にとって考えてみましょう。まず、13を2で割ったあまりは1です。 $13 \equiv 1 \pmod{2}$ ですから、ここで $S_0=1$ としないといけません。なぜなら、

$\begin{eqnarray*} (-2)^1 & = & -2 \\ (-2)^2 & = & 4\\ (-2)^3&=&-8\\ (-2)^4&=&16\\ (-2)^5&=&32 \end{eqnarray*}$

と、 $S_1$ 以降どれを1にしても2の倍数しか加算されません。

さて、 $S_0$ の時点で1がわかったので、 $S_1$ 以降で残りの12 （ $=13-1$ ）を作らなければなりません。

では次に、 $S_1$ について考えてみましょう。 12を4で割ったあまりは0です。 $12 \equiv 0 \pmod{4}$ ですから、ここで $S_1=0$ です。なぜなら、以後 $S_2,S_3, ...$ はどれを1にしても4の倍数が加算され、 $S_1$ を1とすると4の倍数ではないものが加算されるからです。 $S_1=1$ としてしまうと、 $S_2,S_3, ...$ をどう作っても4の倍数にはなり得ません。