手写大数相加，几乎是 C++ 面试里的固定节目。无论是校招还是社招，面试官总喜欢让你在白板上实现一个 addStrings 函数，输入两个可能长达上百位的数字字符串，输出它们的和。你要是没提前琢磨过里面的门道，现场硬写很容易翻车——不是漏了最后一位进位，就是忘了处理字符串长度不一致的情况。
抛开面试不谈，大数相加这玩意儿在真实项目里也不是摆设。RSA 加密、大整数运算库、金融系统的高精度计算、某些科学计算场景，底层都离不开超过 64 位整数表示范围的计算。别以为 C++ 有 __int128 就能通吃，碰到几百位的数字照样歇菜。所以搞明白字符串加法背后的原理，顺便把内存布局的账算清楚，对你写高性能代码是有实打实帮助的。
这篇文章我不想只贴一段能跑的代码就完事。我会把大数相加从算法设计、字符串实现、容器选型到内存布局的完整链路都拆开讲一遍，最后再分享几个我实际调试中踩过的坑。内容适合正在准备 C++ 面试的人，也适合那些想深入了解 std::string、std::deque 内存行为的进阶学习者。只要你把这篇消化了，再遇到大数相关的题目或者工作场景，心里就有底了。
1. 大数相加的底层逻辑与设计思路
1.1 为什么大数相加必须先想清楚整数溢出
很多人一上来就纠结"用 string 还是 vector"，但实际上大数相加真正的起点是理解我们为什么要脱离原始整数类型。C++ 内置的 unsigned long long 最大也只能表示到 18446744073709551615，也就是 20 位十进制数。一旦数字超过这个范围，你再怎么折腾内置类型都会溢出。
有人会想到 __int128，这是 GCC 和 Clang 提供的扩展类型，能表示 39 位十进制数左右。但问题在于：一是它不是 C++ 标准规定的类型，换到 MSVC 环境编译就直接报错；二是在某些平台和编译选项下，__int128 的运算甚至会被降级成软实现，性能并没有想象中好；三是如果你需要处理 50 位、100 位甚至 1000 位的数字，__int128 也撑不住。
所以大数相加最稳妥的做法，就是让数字"脱离"内置类型，用容器来存储每一个数位。你在纸上算加法的时候，会从个位开始逐列相加并处理进位。大数相加算法的全部秘密，就是把你在小学学过的竖式加法翻译成代码。一旦你确定了这个思路，容器的选择就浮出水面了：我们需要一个能够按索引访问、能够从尾部或头部插入、能够方便地转换为可打印字符串的数据结构。
1.2 字符串加法 vs 数组加法：两种方案的取舍
常见的两种实现路径，一种是把大数存储在 std::string 里，另一种是存储在 std::vector<int> 或 std::vector<char> 里。两者各有各的适用场景。
用 std::string 的好处是直观。你输入的就是字符串，算完直接返回字符串，省去中间转换。而且 std::string 的底层内存布局是连续的，对 CPU 缓存友好，尾插 push_back 均摊 O(1) 复杂度。缺点在于，你存储的是 ASCII 字符 '0' 到 '9'，做加法时必须先减去 '0' 转成数字，算完再加回 '0'，这中间多了一步转换，但在大多数场景下这点开销完全可以忽略不计。
用 std::vector<int> 或者 std::vector<char> 存储数字值，好处是省掉了字符和数字之间的转换，而且每个元素可以直接参与算术运算。如果你要做压位优化，比如用一个 int 元素存储 9 位十进制数，那 vector<int> 几乎是唯一合理的选择。但坏处是你需要额外写序列化的函数来把它打印成字符串。
一个设计良好的大数加法模块，通常会把"存储表示"和"算法逻辑"解耦。也就是说，算法只关心"从低位到高位逐位相加"这个核心流程，至于底层是字符串还是整型数组，不应该影响算法的正确性。这也是我在后面推荐你封装 BigInt 类的原因——一旦把底层存储封装好，加法、乘法、比较大小就都可以统一实现了。
2. 字符串加法核心实现全拆解
2.1 竖式加法的代码化：字符转数字、对齐与进位
核心逻辑仔细拆开，其实只有三步：对齐、逐位相加、处理进位。
对齐这一步，很多人第一次写容易踩坑。字符串的高位在左边，低位在右边，比如 "123" 中 '1' 是百位，'3' 是个位。你从下标 0 开始遍历字符串，实际上是从高位往低位走。所以我们必须反向遍历，从最后一个字符开始。
逐位相加时，涉及三个要素：a 的当前位、b 的当前位、来自低位的进位 carry。结果位的公式是：
sum = digit_a + digit_b + carry
当前位结果 = sum % 10
新的进位 = sum / 10
这里我用的是十进制，所以模 10 除 10。如果你想扩展到其他进制，比如二进制、十六进制，只需要把 10 换成对应的 base 就行。这个思想在密码学和编码相关场景里很常见。
注意：这里的 digit_a 和 digit_b 必须是真正的整数值。如果字符串存储的是 ASCII 字符，你必须用 ch - '0' 来转换，千万不能直接用字符变量参与算术运算，否则你会算出完全错误的结果。
进位是竖式加法的灵魂。两个一位数相加最大也就 9 + 9 + 1 = 19，所以进位只能是 0 或者 1。这也是为什么我们不需要担心"进位超过 1"的情况。但如果你做乘法或者压位加法，进位就可能超过 1，那时候你就要用更通用的 sum / base 来处理。
2.2 从低位到高位的完整实现：一份可复用的字符串加法
基于上面的思路，我贴一份可以放到生产代码里的实现。这版代码做了三件事：先把两个字符串的指针分别移到末尾，然后从低位向高位循环相加，最后把结果字符串逆置回来。
#include <string> #include <algorithm> std::string addStrings(const std::string& a, const std::string& b) { std::string result; result.reserve(std::max(a.size(), b.size()) + 1); int i = static_cast<int>(a.size()) - 1; int j = static_cast<int>(b.size()) - 1; int carry = 0; while (i >= 0 || j >= 0 || carry != 0) { int digitA = (i >= 0) ? a[i] - '0' : 0; int digitB = (j >= 0) ? b[j] - '0' : 0; int sum = digitA + digitB + carry; result.push_back(static_cast<char>('0' + sum % 10)); carry = sum / 10; --i; --j; } std::reverse(result.begin(), result.end()); return result; }看到 reserve 那一行了吗？我提前预留了 max(a.size(), b.size()) + 1 的空间，原因是最多可能出现最高位进位，比如 "999" + "1" = "1000"，结果长度比最长的输入多一位。如果不 reserve，push_back 在容量不足时会触发重新分配和拷贝，虽然均摊 O(1)，但提前预留可以减少不必要的内存拷贝，在多次调用时差异还是很明显的。
这个实现的循环条件是 while (i >= 0 || j >= 0 || carry != 0)，而不是 while (i >= 0 && j >= 0)。前者能自动处理两个字符串长度不一致的情况，还能在最高位有进位时把 carry 也写进结果。如果你写的是 &&，那你就得在循环结束后额外判断 carry，非常容易漏。
2.3 前导零的坑：一个不能忽略的边界条件
我在评测别人代码的时候，发现一个极其常见的问题：函数能算对 "123" + "456"，但碰到 "001" + "2" 就会输出 "21" 或者 "003" 之类的东西。问题出在输入字符串可能带前导零。
从数学上讲，"001" 就是 1，所以 "001" + "2" 应该是 3。但如果代码里不对前导零做处理，把 '0' 当合法数字参与逐位加法，后面的算法依然能得到正确结果——注意，因为前导零加另一个数的前导零，结果也是 '0'，最终算完逆置回来可能是 "3" 而不是 "03"。理论上确实不会出错，但如果你把 "000" 和 "0" 相加，结果会是 ""，一个空字符串，这就错了。
所以我建议在函数入口做一次清理。如果你写的是工程代码，可以用 std::string 的 find_first_not_of 来跳过前导零；如果你只是想快速实现，也可以在输入进入函数前用一个 normalize 函数来处理。这个细节在面试场景里往往是区分"能手写"和"能写好"的分水岭。
3. 存储载体的选型：内存布局才是进阶分水岭
3.1 string、vector、deque 三者的内存布局差异
算法写到这里，"能跑"的目标已经达成了。但如果你的追求不止于此，想理解大数算法在底层容器上的表现差异，那就必须聊内存布局。
std::string 在绝大多数标准库实现下采用小字符串优化（SSO，Small String Optimization）。当字符串长度小于等于 15 字节（以 libstdc++ 为例）时，数据直接存储在对象内部的栈缓冲区里，不会触发堆分配；当字符串超过这个长度，才会在堆上分配一块连续的内存。这意味着，短小的大数加法（长度 15 以内）甚至不会产生堆分配，性能非常猛。
std::vector<char> 的内存布局相对"老实"，元素存储在连续的堆内存中，尾插效率高，随机访问性能好。但它没有 SSO 机制，哪怕你只存一个元素也会触发堆分配。如果你用 vector<int> 存大数，每个元素占 4 字节（int），同样的数字长度会比 char 多消耗 3 倍内存。当然，int 的好处是支持更大的"压位"基数。
std::deque 就更有意思了。它的存储是分段连续的：底层由多个固定大小的缓冲区（block）组成，deque 维护一个 map 结构来管理这些块。双端插入删除都是 O(1)，而且不像 vector 那样，在头部插入时不需要搬运所有元素。
3.2 为什么我坚持用 string 做加法结果容器
回到大数加法的具体场景，我个人的选择是：输入用 string，中间计算过程也用 string 来累积结果，最后直接返回 string。原因有三点。
第一是接口一致性。大数相加的输入输出都应该是字符串，因为大数没法用内置类型表示，字符串是最自然的信息交换格式。如果内部用 vector 存储结果，最后还得把 vector 遍历一遍转成字符串，多一次 O(n) 拷贝。
第二是尾部插入的效率。我们的竖式加法是从低位到高位往结果里追加字符的，这个操作天然适合 push_back。string 的 push_back 均摊 O(1)，并且由于 reserve 的存在，在已知结果长度的情况下可以做到零扩容、零拷贝。
第三是引用的便利性。如果你把结果存成 string，可以直接配合 std::reverse 完成逆置；如果你存成 vector<char>，也能做，但要多一次类型转换。string 作为 C++ 标准库里高度优化的类，短字符串走 SSO，长字符串走连续堆内存，整体内存访问模式对缓存很友好。实测下来，使用 string 的实现和手写 char 数组的实现性能差异并不大，但代码可读性和健壮性要高出很多。
3.3 deque 的分段连续：push_front 虽然方便，但别高兴太早
我记得在热词里看到有人专门搜过 std::deque 的内存布局。这个点确实值得展开讲，因为大数算法里有一个很自然的想法：与其最后用 reverse 逆置字符串，不如直接用 deque，从头部 push 结果，这样就不用反转了。
deque 的 push_front 确实是 O(1) 复杂度，但它不提供连续的内存保证。这意味着，如果你使用&d[0]来获取指向首元素的指针并当作数组遍历，行为是未定义的。在大数加法里，我们经常要对结果做进一步的操作，比如进位修正、截断、整体逆置，这些操作在连续内存上做很直接，在 deque 上做就非常别扭。
另外，deque 的内存开销也不小。每个 block 都会有一些管理信息，map 本身也要占用额外内存。如果大数长度只有几十位，deque 引入的额外内存和间接访问开销并不划算。我的结论是：单纯为了省掉一个 reverse 调用而引入 deque，是明显的过度设计。reverse 的复杂度是 O(n)，n 最多也就几千几万，这点时间成本在现代 CPU 面前根本不值一提。
真正适合 deque 的场景是双端队列本身的需求，比如滑动窗口最大值、任务调度等，而不是大数运算。当然，如果你在写一个通用的大数容器，需要频繁地在最高位插入新的大数位（比如做乘法时结果长度动态增长），那 deque 确实有它的用武之地。但这是特殊情况，不是默认选择。
4. 可复用的 BigInt 类设计：从算法到工程能力
4.1 负数、前导零、输入校验这些工程细节
面试常常止步于"能跑通相加"，但实际项目里没人给你保证输入的字符串是干净的。所以设计一个可复用的 BigInt 类时，我会把校验逻辑单独抽出来。
首先要处理的是符号。加一个 bool isNegative 标志位，把符号从数字部分剥离开来。字符串里可能有前导的 '+' 或 '-'，解析时要识别并剔除。如果两个数都是正数，直接调用 AddAbs；如果符号不同，就要转换成绝对值相减，再根据绝对值大小决定结果符号。这里还藏了一个细节点：判断两个字符串谁大谁小，不能只用 std::string 的字典序比较，因为 "123" 和 "45" 在字典序下 "45" > "123"，但长度上 "45" 短，实际的数值大小是 "123" 更大。正确做法是先比较长度，长度相同再逐位比较。
其次是前导零清理。比如输入的 "000123"，在做成数字后应该变成 "123"。如果输入是 "0000"，应该变成 "0"。这个 normalize 函数必须在一切运算之前执行，否则会产生多余的位，影响长度比较和后续运算。
最后是字符合法性校验。每一个字符必须是 '0' 到 '9'，否则直接抛出异常或者返回错误码。这一点在面对外部输入时尤其重要，谁都不知道用户会不会给你塞一个 "12a4" 进来。我在做金融高精度计算模块的时候，就是因为漏掉了这层校验，导致一个脏数据进入了核心计算流程，排查了大半天才定位到。
4.2 压位优化：让加法飞起来的关键技巧
假设现在数字长度不是几十位，而是十万位，你还会一个字符一个字符地加吗？显然不会。这时候就轮到压位优化出场了。
基本思路是：不再用 char 存储单个十进制位，而是用一个 int 元素存储多个十进制位。我们常见的做法是每 9 位十进制数压进一个 int。原因很简单，int 最大能表示 2147483647，如果 base 取 1000000000（10 的 9 次方），两个 9 位数相加再加上最大进位 1，最大值是 1999999999，刚好在 int 范围内不会溢出。
具体实现时，先把字符串从低位开始每 9 位切成一组，转成 int 存进 vector<int>。加法过程从低位往高位按"组"运算，每一组做的是 int 的直接相加，然后处理进位。由于每组内聚了 9 位十进制数，循环次数直接缩小到原来的 1/9，实测性能提升非常可观。下面的示意见代码：
vector<int> toIntVector(const string& s) { vector<int> v; const int base = 1000000000; // 10^9 int i = (int)s.size(); while (i > 0) { int start = max(0, i - 9); string group = s.substr(start, i - start); v.push_back(stoi(group)); i = start; } return v; // v[0] 是最低组 }这里的注意点是，每一组转 int 时不能用 atoi，因为它不会严格检查边界。推荐使用 stoi 并配合异常捕获，或者手写一个安全的字符串转整数辅助函数。压位版本虽然写起来复杂一点，但速度上的提升是实打实的。我做一个 1000 位的加法测试，普通字符逐位加法和压位加法的耗时差距几乎在一个数量级。
4.3 扩展到乘法：加法思想如何复用到更多运算
大数加法是基础，但如果你掌握了它的设计思路，扩展到乘法并不难。乘法本质上就是重复的加法，但更高效的基本实现是"逐位乘法 + 错位相加"。
核心思路是：a 的第 i 位乘以 b 的第 j 位，结果要加到结果的第 i + j 位上。这里的位不再是十进制位，而是压位后的组。乘法过程中会产生比加法大得多的中间值，所以跨组进位处理要格外小心。
vector<int> multiplyBigInt(const vector<int>& a, const vector<int>& b) { vector<int> result(a.size() + b.size(), 0); for (size_t i = 0; i < a.size(); ++i) { long long carry = 0; for (size_t j = 0; j < b.size() || carry; ++j) { long long cur = result[i + j] + a[i] * (j < b.size() ? b[j] : 0) + carry; result[i + j] = static_cast<int>(cur % 1000000000); carry = cur / 1000000000; } } while (result.size() > 1 && result.back() == 0) result.pop_back(); return result; }注意到我用 long long 来存中间乘积，因为 int 的乘法结果很容易溢出。这也是"知其所以然"在工程里的体现：每个类型的选择背后都有对应的数据范围考量。如果你只背模板不思考边界，很容易在乘法里用 int 存中间的积，导致不可预知的错误。
5. 踩坑实录与排查技巧
5.1 字符数字混淆、进位遗漏、逆置顺序
我先说一个我见过无数次的错误，就是把字符直接当数字参与运算。有人写digitA = a[i]，然后看到结果完全对不上，抓耳挠腮半天不知道错在哪。正确的做法是a[i] - '0'。在 ASCII 编码里，'0' 的十进制值是 48，所以'0' - '0' = 0，'9' - '0' = 9。这一步一旦漏掉，后面所有计算都全乱了。
进位遗漏是第二个高发错误。有个经典案例是计算 "999" + "1"，两个数字长度差很多，循环如果写成while (i >= 0 && j >= 0)，当较短的数字遍历完之后，循环就提前结束了。但此时进位可能还没有处理完，结果就会是 "990" 而不是 "1000"。我建议循环里显式包含carry != 0这个条件，宁可多算一轮也不能丢进位。
逆置顺序这个坑相对隐蔽。如果你在循环里直接result += (sum % 10) + '0'，结果是按从低位到高位的顺序存储的，比如 "123" + "456" 的结果会存成 "975"。你必须对结果做一次 std::reverse 才能得到正序的 "579"。很多人记得要 reverse，却忘了应该在最终 return 之前 reverse。如果 reverse 之后又做了任何 push_back 操作，顺序又要乱了。建议在最终返回前的一行做 reverse，并且养成注释的习惯。
5.2 参数传递的性能坑与常引用习惯
大数相加的输入可能是几千位的字符串，如果你用传值的方式接收参数，会产生至少一次完整拷贝。拷一个几千字符的字符串倒是不慢，但万一你在循环里调用了很多次，这种拷贝开销就会累积。
正确做法是使用const std::string&来传递参数，既避免了拷贝，又能防止在函数体内意外修改原始数据。同理，返回结果时不要担心返回值拷贝的问题。现代 C++ 编译器有 RVO（Return Value Optimization）和移动语义，返回局部 string 对象是高效的，不会产生多余的深层拷贝。
还有一个隐藏在细节里的性能问题：在循环内部访问字符串的字符时，应该使用a[i]而不是a.at(i)。at()会做越界检查，如果越界会抛出 std::out_of_range 异常，这个安全机制是有代价的。在算法核心部分，我们应该已经通过条件判断保证了索引不会越界，所以直接用operator[]是安全且高效的。当然，如果你是在写一个需要强安全保证的对外接口，则可以保留 at() 或在前置条件里做严格校验。
5.3 面试与代码评审中的加分写法
最后分享一下我在评审别人代码和模拟面试中总结出的几个加分点。这些细节不会直接改变算法的正确性，但能体现你对 C++ 语言和工程实践的掌握程度。
第一，加了 reserve 预分配。前面提到过，reserve 可以避免多次扩容。面试官往往不会一眼看到这个细节，但当他问起的时候，你能把内存分配的机制讲清楚，这就是加分项。
第二，用 enum 或者 constexpr 定义进制常量，而不是硬编码 10。万一产品经理想改成 16 进制，一行改动就能实现。推荐在类里加一个static constexpr int BASE = 10;的常量。
第三，把核心算法声明成 static 函数，隐藏内部实现细节，只暴露必要的接口。缩小的外部可见面，本身就是可维护性的体现。我见过很多大数类把所有辅助函数都声明成 public，类接口一坨复杂，这会让后续维护的人头大。
第四，在代码评审时，主动说出"这个算法时间复杂度是 O(max(m, n))，空间复杂度是 O(max(m, n))"这两句话。别看简单，很多人真的说不利索。一个能清晰分析算法复杂度的人，面试观感完全不一样。
我在实际使用中还有一个体会：大数相加看起来很简单，但它牵扯到的知识点密度非常高——ASCII 编码、类型转换、边界处理、容器内存布局、复杂度分析、压位优化、参数传递语义。任何一环没吃透，都可能在某个细节上卡壳。如果你能把这一道题讲明白，说明你对 C++ 底层和算法基础都有了一个比较扎实的掌握，这是后续深入学习的很不错的抓手。
