1073. Adding Two Negabinary Numbers 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public int[] addNegabinary(int[] arr1, int[] arr2) {
        int[] ans = new int[2 + arr1.length + arr2.length];
        int index = ans.length - 1;

        int i = arr1.length - 1, j = arr2.length - 1;
        while (i >= 0 || j >= 0) {
            int sum = 0;
            if (i >= 0) {
                sum += arr1[i--];
            }
            if (j >= 0) {
                sum += arr2[j--];
            }
            ans[index--] = sum;
        }

        for (int k = ans.length - 1; k > 0; k--) {
            if (ans[k] > 1) {
                ans[k] -= 2;
                if (ans[k - 1] > 0) { // 未处理过的高位值最大为 2
                    ans[k - 1] -= 1; // 抵消掉一个更高位
                } else {
                    // 0010
                    // 0010
                    // 1100
                    //
                    // -2 + -2 = -4
                    // -8 + 4 = -4
                    ans[k - 1] += 1;
                    ans[k - 2] += 1;
                }
            }
        }

        index = 0;
        while (index < ans.length - 1 && ans[index] == 0) {
            index++;
        }
        return Arrays.copyOfRange(ans, index, ans.length);
    }
}

References

1073. Adding Two Negabinary Numbers
两个方法：①转十进制计算；②模拟负二进制加法