> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/wei-yun-suan/67-er-jin-zhi-qiu-he.md).

# \[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中`^`运算符表示**异或**.

```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.

对应的代码为:

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