問題

https://beta.atcoder.jp/contests/abc105/tasks/abc105_c

整数 $N$ が与えられる。 $N$ の $-2$ 進数表現を求めよ。

考え方

考え方は通常の $n$ 進数を求める方法と同じだが、操作をちゃんと理解していないと実装でバグります。通常の $n$ 進数(今回は $2$ 進数とします) の求め方を復習しておきます。

例として $10$ 進数で $99$ と表現される数の $2$ 進数表現を考えます。これは $99$ を $2$ で割り続けてそのあまりを求めればよいです。以下のような要領でした。
右側が数で左があまりです。

99
49	1
24	1
12	0
6	0
3	0
1	1
0	1

あまりを後ろからみて $99 (10) = 1100011 (2)$ となります。
なぜこのような方法で求められたのか考えてみます。

$99 = 49 * 2 + 1$
$= (24 * 2 + 1) * 2 + 1$
$= 24 * 2^2 + 1 * 2^1 + 1$
$= (12 * 2) * 2^2 + 1 * 2^1 + 1$
・・・
$= 2^6 + 2^5 + 2^1 + 1$

つまりあまりを順次求めていくことで $2^k$ が必要な回数がわかることになります。

この考えと同様に $-2$ で割り続ければよいです。ただし、負数で割るときは注意が必要です。たとえば $-9 = -2 * (5) + 1$ となることから、 $-9$ を $-2$ で割ったときの商は $5$ になります。これはあまりが $1$ になるときに事前に $-1$ することで調整することにします。

public void solve(int testNumber, InputReader in, PrintWriter out) {

            long n = in.nextLong();
            out.println(keta(n, -2));

        }

        String keta(long num, long mod) {

            if (num == 0) {
                return "0";
            }

            StringBuilder sb = new StringBuilder();
            while (num != 0) {
                if (num % mod == 0) {
                    sb.append('0');
                } else {
                    sb.append('1');
                    num -= 1;
                }
                num /= mod;
            }

            return sb.reverse().toString();
        }