67. 二进制求和

题目描述

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

示例 1：

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

示例 2：

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

提示：

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

解法

方法一：模拟

思路和算法

我们可以借鉴「列竖式」的方法，末尾对齐，逐位相加。在十进制的计算中「逢十进一」，二进制中我们需要「逢二进一」。

具体的，我们可以取 \(n = \max\{ |a|, |b| \}\)，循环 \(n\) 次，从最低位开始遍历。我们使用一个变量 \(\rm carry\) 表示上一个位置的进位，初始值为 \(0\)。记当前位置对其的两个位为 \(a_i\)
和 \(b_i\)，则每一位的答案为 \(({\rm carry} + a_i + b_i) \bmod{2}\)，下一位的进位为
\(\lfloor \frac{{\rm carry} + a_i + b_i}{2} \rfloor\)。重复上述步骤，直到数字 \(a\) 和 \(b\) 的每一位计算完毕。最后如果 \(\rm carry\) 的最高位不为 \(0\)，则将最高位添加到计算结果的末尾。

注意，为了让各个位置对齐，你可以先反转这个代表二进制数字的字符串，然后低下标对应低位，高下标对应高位。当然你也可以直接把 \(a\) 和 \(b\) 中短的那一个补 \(0\) 直到和长的那个一样长，然后从高位向低位遍历，对应位置的答案按照顺序存入答案字符串内，最终将答案串反转。这里的代码给出第一种的实现。

复杂度分析

假设 \(n = \max\{ |a|, |b| \}\)。

时间复杂度：\(O(n)\)，这里的时间复杂度来源于顺序遍历 \(a\) 和 \(b\)。
空间复杂度：\(O(1)\)，除去答案所占用的空间，这里使用了常数个临时变量。

Python3

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        a = int(a,2)
        b = int(b,2)
        c = bin(a+b)
        return c[2::]
        # return '{0:b}'.format(int(a, 2) + int(b, 2))

C++


class Solution {
public:
    string addBinary(string a, string b) {
        string ans;
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());
        int n = max(a.size(),b.size()),carry = 0;
        for(int i=0;i<n;i++){
            carry += i<a.size()? int(a[i])-48 : 0;
            carry += i<b.size()? int(b[i])-48 : 0;
            ans.push_back((carry%2)? '1':'0');
            carry /=2;
        }
        if(carry)
            ans.push_back('1');
        
        reverse(ans.begin(),ans.end());

        return ans;
    }
};