企业官网建设流程全解析

• 文档
• 教程
• 知识库

导读

67. 二进制求和（Add Binary）是 LeetCode 精选 300+ 刷题笔记中字符串分类下的一道 Easy 题目，也是"大数加法"这一高频面试考点的二进制形态：当数字的长度远超内置整数类型能表示的范围时，必须改用字符串/数组模拟竖式加法。本文以仓库中的原始 C++ 解法为骨架，完整继承题目、示例与实测数据，并在此基础上补充标准模拟解法、位运算解法、复杂度分析与边界条件总结，帮助你在笔试、面试中一次性吃透这类题目。

1. 题目回顾：输入输出与考点

题目给定两个二进制字符串，返回它们的和（同样用二进制字符串表示）。输入为非空字符串且只包含数字1和0。

示例 1：

输入: a = "11", b = "1" 输出: "100"

示例 2：

输入: a = "1010", b = "1011" 输出: "10101"

核心考点可以归纳为三点：

1. 大数溢出：字符串长度没有上限，"1"重复 1000 次时，任何内置整数类型都无法承载，因此必须用字符串模拟加法；
2. 二进制进位规则：满 2 进 1，这与十进制满 10 进 1 的唯一区别就是进位阈值；
3. 字符串与字符的算术转换：'1' - '0'得到数值 1，'0' + 1得到字符'1'，这是处理字符数字的通用技巧。

2. 思路分析：为什么不能直接转数字相加

最容易想到的方案是把两个字符串用stoi/stoll转成整数再相加，最后转回二进制字符串。但这一步在题目给出的输入规模下是不成立的：

• 二进制串长度超过 64 位时，long long已经溢出；
• 面试官考察本题的意图恰恰是手写逐位加法，与字符串处理能力直接挂钩。

正确思路与人类列竖式完全一致：从**最低位（个位）**开始逐位相加，同时维护一个进位carry，每一位的结果为(a_i + b_i + carry) % 2，新的进位为(a_i + b_i + carry) / 2。仓库笔记中记录的原始解法正是这一思路的实现，只不过它选择先用reverse把低位对齐到数组头部，从而免去从尾部反向遍历时对索引的繁琐控制。

3. 第一版解法：反转对齐 + 字符数组逐位进位

以下是仓库笔记67.二进制求和.md中记录的第一版（原始）解法，用 C++ 实现。笔记同时记录了当时的实测数据：

• 执行用时：8 ms，击败 48.84% 的 cpp 提交；
• 内存消耗：8.7 MB，击败 45.19% 的 cpp 提交。

string addBinary(string a, string b) { reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); if (a.size() < b.size()) swap(a, b); vector<char> res; int len = b.size(), minus = a.size() - b.size(); for (int i = 0; i < len; ++i) { res.push_back(b[i] - '0' + a[i]); // 重叠部分：字符 + 数值 } for (int i = len; i < len + minus; ++i) res.push_back(a[i]); // 长串多出的高位直接补上 for (int i = 0; i < len + minus - 1; ++i) { if (res[i] >= '2') { // 满 2 进 1 res[i + 1] = res[i + 1] + (res[i] - '0') / 2; // 向高一位进位 res[i] = '0' + (res[i] - '0') % 2; // 本位保留余数 } } string result; for (auto& a : res) result += a; reverse(result.begin(), result.end()); if (result[0] > '1') { // 最高位仍需进位 result[0] = result[0] - 2; result = '1' + result; // 在前面补一个 1 } return result; }

3.1 分步拆解：为什么这样写

第一步（对齐低位）：reverse两个字符串，让个位落在下标 0。例如a = "1010"反转后是"0101"，这样a[0]与b[0]恰好是同一数位，后续遍历即可从低到高同步进行。

第二步（归一化长度）：if (a.size() < b.size()) swap(a, b)保证a始终是较长者。随后len = b.size()是重叠部分的位数，minus = a.size() - b.size()是a独有的高位位数。

第三步（合并两段）：先对重叠部分执行res.push_back(b[i] - '0' + a[i])——注意这里把b[i]转成数值（'1' - '0'得 1）加到字符a[i]上，结果可能是'1'、'2'，甚至后续进位后会变成'3'；再把a剩余的高位原样追加。此时res中每个元素都是字符，且值域为'0'~'3'。

第四步（低位向高位传播进位）：遍历0到len + minus - 2（不含最高位本身），只要当前位>= '2'就进位：

• res[i + 1] = res[i + 1] + (res[i] - '0') / 2;——二进制满 2 进 1，当前位为'2'时商为 1、为'3'时整数除法3 / 2仍为 1，恰好都向高位加 1；
• res[i] = '0' + (res[i] - '0') % 2;——'2'取余得 0、'3'取余得 1，本位留下余数。

第五步（处理最高位可能的溢出）：所有进位传播到最高位后，若翻转后的result[0]仍> '1'（说明最高位产生了一个新的进位），就把它减 2 归位，并在最前面补字符'1'。

3.2 用示例验证流程

以a = "11", b = "1"为例：

3.3 复杂度分析

• 时间复杂度：O(n + m)，其中n、m分别为两个字符串的长度。反转、合并、进位传播、翻转各是一趟线性遍历，总开销与较长串的长度成正比。
• 空间复杂度：O(max(n, m))，结果容器res与结果串result各占与较长串同量级的空间，未使用额外的大规模存储。

4. 补充解法一：标准模拟法（从右往左 + carry 变量）

相比反转对齐，更常见、也更易读的写法是直接从字符串尾部向左遍历，用一个carry变量贯穿全程。它在可读性上更胜一筹，也是面试中最推荐优先表达的版本：

string addBinary(string a, string b) { int i = a.size() - 1, j = b.size() - 1; int carry = 0; string result; while (i >= 0 || j >= 0 || carry > 0) { int sum = carry; if (i >= 0) sum += a[i--] - '0'; if (j >= 0) sum += b[j--] - '0'; result += char('0' + sum % 2); carry = sum / 2; } reverse(result.begin(), result.end()); return result; }

要点说明：

• 循环条件i >= 0 || j >= 0 || carry > 0天然覆盖"一长一短"与"最后还有进位"两种边界，无需单独处理；
• sum的取值范围是 0~3，sum % 2是当前位、sum / 2是进位，与原始解法中的进位公式完全等价；
• 结果按低位到高位依次追加，最后一次性reverse即可。

两种写法在算法思想上等价：仓库原版是"先反转、后进位"，标准模拟法是"从右往左、边加边进位"，都可直接 AC。

5. 补充解法二：位运算思路（了解即可）

二进制加法的另一个本质视角是位运算：a + b可以拆成"无进位加法和"与"进位"两部分——a ^ b得到无进位和，(a & b) << 1得到需要继续传递的进位，两者相加（可能再次产生进位）直到进位为 0。写成循环如下：

string addBinary(string a, string b) { // 先将二进制字符串转为数值再做位运算（适用于长度不超长的情况） long long x = stoll(a, nullptr, 2); long long y = stoll(b, nullptr, 2); while (y != 0) { long long carry = (x & y) << 1; x = x ^ y; y = carry; } // 将结果转回二进制字符串 string result; if (x == 0) return "0"; while (x > 0) { result += char('0' + (x & 1)); x >>= 1; } reverse(result.begin(), result.end()); return result; }

这种解法在概念上很优雅，但要注意：它受限于内置整数类型的位宽，超长输入时依然会溢出。因此它更适合作为理解"异或 = 无进位加、与 + 左移 = 进位"这一本质的辅助手段，真正的通用解法仍应以字符串模拟为准。

6. 易错点与边界情况清单

7. 举一反三：大数加法的同源题目

二进制求和属于"大数加法"这一家族，仓库刷题笔记中与其思路高度同源的题目还包括：

• 989. 数组形式的整数加法：整数K与数组形式的数字逐位相加，同样是"低位对齐 → 逐位求和 → 处理进位 → 反转"四部曲，笔记中记录了从第一版到第三版的渐进优化过程，与本题的进位处理逻辑完全一致；
• 字符串分类下的其他题目，如13. 罗马数字转整数等，可参考字符串分类目录系统刷练。

如果进一步延伸，把二进制换成十进制（如415. 字符串相加），只需把进位阈值从2改成10，其余流程一字不改——这正是"逐位模拟 + 进位"模板的普适性所在。面试中常把这类题目作为考察候选人"能否把竖式加法正确地翻译成代码、并处理好边界"的试金石。

8. 总结

67. 二进制求和是一道以字符串为载体的经典大数加法题。仓库笔记中的第一版解法采用"反转对齐 + 字符数组逐位进位"，其res[i + 1] += (res[i] - '0') / 2与res[i] = '0' + (res[i] - '0') % 2两句，本质上就是二进制"满 2 进 1"的紧凑表达；而标准模拟法用carry变量把同一逻辑写得更加直观。两类写法的时间复杂度均为O(n + m)，空间复杂度均为O(max(n, m))。掌握这道题，就掌握了字符串大数运算这一类题目的核心模板，无论是校招还是社招面试都能举一反三。

本文内容整理自阿秀的精选力扣 300+ 道算法题刷题笔记，该系列按照 13 个标签（数组、字符串、链表、数学、哈希表、二分查找、栈、双指针、贪心、回溯、动态规划、DFS、树）分类，每个标签下再按 Easy / Medium / Hard 三个等级组织，适合校招、社招以及转行求职者参考；不了解如何上手刷题的话，可先阅读基础算法部分的使用说明。

• 文档
• 教程
• 知识库