0067.二进制求和

难度：🟢 简单

标签：数学、字符串、位运算、模拟

链接：67. 二进制求和

题目描述

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例 1：

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

示例 2：

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

解题思路

核心思想

本题的核心是模拟两个二进制数的加法过程。这与我们手动进行十进制加法非常相似，区别在于二进制的进位规则是“逢二进一”。我们需要从两个字符串的末尾（最低位）开始，逐位相加，并处理好每一位的进位。

思路选择

迭代法 + 双指针 是解决此问题的标准最优思路。

• 我们使用两个指针，分别指向两个字符串的末尾。

• 在一个循环中，我们逐位取出数字进行相加，同时加上来自前一位的进位。

• 循环的条件是，只要两个指针中还有一个在有效范围内，或者最后还存在进位，就继续计算。

关键步骤

1. 初始化：初始化两个指针 i 和 j 分别指向 a 和 b 的末尾。初始化进位 carry = 0。初始化一个结果数组或字符串 result。

2. 循环计算：当 i >= 0 或 j >= 0 或 carry > 0 时，持续循环。 a. 取值：获取 a[i] 和 b[j] 对应的数字。如果某个指针已经越界，则其对应的位视为 0。 b. 求和：计算当前位的和 sum = digitA + digitB + carry。 c. 计算当前位结果：当前位应存入的结果是 sum % 2。 d. 更新进位：新的进位是 Math.floor(sum / 2)。 e. 拼接结果：将当前位的结果添加到 result 的最前面。 f. 移动指针：将 i 和 j 指针向前移动。

3. 返回结果：循环结束后，result 就是最终的二进制和字符串。

代码实现

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    let i = a.length - 1;
    let j = b.length - 1;
    let carry = 0;
    let result = '';

    while (i >= 0 || j >= 0 || carry > 0) {
        const digitA = i >= 0 ? parseInt(a[i]) : 0;
        const digitB = j >= 0 ? parseInt(b[j]) : 0;
        const sum = digitA + digitB + carry;

        result = (sum % 2) + result; // 将当前位结果加到最前面
        carry = Math.floor(sum / 2); // 计算新进位

        i--;
        j--;
    }

    return result;
};

复杂度分析

• 时间复杂度：O(max(m, n)) 其中 m 和 n 分别是两个输入字符串的长度。我们需要遍历完两个字符串中较长的那一个。

• 空间复杂度：O(max(m, n)) 返回的结果字符串的长度最多为 max(m, n) + 1。

相关题目

• 0002.两数相加

• 0043.字符串相乘

• 0415.字符串相加

总结

本题是模拟计算机底层二进制加法的经典题目。通过双指针从后向前遍历，并细心处理进位，是解决这类问题的通用模式。将复杂的 if/else 逻辑抽象为数学运算是提升代码质量的关键。