# \[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:]
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/wei-yun-suan/67-er-jin-zhi-qiu-he.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.