[67][简单] 二进制求和

题目描述

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

示例 1:

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

示例 2:

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

提示：

• 每个字符串仅由字符 '0' 或 '1' 组成。

• 1 <= a.length, b.length <= 10^4

• 字符串如果不是 "0" ，就都不含前导零。

解题思路

竖式加法

如同十进制的加减法, 竖式加减思路. Python中^运算符表示异或.

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        n, m = len(a), len(b)

        res = []
        carry = 0
        for i in range(max(n, m)):
            ba = int(a[n - i - 1] if n - i - 1 >= 0 else '0')
            bb = int(b[m - i - 1] if m - i - 1 >= 0 else '0')
            number = ba ^ bb ^ carry
            carry = (ba + bb + carry) // 2
            res.append(str(number))

        if carry:
            res.append('1')

        return ''.join(res[::-1])

位运算

对于两个二级制数, 直接进行异或运算得到的是加完之后每一位残留数的结果(无进位相加结果), 与运算得到是加法的进位结果. 依据这个思路, 可以循环地从低位开始, 计算对应的异或和与的结果, 然后逐步把进位加到异或运算的结果上.

以5和7两个数字为例, 对应的二级制为101和111, 运算得到:

• 异或: 010

• 与并左移一位: 1010

这里的左移一位是模拟进位的操作, 得到的数字1010就是只考虑进位对应的数字, 而010是不考虑进位的数字, 两者之和始终是加法的最终结果.

这样在第一步, 我们就得到了所有位置的无进位相加的结果和所有位置的进位结果, 之后就是循环吧对应的进位加上. 循环到进位为0结束.

• 第二步: 异或: 1000, 与移: 0100

• 第三步: 异或: 1100, 与移: 0000

进位已经为0, 循环结束, 最终的结果为1100, 即12.

对应的代码为:

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:]