题目内容

给你两个二进制字符串，返回它们的和（用二进制表示）。输入为非空字符串且只包含数字 1 和 0。

e.g 示例 1:

输入: a = "11", b = "1" 输出: "100" 示例 2:

输入: a = "1010", b = "1011" 输出: "10101"

提示：

1. 每个字符串仅由字符 '0' 或 '1' 组成
2. a.length >= 1, b.length <= 10^4
3. 字符串如果不是 "0" ，就都不含前导零

我的解法

看完题目，没啥特别的想法。山不过来，我就过去。算不了二进制的加法，转换为十进制计算就好了。

那要做的事就是将输入的字符转为十进制，进行完加法运算后再转换为二进制。

var addBinary = function(a, b) {
    return (Number(convertToDecimal(a)) + Number(convertToDecimal(b))).toString(2)
};
// 转为十进制
var convertToDecimal = (num) => {
    let numArr = num.split('').reverse()
    return numArr.reduce((total, e, i) => {
        return Number(total) + Number(e) * Math.pow(2, i)
    });
}

然而现实并不美好，看着一长串像不像黑客帝国里的乌贼。把类型转为BigInt后，测试用例也只是前进了一格。

大神解法一

var addBinary = function(a, b) {
    return (BigInt('0b' + a) + BigInt('0b' + b)).toString(2);
};

思路可以说是一样，但是实现有点惊为天人了。剖析一下这简短的一句代码。BigInt('0b' + 1010)这一个表达式包含了两部分。0b将1010这一数值显示地声明为二进制数值。同时，BigInt拥有像Number一样的能力，会将其中的数值以十进制的形式返回。由此，我们可以将两个二进制形式的数值以我们擅长的十进制形式来计算。计算完成之后再使用toString(2)转为二进制。

大神解法二

上面的两种逻辑都借助了十进制的计算，有没有可能直接对二进制进行加法运算，也是可以的。主要的算法逻辑是先补齐两个二进制字符串的位数，以实现在相同的位次进行相加。如果相加的和大于1还需要进位，即下次相加还要加上进位的1。另外需要注意的是，因为加法运算是从右往左，所以循环的计数应是减减。

var addBinary = function(a, b) {
    let maxLen = Math.max(a.length, b.length);
    a = a.padStart(maxLen, '0')
    b = b.padStart(maxLen, '0')
    let result = Array.from({length: maxLen}, x => 0)

    let shouldMove = false
    for (let i = maxLen - 1;i >= 0;i--) {
    	let tempa = a[i] || 0, tempb = b[i] || 0;
    	result[i] = +tempa + +tempb + (shouldMove ? 1 : 0)
    	shouldMove = result[i] >= 2
    	result[i] %= 2
    }
    result = (shouldMove ? '1' : '') + result.join('')
    return result
};