AtCoder Beginner Contest 105 C - Base -2 Number

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

問題概略
整数Nの-2進数表現を求めよ

制約

• 入力はすべて整数である
• $-{10}^9\le N\le {10}^9$

解法

とりあえず正の数の足し算で考える。

上から桁の値を書くと

64 -32 16 -8 4 -2 1　となる

ある桁で1 + 1 が行われると 110になる。これは f(i) :=  2 ^ i * (-1) ^ iとして（値を求めている）f(i+2) + f(i+1) = f(i) * 2より示せる

また、任意の桁で 11 = -1 (たとえば1100 = 100 * -1)より、11 + 1 = 0となる。

以上の２つより-2進数の足し算ができるため、繰り返し二乗法を使えば正の数の場合答えを求められる。

たとえば15の二進数表現は 1111であるため、1 , 2 , 4 , 8 の-2進数表現を足せば答えが導ける。以降-2進数は(-2)と書く

前提として1(-2) = 1

2(-2) = 1(-2) + 1(-2) = 110 (-2)

4(-2) = 110(-2) + 110(-2) = 00(-2) + 100(-2) = 100(-2)

8(-2) = 100(-2) + 100(-2) = 11000(-2)

これらを足すと 11211(-2) = 10011(-2)  となり(11 + 1 = 0 より、12 = 0)

15 = 10011(-2)

与えられたNが負の数の場合は、正の数での値を求め、それに足したら0になるようなものが答えである。

public class Main
{
    static int N, M, K;
    static int[] A;
    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args)
    {
        //longを忘れるなオーバーフローするぞ
        N = sc.nextInt();
        int rN = N;
        N = Math.abs(N);
        String sum = "1";
        String res = "0";
        if (N % 2 == 1) res = "1";
        N /= 2;
        while (N > 0)
        {
            sum = msum(sum, sum);
            if (((N % 2) & 1) == 1) res = msum(res, sum);
            N /= 2;
        }
        if (rN < 0) res = minus(res);
        System.out.println(res);
    }

    public static String minus(String s)
    {
        StringBuilder res = new StringBuilder();
        int[] calc = new int[s.length() + 30];
        int[] calc2 = new int[s.length() + 30];
        for (int i = 0; i < s.length(); i++)
        {
            calc[i] = Character.getNumericValue(s.charAt(s.length() - i - 1));
        }
        for (int i = 0; i < calc.length - 2; i++)
        {
            if (calc[i] > 0)
            {
                calc2[i + 1] += calc[i];
                calc2[i] += calc[i];
            }
        }
        for (int i = 0; i < calc.length; i++)
        {
            calc[i] = calc2[i];
        }
        //仕上げ
        for (int i = 0; i < calc.length - 2; i++)
        {
            int can = Main.min(calc[i + 1], calc[i] / 2);
            calc[i] -= can * 2;
            calc[i + 1] -= can;
            if (calc[i] >= 2)
            {
                calc[i + 1] += calc[i] / 2;
                calc[i + 2] += calc[i] / 2;
                calc[i] %= 2;
            }
        }
        int i = calc.length - 1;
        while (calc[i] == 0) i--;
        while (i >= 0) res.append(calc[i--]);
        return res.toString();
    }

    public static String msum(String a, String b)
    {
        //先頭が0桁目
        StringBuilder res = new StringBuilder();
        int[] calc = new int[Math.max(a.length(), b.length()) + 30];
        for (int i = 0; i < a.length(); i++)
        {
            calc[i] = Character.getNumericValue(a.charAt(a.length() - i - 1));
        }
        for (int i = 0; i < b.length(); i++)
        {
            calc[i] += Character.getNumericValue(b.charAt(b.length() - i - 1));
        }
        for (int i = 0; i < calc.length - 2; i++)
        {
            int can = Main.min(calc[i + 1], calc[i] / 2);
            calc[i] -= can * 2;
            calc[i + 1] -= can;
            if (calc[i] >= 2)
            {
                calc[i + 1] += calc[i] / 2;
                calc[i + 2] += calc[i] / 2;
                calc[i] %= 2;
            }
        }
        int i = calc.length - 1;
        while (calc[i] == 0) i--;
        while (i >= 0) res.append(calc[i--]);
        return res.toString();
    }