题目描述

负二进制数相加

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

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

分析

普通的二进制相加

从低位到高位进行加法运算，在运算的过程中维护一个进位变量carry，carry默认为0

设当前位置该放入的值为cur, 则x = arr[i] + arr[j] + carry —— 例如 arr[i] = 0, arr[j] = 1, carry = 0， 则x = 1

• x = 0或1时，cur = x，同时不进位，carry = 0;
• x = 2或3时，cur = x - 2， 要进位， carry = 1;

比如 arr[i] = 1, arr[j] = 1, carry = 1, 则该位置该放入的值为 3 - 2 = 1，同时进位carry = 1，再进行下一个位置的加法运算

负二进制数相加

与普通二进制计算方式一样，只是处理时需要做一下改变

从低位到高位进行加法运算，在运算的过程中维护一个变量 carry，carry默认为0

设当前位置该放入的值为cur, 则x = arr[i] + arr[j] + carry —— 例如 arr[i] = 0, arr[j] == 1, carry = 0， 则x = 1

• x = 0或1时，cur = x，同时不进位，carry = 0;
• x = 2时，cur = x - 2，同时进位，注意此时的进位就变成了-1，即carry = -1，因为下一位的值与该位置的值的符号是相反的，所以要进位负数
• x = -1时，cur = 1，同时进位，注意进位应该是1, 即carry = 1，因为让该位置取1，下一个位置也取1，两者的和正好表示该位置进制对应是 -1 的情况（如下图公式）
• x = 3时，与x=2的操作时一样的。

$$ -(-2)^i = (-2)^i+1 + (-2)^2 $$

👇 注意：

最坏情况下，当计算完二者最高位的x后，得到x = 3，此时会产生-1的进位， 在之后又会产生 1 的进位，因此，答案的长度最多为 arr1 和 arr2 最大长度 + 2；

我们需要处理到进位为0的地方，也就是虽然遍历完两个数组，但进位不为0时仍要继续处理

代码实现

/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @return {number[]}
 */
var addNegabinary = function (arr1, arr2) {
  let i = arr1.length - 1;
  let j = arr2.length - 1;

  let carry = 0;

  let ans = [];
  // 两个数组长度不一样，所以要用或来判断结束
  // 同时要判断carry，如果遍历完最大长度后不为0，就要往前继续进位计算，直到carry = 0
  while (i >= 0 || j >= 0 || carry !== 0) {
    let x = carry;
    if (i >= 0) {
      x += arr1[i];
    }
    if (j >= 0) {
      x += arr2[j];
    }

    // 开始判断
    if (x >= 2) {
      // 相加等于2或3
      ans.unshift(x - 2);
      carry = -1;
    } else if (x >= 0) {
      // 相加为0或1
      ans.unshift(x);
      carry = 0;
    } else {
      // 相加等于 -1
      ans.unshift(1);
      carry = 1;
    }
    j--;
    i--;
  }

  while (ans.length > 1 && ans[0] == 0) {
    ans.splice(0, 1);
  }

  return ans;
  // 去除前导零
};

var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });
var readline = __readline.prompt;

let arr1 = [];
console.log("请输入arr1: ");

let line1 = readline().split(" ").map(Number);

for (let i = 0; i < line1.length; i++) {
  arr1.push(line1[i]);
}

// console.log(arr1);

let arr2 = [];
console.log("请输入arr2: ");

let line2 = readline().split(" ").map(Number);


for (let i of line2) {
  arr2.push(i);
}

// console.log(arr2);

let res = addNegabinary(arr1, arr2);

console.log("结果为: ", res);