二进制求和

七崽爱吃小饼干2026/01/19阅读 1专栏算法合集

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

示例 1：

codeType

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

示例 2：

codeType

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

提示：

1 <= a.length, b.length <= 104
a 和 b 仅由字符 '0' 或 '1' 组成
字符串如果不是 "0" ，就不含前导零

解法

解法一：模拟

function addBinary(a: string, b: string): string {
    // 给较短的字符串补0，然后从后往前逐位进行加法运算即可
    let ans = []
    const n = a.length
    const m = b.length
    let c = 0 // 进位
    for(let i = n - 1, j = m - 1; i >= 0 || j >= 0; i--, j--){ // 从后往前遍历
        let c1 = i >= 0 ? parseInt(a.slice(i, i + 1)) : 0
        let c2 = j >= 0 ? parseInt(b.slice(j, j + 1)) : 0
        ans.unshift((c1 + c2 + c) % 2)
        c = Math.floor((c1 + c2 + c) / 2)
    }
    if(c > 0){ // 处理最后一位进位
        ans.unshift(1)
    }
    return ans.join('')
};

上面的写法用unshift和slice性能比较差，因为unshift是从头插入，后续的元素都需要后移。用push再reverse会更高效（理论上，实际测下来其实还是上面的快）。

function addBinary(a: string, b: string): string {
    // 给较短的字符串补0，然后从后往前逐位进行加法运算即可
    let ans = []
    const n = a.length
    const m = b.length
    let c = 0 // 进位
    for(let i = n - 1, j = m - 1; i >= 0 || j >= 0; i--, j--){ // 从后往前遍历
        let c1 = i >= 0 ? parseInt(a.charAt(i)) : 0
        let c2 = j >= 0 ? parseInt(b.charAt(j)) : 0
        ans.push((c1 + c2 + c) % 2)
        c = Math.floor((c1 + c2 + c) / 2)
    }
    if(c > 0){ // 处理最后一位进位
        ans.push(1)
    }
    return ans.reverse().join('')
};

解法二：位运算

function addBinary(a: string, b: string): string {
    let res = '';
    let i = a.length - 1, j = b.length - 1, carry = 0;
    while(i >= 0 || j >=0 || carry) {
        const sum = (i >=0 ? +a[i--] : 0) + (j >=0 ? +b[j--] :0) + carry;
        res = (sum & 1) + res; // 直接拼在字符串前面，替代unshift
        carry = sum >> 1; // 位运算：右移1位 等价于 除以2取整，最快！
    }
    return res;
}