Given two numbers arr1 and arr2 in base -2, return the result of adding them together.

Each number is given in array format: as an array of 0s and 1s, from most significant bit to least significant bit. For example, arr = [1,1,0,1] represents the number (-2)^3 + (-2)^2 + (-2)^0 = -3. A number arr in array format is also guaranteed to have no leading zeros: either arr == [0] or arr[0] == 1.

Return the result of adding arr1 and arr2 in the same format: as an array of 0s and 1s with no leading zeros.

• Example 1:

1
2
3

Input: arr1 = [1,1,1,1,1], arr2 = [1,0,1]
Output: [1,0,0,0,0]
Explanation: arr1 represents 11, arr2 represents 5, the output represents 16.

• Note:

1 <= arr1.length <= 1000

1 <= arr2.length <= 1000

arr1 and arr2 have no leading zeros

arr1[i] is 0 or 1

arr2[i] is 0 or 1

将两个数组,转化为-2 进制数后求和。将和也对应转化为-2 进制返回.

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public int[] addNegabinary(int[] arr1, int[] arr2) {
         int i = arr1.length - 1, j = arr2.length - 1, carry = 0;
    Stack<Integer> stack = new Stack<>();
    while (i >= 0 || j >= 0 || carry != 0) {
      int v1 = i >= 0 ? arr1[i--] : 0;
      int v2 = j >= 0 ? arr2[j--] : 0;
      carry = v1 + v2 + carry;
      stack.push(carry & 1);
      carry = -(carry >> 1);
    }
    while (!stack.isEmpty() && stack.peek() == 0) {
      stack.pop();
    }
    int[] res = new int[stack.size()];
    int index = 0;
    while (!stack.isEmpty()) {
      res[index++] = stack.pop();
    }
    return res.length == 0 ? new int[1] : res;
    }

参考资料

• Negative_base

• adding-two-negabinary-numbers