67. 二进制求和
题目描述
输入两个字符串 a 和 b，它们都是二进制数的写法，只含 '0' 和 '1'。
计算这两个数的和，并把结果同样写成二进制字符串返回。
示例 1
输入：a = "11", b = "1" 输出："100"
解释：3 + 1 = 4，二进制为 "100"。
示例 2
输入：a = "1010", b = "1011" 输出："10101"
解释：10 + 11 = 21，二进制为 "10101"。
数据范围
1 <= a.length, b.length <= 10^4a和b只由'0'和'1'组成。- 除了
"0"本身，两个字符串都没有前导零。
解题思路
模拟竖式加法：两个指针 i、j 从末位往前走，每一位计算 s = 进位 + a[i] + b[j]（缺位当 0）。本位结果是 s & 1（s 的最低位），新进位是 s >> 1。只要还有位没加完或还有进位就继续。最后把收集到的位反转。
为什么正确
处理完低 k 位后，res 中是和的低 k 位（逆序），carry 是向第 k 位的进位，且 carry ∈ {0, 1}。
复杂度分析
时间 O(max(m, n))；结果占 O(max(m, n)) 空间。
易错点
循环条件里别漏掉 carry，否则 "1" + "1" 会得到 "0"；结果是从低位往高位收集的，最后要反转。不要把字符串转成整数相加，长度可达 10^4 位会溢出。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def addBinary(self, a: str, b: str) -> str:
i, j = len(a) - 1, len(b) - 1
carry = 0
res = []
while i >= 0 or j >= 0 or carry:
s = carry
if i >= 0:
s += ord(a[i]) - 48
i -= 1
if j >= 0:
s += ord(b[j]) - 48
j -= 1
res.append(str(s & 1))
carry = s >> 1
return ''.join(reversed(res))class Solution {
public String addBinary(String a, String b) {
int i = a.length() - 1, j = b.length() - 1;
int carry = 0;
StringBuilder res = new StringBuilder();
while (i >= 0 || j >= 0 || carry != 0) {
int s = carry;
if (i >= 0) {
s += a.charAt(i) - '0';
i--;
}
if (j >= 0) {
s += b.charAt(j) - '0';
j--;
}
res.append(s & 1);
carry = s >> 1;
}
return res.reverse().toString();
}
}class Solution {
public:
string addBinary(string a, string b) {
int i = a.size() - 1, j = b.size() - 1;
int carry = 0;
string res;
while (i >= 0 || j >= 0 || carry) {
int s = carry;
if (i >= 0) {
s += a[i] - '0';
i--;
}
if (j >= 0) {
s += b[j] - '0';
j--;
}
res.push_back('0' + (s & 1));
carry = s >> 1;
}
reverse(res.begin(), res.end());
return res;
}
};func addBinary(a string, b string) string {
i, j := len(a)-1, len(b)-1
carry := 0
res := []byte{}
for i >= 0 || j >= 0 || carry != 0 {
s := carry
if i >= 0 {
s += int(a[i] - '0')
i--
}
if j >= 0 {
s += int(b[j] - '0')
j--
}
res = append(res, byte('0'+s&1))
carry = s >> 1
}
for l, r := 0, len(res)-1; l < r; l, r = l+1, r-1 {
res[l], res[r] = res[r], res[l]
}
return string(res)
}var addBinary = function(a, b) {
let i = a.length - 1, j = b.length - 1;
let carry = 0;
const res = [];
while (i >= 0 || j >= 0 || carry) {
let s = carry;
if (i >= 0) {
s += a.charCodeAt(i) - 48;
i--;
}
if (j >= 0) {
s += b.charCodeAt(j) - 48;
j--;
}
res.push(String(s & 1));
carry = s >> 1;
}
return res.reverse().join('');
};function addBinary(a: string, b: string): string {
let i = a.length - 1, j = b.length - 1;
let carry = 0;
const res: string[] = [];
while (i >= 0 || j >= 0 || carry) {
let s = carry;
if (i >= 0) {
s += a.charCodeAt(i) - 48;
i--;
}
if (j >= 0) {
s += b.charCodeAt(j) - 48;
j--;
}
res.push(String(s & 1));
carry = s >> 1;
}
return res.reverse().join('');
}