二进制求和
一、二进制求和的核心逻辑
二进制求和的本质是模拟十进制加法的竖式运算，但遵循 “逢二进一” 规则。与十进制不同，二进制中每一位的计算结果只有 0 或 1，且产生的进位也仅为 0 或 1。
核心规则：
- 单个位相加：a + b + carry（carry 为上一位的进位，初始为 0）
- 当前位结果：(a + b + carry) % 2（取余得到 0 或 1）
- 新进位：(a + b + carry) // 2（整除得到 0 或 1）
- 处理完所有位后，若仍有进位（carry = 1），需在结果头部补 1
二、直观示例：手动计算二进制求和
以 a = "1010"（十进制 10）、b = "1011"（十进制 11）为例，手动模拟计算过程：
分步拆解：
- 第 0 位（右起）：0 + 1 + 0 = 1 → 结果 1，进位 0
- 第 1 位：1 + 1 + 0 = 2 → 结果 0，进位 1
- 第 2 位：0 + 0 + 1 = 1 → 结果 1，进位 0
- 第 3 位：1 + 1 + 0 = 2 → 结果 0，进位 1
- 处理剩余进位 1 → 结果头部补 1，最终得 "10101"
三、两种高效实现方法（Python）
方法一：模拟竖式运算（易理解，推荐入门）
思路：从字符串末尾（二进制最低位）开始，逐位计算，记录进位，最后反转结果（若有进位需补 1）。
def add_binary(a: str, b: str) -> str:
i, j = len(a) - 1, len(b) - 1 # 指针指向最低位
carry = 0 # 进位初始为 0
result = []
while i >= 0 or j >= 0 or carry > 0:
# 提取当前位的值（越界则视为 0）
val_a = int(a[i]) if i >= 0 else 0
val_b = int(b[j]) if j >= 0 else 0
total = val_a + val_b + carry
current_bit = total % 2 # 当前位结果
carry = total // 2 # 更新进位
result.append(str(current_bit))
i -= 1
j -= 1
# 结果是逆序存储的，需反转
return ''.join(reversed(result))
代码解析：
- 指针 i、j 分别遍历两个二进制字符串的最低位到最高位；
- 循环条件包含 carry > 0，确保最后一位进位被处理（如 a="1111"、b="1111" 需补进位 1）；
- 用列表存储结果比字符串拼接更高效（Python 字符串不可变，拼接会创建新对象）。
方法二：位运算（进阶，无算术运算依赖）
利用二进制的位运算特性，避免直接转换为整数（适用于超长二进制字符串，避免溢出）。核心是用异或、与运算分别处理 “无进位相加” 和 “进位”。
原理：
- 无进位相加：a ^ b（相同为 0，不同为 1）；
- 进位计算：`(a & b) <（只有两位都为 1 才产生进位，左移 1 位表示进位到高位）；
- 循环直到进位为 0，此时异或结果即为最终答案。
def add_binary_bitwise(a: str, b: str) -> str:
# 转换为整数（Python 整数支持任意长度，无溢出问题）
x, y = int(a, 2), int(b, 2)
while y != 0:
# 无进位相加结果
xor = x ^ y
# 进位（左移 1 位）
carry = (x & y) < # 更新 x 为无进位结果，y 为进位
x, y = xor, carry
# 转换回二进制字符串，去掉前缀 '0b'
return bin(x)[2:]
代码解析：
- int(a, 2) 将二进制字符串转换为整数（Python 对大整数支持良好，无需担心溢出）；
- 循环中不断用异或结果替代原数，进位替代原第二个数，直到进位为 0；
- bin(x) 返回格式为 '0bxxxx'，切片 [2:] 去掉前缀得到纯二进制字符串。
四、性能对比与适用场景
实现方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
模拟竖式运算 | O(max(n,m)) | O(max(n,m)) | 超长二进制字符串（无长度限制） |
位运算（整数转换） | O(1) | O(1) | 常规长度二进制字符串（简洁高效） |
- 模拟竖式：不依赖整数转换，即使二进制字符串长度超过 1000 位也能正常运行，兼容性更强；
- 位运算：代码简洁，利用 Python 整数特性实现高效计算，但本质是依赖整数运算，若字符串过长（如 10^6 位），转换整数过程可能耗时。
五、常见边界案例测试
- 其中一个字符串为空：a="", b="1" → 输出 "1"
- 均为 0：a="0", b="0" → 输出 "0"
- 产生最终进位：a="111", b="111" → 输出 "1110"
- 长度不一致：a="10100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101" → 正常计算
六、总结
二进制求和的核心是 “逢二进一”，实现时可根据需求选择：
- 入门或处理超长字符串：优先模拟竖式运算，逻辑清晰且无长度限制；
- 追求简洁高效：位运算方法更优，利用 Python 整数特性简化代码。
实际开发中，需注意边界案例（如空字符串、进位残留），同时兼顾代码可读性与性能。如果需要处理超大长度的二进制数据（如区块链、加密算法场景），建议基于模拟竖式的思路优化，避免整数转换带来的性能损耗。