题目：

给出基数为 -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) {
      int len1 = arr1.length, len2 = arr2.length;
      int p1 = len1 - 1, p2 = len2 - 1;
      List<Integer> ans = new ArrayList<>();
      int[] carry = new int[] { 0, 0 };
      while (p1 >= 0 || p2 >= 0) {
          int[] n1 = new int[] { p1 - 1 >= 0 ? arr1[p1 - 1] : 0, p1 >= 0 ? arr1[p1] : 0 };
          int[] n2 = new int[] { p2 - 1 >= 0 ? arr2[p2 - 1] : 0, p2 >= 0 ? arr2[p2] : 0 };
          int[] a1 = add(n1, n2);
          int[] a2 = add(new int[] { a1[2], a1[3] }, carry);
          int[] a3 = add(new int[] { a1[0], a1[1] }, new int[] { a2[0], a2[1] });
          carry = new int[] { a3[2], a3[3] };
          ans.add(a2[3]);
          ans.add(a2[2]);
          p1 -= 2;
          p2 -= 2;
      }
      if (carry[0] != 0) {
          ans.add(carry[1]);
          ans.add(carry[0]);
      } else if (carry[1] != 0) {
          ans.add(carry[1]);
      }
      ans = ans.subList(0, ans.lastIndexOf(1) + 1);
      if (ans.size() == 0) {
          return new int[] { 0 };
      }
      int[] ret = new int[ans.size()];
      for (int i = 0; i < ret.length; i++) {
          ret[i] = ans.get(ans.size() - i - 1);
      }
      return ret;
  }

  private int[] add(int[] n1, int[] n2) {
      int[] n = new int[] { n1[0] + n2[0], n1[1] + n2[1] };
      int a = n[0], b = n[1];
      if (a == 0 && b == 2) {
          return new int[] { 0, 1, 1, 0 };
      } else if (a == 1 && b == 2) {
          return new int[] { 0, 0, 0, 0 };
      } else if (a == 2 && b == 0) {
          return new int[] { 1, 1, 0, 0 };
      } else if (a == 2 && b == 1) {
          return new int[] { 1, 1, 0, 1 };
      } else if (a == 2 && b == 2) {
          return new int[] { 0, 0, 1, 0 };
      } else {
          return new int[] { 0, 0, a, b };
      }
  }

}