二进制求和
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你两个二进制字符串 a 和 b，以二进制字符串的形式返回它们的和。
字符串仅由 '0' 或 '1' 组成；若不是 "0" 则不含前导零。
示例 1
解释：3 + 1 = 4，二进制为 100。
示例 2
解释：10 + 11 = 21，二进制为 10101。
模拟答题者思考
1. 暴力：把两个二进制串转成整数相加再转回二进制——Python 可用 bin(int(a,2)+int(b,2))，但长度可达 104，且面试要的是「模拟竖式」过程。
2. 重复在哪里？和十进制加法一样：从最低位（字符串末尾）对齐，每位只有 0/1，和为 0/1/2/3，当前位写下 sum % 2，进位 sum // 2。
3. 两串长度不同（如 "11" + "1"）时，较短串左侧视为补 0，只需在指针走出边界后把该侧位当作 0。
4. 两串都扫完若 carry==1（如 "1"+"1"→"10"），结果比较长串多一位，不能忘记最高位的 1。
5. 从低位往高位收集字符，最后反转（或头插）才符合「无前导零」的输出习惯。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
carry | int | 定义：当前列相加后向更高位传递的进位，取值 0 或 1，初始为 0 维护：每位处理完后，若 bit_a + bit_b + carry >= 2 则 carry=1 否则 carry=0更新：从两串末尾同步向左扫描，用新 carry 进入下一列；两串都扫完后若 carry==1 再补一位 |
i / j | int | 定义：a、b 当前正在处理的字符下标，分别从 len(a)-1、len(b)-1 开始维护：某串已扫完时，该侧当前位视为 0（相当于前导补零对齐） 更新：每轮若 i>=0 则取 a[i] 并 i-=1，同理 j |
ans（或逆序收集） | str / list | 定义：从低位到高位依次得到的和位字符 维护：每列的和位为 (bit_a + bit_b + carry) % 2，追加到结果尾部（或先 push 再最后反转）更新：循环结束后若仍有进位，再追加 '1'，最后反转得到最高位在左的字符串 |
落码步骤
1. carry = 0，i = len(a)-1，j = len(b)-1，用列表 bits 收集结果位
2. 当 i >= 0 或 j >= 0 或 carry：取当前位 da = int(a[i]) if i>=0 else 0，db 同理；sum = da + db + carry
3. bits.append(str(sum % 2))，carry = sum // 2，i--，j--
4. 将 bits 反转拼接为字符串返回（或循环中用 result = str(sum%2) + result 正序构建）
代码实现
class Solution:
def addBinary(self, a: str, b: str) -> str:
i, j = len(a) - 1, len(b) - 1
carry = 0
bits = []
while i >= 0 or j >= 0 or carry:
da = int(a[i]) if i >= 0 else 0
db = int(b[j]) if j >= 0 else 0
s = da + db + carry
bits.append(str(s % 2))
carry = s // 2
i -= 1
j -= 1
return "".join(reversed(bits))class Solution {
public:
string addBinary(string a, string b) {
int i = (int)a.size() - 1, j = (int)b.size() - 1;
int carry = 0;
string ans;
while (i >= 0 || j >= 0 || carry) {
int da = i >= 0 ? a[i--] - '0' : 0;
int db = j >= 0 ? b[j--] - '0' : 0;
int s = da + db + carry;
ans.push_back(char('0' + s % 2));
carry = s / 2;
}
reverse(ans.begin(), ans.end());
return ans;
}
};
// 时间 O(max(m,n))，空间 O(max(m,n))复杂度分析
O(max(m,n))
O(max(m,n))（结果字符串）
常见坑
从字符串头部开始加：低位在末尾，必须从 len-1 向 0 扫描。
忘记最终进位："1"+"1" 循环结束后 carry==1，需再写入一位 '1'。
C++ 中 char + char 是 ASCII 相加，应写成 a[i]-'0' 得到 0/1。
必测边界 Case
"11" + "1" → "100"（较短串左侧补 0）
"1111" + "1" → "10000"（结果位数 +1）
"0" + "0" → "0"，"1" + "0" → "1"
"1010" + "1011" → "10101"（示例 2）
"111" + "111" → "1110"（每位都产生进位）