负二进制数相加

给出基数为 -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

代码：

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

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";
    }
}