题目: 二进制求和

分析

方法一：模拟

这是一种非常直接的方法，将两个二进制数转换成整数之后求和，再把和转换成二进制。但需要考虑较大数据的情况，比如 $2^{31}-1$。

具体实现如下：

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            answer = x ^ y
            carry = (x & y) << 1
            x, y = answer, carry
        return bin(x)[2:]

时间复杂度为 $O(\max(m, n))$，其中 $m$ 和 $n$ 分别是两个字符串的长度，空间复杂度为 $O(\max(m, n))$。

方法二：字符串模拟

这是一种更直接的方法，从低位开始模拟加法，遇到进位就记录下来，最后将结果翻转。实现起来比较简单。

具体实现如下：

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        n = max(len(a), len(b))
        a, b = a.zfill(n), b.zfill(n)
        carry = 0
        answer = []
        for i in range(n - 1, -1, -1):
            if a[i] == '1':
                carry += 1
            if b[i] == '1':
                carry += 1
            if carry % 2 == 1:
                answer.append('1')
            else:
                answer.append('0')
            carry //= 2
        if carry == 1:
            answer.append('1')
        answer.reverse()
        return ''.join(answer)

时间复杂度为 $O(\max(m, n))$，其中 $m$ 和 $n$ 分别是两个字符串的长度，空间复杂度为 $O(\max(m, n))$。

方法三：位运算

这是一种更为高效的方法，使用位运算模拟加法，可以不用转换成整数，而是直接操作二进制数的每一位。

具体实现如下：

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            answer = x ^ y
            carry = (x & y) << 1
            x, y = answer, carry
        return bin(x)[2:]

时间复杂度为 $O(\max(m, n))$，其中 $m$ 和 $n$ 分别是两个字符串的长度，空间复杂度为 $O(\max(m, n))$。