负二进制数相加

给出基数为 **-2** 的两个数 `arr1` 和 `arr2`，返回两数相加的结果。

数字以 *数组形式* 给出：数组由若干 0 和 1 组成，按最高有效位到最低有效位的顺序排列。例如，`arr = [1,1,0,1]` 表示数字 `(-2)^3 + (-2)^2 + (-2)^0 = -3`。*数组形式* 中的数字 `arr` 也同样不含前导零：即 `arr == [0]` 或 `arr[0] == 1`。

返回相同表示形式的 `arr1` 和 `arr2` 相加的结果。两数的表示形式为：不含前导零、由若干 0 和 1 组成的数组。

**示例 1：**

```
输入：arr1 = [1,1,1,1,1], arr2 = [1,0,1]
输出：[1,0,0,0,0]
解释：arr1 表示 11，arr2 表示 5，输出表示 16 。
```

**示例 2：**

```
输入：arr1 = [0], arr2 = [0]
输出：[0]
```

**示例 3：**

```
输入：arr1 = [0], arr2 = [1]
输出：[1]
```

**提示：**

- `1 <= arr1.length, arr2.length <= 1000`
- `arr1[i]` 和 `arr2[i]` 都是 `0` 或 `1`
- `arr1` 和 `arr2` 都没有前导0

## 代码：

```java
class Solution {
    public int[] addNegabinary(int[] arr1, int[] arr2) {
        // 定义规则：0+1=1，进位向前边减一，够减则减，不够减则借位
        int[] outCome = null;
        if (arr1.length > arr2.length) {
            for (int i = 1; i <= arr2.length; i++) {
                arr1[arr1.length - i] += arr2[arr2.length - i];
            }
            outCome = arr1;
        } else {
            for (int i = 1; i <= arr1.length; i++) {
                arr2[arr2.length - i] += arr1[arr1.length - i];
            }
            outCome = arr2;
        }
        // System.out.println(Arrays.toString(outCome));
        int add = 0;
        for (int i = outCome.length - 1; i > 0; i--) {
            if (outCome[i] + add >= 2) {
                add = -1;
                outCome[i] -= 2;
            } else if (outCome[i] + add < 0) {
                outCome[i - 1] += 1;
                outCome[i] = 1;
                add = 0;
            } else {
                outCome[i] += add;
                add = 0;
            }
        }
        outCome[0] += add;
        //System.out.println(Arrays.toString(outCome));
        if (outCome[0] >= 2) {
            outCome[0] -= 2;
            int[] newOutCome = new int[outCome.length + 2];
            newOutCome[0] = 1;
            newOutCome[1] = 1;
            for (int i = 0; i < outCome.length; i++) {
                newOutCome[2 + i] = outCome[i];
            }
            outCome = newOutCome;
        }
        // System.out.println(Arrays.toString(outCome));
        if (outCome[0] == 0) {
            int zlength = 0;
            while (zlength < outCome.length && outCome[zlength] == 0) {
                zlength++;
            }
            System.out.println(zlength);
            if (zlength == outCome.length) {
                outCome = new int[1];
                outCome[0] = 0;
            } else {
                int[] newOutCome = new int[outCome.length - zlength];
                for (int i = 0; i < newOutCome.length; i++) {
                    newOutCome[i] = outCome[zlength + i];
                }
                outCome = newOutCome;
            }
        }

return outCome;
    }
}

```

## 错误的办法：

这里主要错误的原因是因为忽略了数组之间的长度，因为长度是1000也就是最大的数是-2的1000次幂。远远的超出了bigint，int，以及long类型的计算长度。所以下面的办法是妥妥的不对的

| 关键字 | 所占位数 | 范围                   |
| ------ | -------- | ---------------------- |
| int    | 32       | −231−231 ~ 2 ^{31} - 1 |
| long   | 64       | −263−263 ~ 2 ^{63} - 1 |

```java
class Solution {
    public int[] addNegabinary(int[] arr1, int[] arr2) {
        int xx = lowBinaryToInt(arr1) + lowBinaryToInt(arr2);
        String ss= intToLowBinaryString(xx);
        String[] ssArr = ss.split("");
        int[] res = new int[ss.length()];
        for (int i = 0; i <= ss.length()-1; i++) {
            res[i] = Integer.parseInt(ssArr[i]);
        }
        return res;
    }
    public static int lowBinaryToInt(int[] arr) {
        double res=0;
        int xx = 0;
        for (int i = arr.length - 1; i>=0; i--) {
            if (arr[i] == 1) {
                res = res+Math.pow(-2, xx);
                xx++;
            }else{
                xx++;
            }
        }
        return (int)res;
    }
    public static String intToLowBinaryString(int N) {
        StringBuilder sb = new StringBuilder();
        while (N != 0) {
            int r = N % -2;
            N = N / -2;
            if (r < 0) {
                r = r + 2;
                N = N+1;
            }
            sb.append(r);
        }
        return sb.length() > 0 ? sb.reverse().toString() : "0";
    }
}
```