剑指 Offer II 002. 二进制加法

问题描述

给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。

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

示例 1:

输入: a = "11", b = "10"
输出: "101"
1
2

示例 2:

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

提示：

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

题解

方法一：从后到前每位依次加

类似于把多位数字以链表的形式存储后来实现加法（如123+456=579，但是存储数字是以链表的形式存，即$1\to 2\to 3+4\to 5\to 6=5\to 7\to 9$）的一种思路。

步骤（以 a = “11”, b = “10” 为例）：

1. 把数字反转 —— a = “11”, b = “01”
2. 将反转后的两个数字从前往后 每位 进行加。

之所以需要反转就是因为可能出现最前面进位的情况，就如这个例子，加完后进位需要前面再补个 1。当然这道题以字符串的形式存储数字，自然不反转倒也可以，因为在前面补 1很方便，每位计算也不难。但如果是链表存多位数的话，首先每位计算时都要遍历链表到后面的位，假如两个4位数相加，就需要遍历4+3+2+1次两个链表，这样时间复杂度很高；其次，在进位时也比较复杂。不过这道题的话这么做确实没有必要，可以更简化一些，这里只是提供个思路。

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        a = a[::-1]
        b = b[::-1]
        sum = ""
        jinwei = 0
        min_len = min(len(a), len(b))
        for i in range(min_len):
            c = int(a[i]) + int(b[i]) + jinwei
            if c < 2:
                sum += str(c)
                jinwei = 0
            else:
                sum += str(c % 2)
                jinwei = 1
        if len(a) == len(b):
            if jinwei:
                sum += str(jinwei)
            return sum[::-1]
        longer = a if len(a) > len(b) else b
        for i in range(min_len, len(longer)):
            c = int(longer[i]) + jinwei
            if c < 2:
                sum += str(c)
                jinwei = 0
            else:
                sum += str(c % 2)
                jinwei = 1
        if jinwei:
            sum += str(jinwei)
        return sum[::-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

上面的代码有些繁杂，改变一下，这样可能更容易理解。不过经过多次提交后这个用时一直都大于上面代码的用时，上面的代码一般是击败80%-90%（32ms，36ms），下面这个只能击败30%左右（40ms，44ms）

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        i = len(a) - 1
        j = len(b) - 1
        sum = ""
        jinwei = 0
        while(i >= 0 or j >= 0):
            add_a = int(a[i]) if i >= 0 else 0
            add_b = int(b[j]) if j >= 0 else 0
            c = add_a + add_b + jinwei
            if c < 2:
                sum += str(c)
                jinwei = 0
            else:
                sum += str(c % 2)
                jinwei = 1
            i -= 1
            j -= 1
        if jinwei:
            sum += "1"
        return sum[::-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

方法二：位运算

我们可以设计这样的算法来计算：

• 把 a 和 b 转换成整型数字 x 和 y，在接下来的过程中，x 保存结果，y 保存进位。
• 当进位不为 0 时
  计算当前 x 和 y 的无进位相加结果：answer = x ^ y
  计算当前 x 和 y 的进位：carry = (x & y) << 1
  完成本次循环，更新 x = answer，y = carry
• 返回 x 的二进制形式

为什么这个方法是可行的呢？在第一轮计算中，answer 的最后一位是 x 和 y 相加之后的结果，carry 的倒数第二位是 x 和 y 最后一位相加的进位。接着每一轮中，由于 carry 是由 x 和 y 按位与并且左移得到的，那么最后会补零，所以在下面计算的过程中后面的数位不受影响，而每一轮都可以得到一个低 i 位的答案和它向低 i + 1 位的进位，也就模拟了加法的过程。

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            sum = x ^ y
            jinwei = (x & y) << 1
            x, y = sum, jinwei
        return bin(x)[2:]
1
2
3
4
5
6
7
8