进制-Adding Two Negabinary Numbers

2020-02-20 14:52:41

问题描述：

问题求解：

最开始的想法是将两个数字先转化成自然数在求和，最后转化回去，但是实际上这种方案是不可取的，主要的问题就是会爆掉。

那么就得按位进行运算了。

进行位运算的时候最大的难点在于进位怎么获得。

显然，当sum = 0 / 1的时候，carry = 0；

当sum > 1的时候，carry = -1;

当sum < 0的时候，carry = 1；

sum = 0 -> carry = 0, result = 0

sum = 1 -> carry = 0, result = 1

sum = 2 -> carry = -1, result = 0

sum = 3 -> carry = -1, result = 1

sum = -1 -> carry = 1, result = 1

    public int[] addNegabinary(int[] arr1, int[] arr2) {

        List<Integer> res = new ArrayList<>();

        int len1 = arr1.length;

        int len2 = arr2.length;

        int carry = 0;

        for (int i = 0; i < Math.max(len1, len2) || carry != 0; i++) {

            int d1 = i < len1 ? arr1[len1 - 1 - i] : 0;

            int d2 = i < len2 ? arr2[len2 - 1 - i] : 0;

            int sum = d1 + d2 + carry;

            res.add(Math.abs(sum) % 2);

            if (sum > 1) carry = -1;

            else if (sum < 0) carry = 1;

            else carry = 0;

        }

        int idx = res.size() - 1;

        while (idx >= 1) {

            if (res.get(idx) == 0) idx -= 1;

            else break;

        }

        int[] nums = new int[idx + 1];

        while (idx >= 0) {

            nums[nums.length - 1 - idx] = res.get(idx--);

        }

        return nums;

    }

巴特西

进制-Adding Two Negabinary Numbers

最新文章

热门文章