乐趣区

LeetCode-67-二进制求和-Python

67. 二进制求和


题目来源:力扣(LeetCode)https://leetcode-cn.com/problems/add-binary

题目


给你两个二进制字符串,返回它们的和(用二进制表示)。

输入为 非空 字符串且只包含数字 1 和 0。

示例 1:

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

示例 2:

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

提示:

  • 每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。
  • 1 <= a.length, b.length <= 10^4
  • 字符串如果不是 “0”,就都不含前导零。

解题思路


思路:位运算

题目提示中说明,如果字符串不是“0”,那么都不含前导零。在这里先用普通的加法来尝试解决问题,由于这个前提,在进行加法运算的时候,需要先将字符进行补位,然后逐位相加。

这个方法的具体步骤如下:

  • 先对两个字符串进行补位,方便逐位相加
  • 在这里,字符相加可能会有进位,这里用 carry 变量储存
  • 将逐位相加的结果存储在列表中,最后转成字符串返回。

关于这个方法的代码大致如下:

def addBinary(self, a: str, b: str) -> str:
    while len(a) > len(b):
        b = '0' + b
    while len(a) < len(b):
        a = '0' + a

    ans = [0] * len(a)

    # 记录逐位相加的结果,# 判断是否有进位
    add_res = 0
    carry = 0

    for i in range(len(a)-1, -1, -1):
        add_res = int(a[i]) + int(b[i]) + carry
        # 字符只包含 1 和 0
        # 不包含进位,相加结果最大为 2
        # 包含进位,可能为 3
        if add_res >= 2:
            carry = 1
            # 逢 2 进位,当前位置的元素则为 add_res - 2
            ans[i] = str(add_res - 2)
        else:
            carry = 0
            ans[i] = str(add_res)

    # 最后还需要再次确认,最终的运算中是否有进位
    return ''.join(['1'] + ans) if carry else''.join(ans)

这段代码使用的普通加法进行解决问题。下面尝试不用加减法来解决问题,这里涉及的就是 位运算

这里再提及下,按位与 异或 运算。

按位与 运算:是指参与运算的两数对应二进制相与。运算的规则是,当对应的进制位都为 1 时,结果才为 1,否则都为 0。

异或 运算:也叫半加运算,因为它的运算法则相当于不带进位的二进制加法。例如:

  • 0⊕0=0,
  • 1⊕0=1,
  • 0⊕1=1,
  • 1⊕1=0

可以看出,异或运算法则与加法法则相同,但是不带进位。

回到当前的题目,我们现在要用位运算来模拟加法求出结果。现在我们拆解一下,先进行 异或 运算,求得无进位结果。根据 按位与,同为 1,结果位才是 1 的运算规则,可以求得进位。循环运算,直到最终进位为 0 时,也就能得到结果。

具体的算法设计如下:

  • 首先将给定字符串 a, b 转换为整数型数字 m, n
  • 当有进位时:

    • 先进行 异或 运算:ans = m ^ n
    • 再进行 按位与 运算获得进位:carry = (m & n) << 1。(这里左移是因为进位应该在更高一位)
    • 重置 m, n 的值。此时 m 表示无进位相加结果,n 表示进位,继续循环
  • 上面 m 相当于存储结果,返回 m 的二进制形式(注意返回字符中 0b

具体的代码实现如下。

代码实现


class Solution:
    def addBinary(self, a: str, b: str) -> str:
        # 转换为整数型数值
        m, n = int(a, 2), int(b, 2)

        # n 在循环中存储进位
        # 当进位为 0,循环结束
        while n:
            # 异或计算无进位相加结果
            ans = m ^ n
            # 计算进位
            # 进位应该在更高一位,所以需要左移
            carry = (m & n) << 1
            # 重置 m,n;此时 m 存储结果,n 存储进位
            m = ans
            n = carry
        # m 存储结果,当 n 为 0,表示无进位
        # 循环结束,返回 m 的二进制形式
        # 注意转换成二进制形式的前缀 '0b'
        return bin(m)[2:]

实现结果


总结


  • 先使用普通的加法解决问题,具体实现如下:

    • 因为要进行逐位相加,那么需要对给定的字符进行补位;
    • 进行逐位相加,(字符仅包含 0 和 1),逢 2 进 1,那么需要定义 carry 变量保存进位;
    • 将逐位相加的结果放到列表中,后面转换为字符串返回。
  • 题目中虽然没有提及不可使用加减法。但是如果有所限制的话,可以考虑使用位运算模拟加法。
  • 这里涉及到两个位运算:按位与 异或

    • 按位与 运算:是指参与运算的两数对应二进制相与。运算的规则是,当对应的进制位都为 1 时,结果才为 1,否则都为 0。
    • 异或 运算:也叫半加运算,因为它的运算法则相当于不带进位的二进制加法。
  • 关于使用位运算的实现方法:

    • 先进行异或运算,求得无进位相加结果
    • 在进行按位与运算,根据按位与的运算法则可以求得进位。
    • 循环计算,当进位为 0 时,则可以得到结果。
退出移动版