C++高精度算法从入门到实战：突破整型上限的大数运算模板

C++里搞高精度算法，说白了就是绕开 int、long long 这些内置整型的长度限制，用数组、字符串或者 vector 把大数拆开一位一位存，再按手算竖式的思路模拟加减乘除。不少入门的朋友一听到“突破整型限制”就觉得是是什么高大上的数学技巧，实际上它就是一组“用空间换范围”的工程手段。今天这篇东西，我直接以 C++ 为语言环境，从存储结构讲起，把加、减、乘、除、阶乘、快速幂这套完整过一遍，顺便把我在调试和性能优化时踩过的坑也一并记录下来。文章适合刚学 C++、准备算法竞赛，或者工作中偶尔要处理超大整数运算的开发者，看完你至少能自己写一份能跑、可扩展的高精度模板。

1. 整型的上限与高精度算法的设计逻辑

1.1 内置整型到底能存多大

C++ 里内置整型的范围是很多人容易忽略的“隐形天花板”。int 通常是 32 位，范围是 -2147483648 到 2147483647，也就是最多 10 位数；unsigned int 翻一倍，但还是只有 42 亿多。long long 一般是 64 位，能到 9223372036854775807，看着挺大，其实也就 19 位数。我们再看两个实际场景：100 的阶乘大约有 158 位；斐波那契数列第 100 项已经超过 20 位数；RSA 加密里要处理的模数动辄 1024 位以上。这些数字靠 long long 根本装不下，强行用 double 又会有精度丢失。

所以高精度算法干的事情，就是“拆数”。把一个 100 位的大数拆成 100 个 0 到 9 的数字，按顺序放进数组里，再用我们小学就学过的竖式方法做运算。单个数字的运算永远不可能溢出，每一位的进位和借位也都是小范围操作，这样整体上就突破了内置整型的限制。

这里顺便说一句，很多人问“用 Python 不就没这个问题了吗”。确实，语言层面自带大整数会省事很多，但 C++ 里你还是得懂这层逻辑。一方面算法竞赛里 C++ 是大头，高精度是基本功；另一方面，自己手写一遍会让你彻底明白计算机是怎么处理超出字长的数值的。面试时被问到“大数相加怎么实现”，本质考的就是这个。

1.2 数组模拟竖式的核心思想

高精度最核心的两个设计决策：用什么结构存数，以及为什么低位放在数组前面。

我用的是vector<int>配合“低位在前”的存储方式。举个例子，整数 12345 存进数组时，顺序是[5, 4, 3, 2, 1]，a[0]是个位，a[1]是十位，依此类推。这样设计的理由是：加法和乘法产生的进位只会向高位扩散，也就是数组的下标越来越大。如果采用“高位在前”的存储，每次进位都得在数组头部插入元素，时间复杂度会退化到 O(n)，很痛苦。低位在前，进位就变成了push_back操作，摊还复杂度是 O(1)。

有人可能会建议用字符数组或者string存储，字符串的好处是不用处理输入时的大小写转换，直接从'0'减到0就行。但字符串做中间运算时，进位和借位要反复修改字符，而且下标处经常出现需要转换成数字的麻烦。实战下来，vector<int>是最顺手的，因为元素本身就是整数，加减运算不用做 ASCII 转换，而且后面做压位优化时，一个元素可以直接存 0 到 9999 的大数，用vector<int>天然支持这种改造。

还有一个细节：高精度算法里，数字 0 的表示要统一。我习惯用vector<int>只存一个 0。减法、除法做完后如果结果全部为 0，至少保留一个元素，避免输出空字符串。这个边界问题在后面会反复出现。

2. 基础运算的全实现：字符串转数组、加法、减法

2.1 从字符串到高精度数组的读写

在做任何运算前，先要解决两件事：把输入字符串转成高精度数组；把高精度数组转回字符串输出。这两步看着简单，但不少 bug 都埋在这。下面这段代码我用了很久，逻辑非常直接：

#include <bits/stdc++.h> using namespace std; // 字符串 -> 高精度数组（低位在前） vector<int> load(const string& s) { vector<int> a; for (int i = s.size() - 1; i >= 0; --i) { a.push_back(s[i] - '0'); } if (a.empty()) a.push_back(0); return a; } // 高精度数组 -> 字符串（去掉前导零） string to_string_big(const vector<int>& a) { int pos = a.size() - 1; while (pos > 0 && a[pos] == 0) --pos; // 至少保留一位 string res; for (int i = pos; i >= 0; --i) { res.push_back(char('0' + a[i])); } return res; }

load里倒序遍历字符串，把每个字符转成数字后再push_back，这样低位天然就落在数组头部。to_string_big则从尾部高位开始找第一个非零元素，如果全部是 0，也保留最后一位，所以输出永远是“0”，不会输出空串。

这里我要提醒一个容易出错的地方：如果你从键盘读入的数字本身就带换行、空格或者是有符号的负号“-”，上述load函数会因为无法处理符号而错乱。我的做法是：读入整体字符串后先判一下首位是不是-，如果是就单独记录符号标记，再把剩余部分传入load。后面的比较、减法也已经考虑了符号维度，但在基础模板里可以先只做非负数，避免一上来就被负号搞晕。

2.2 高精度加法：进位处理与模板

高精度加法是最容易上手的运算。原理就是竖式：从低位到高位，把两个数对应位相加，加上来自低位的进位，然后取个位作为当前结果位，十位作为下一位的进位。循环结束后，如果最高位还有进位，再补一位。代码写出来非常紧凑：

// 高精度加法：支持不同长度的 vector vector<int> add(const vector<int>& a, const vector<int>& b) { vector<int> c; int carry = 0; int n = max(a.size(), b.size()); for (int i = 0; i < n; ++i) { int sum = carry; if (i < (int)a.size()) sum += a[i]; if (i < (int)b.size()) sum += b[i]; c.push_back(sum % 10); carry = sum / 10; } if (carry) c.push_back(carry); return c; }

这个模板有两个关键点。第一个是sum % 10和carry = sum / 10这两个操作，在十进制下相当于取个位和取十位。如果以后要做 16 进制高精度，这里改成% 16和/ 16就行。第二个是max(a.size(), b.size())来确定循环次数，避免两个数位数不同时漏掉较长那个数的剩余位。我在新手期犯过的最臭错误就是循环写成a.size()，然后两个长度不等的数相加时，高的位直接被丢掉了。

调试小技巧：单测就用最野的边界值。0 + 0必须输出 0；99 + 1必须输出 100 而不是 00；9999999 + 1必须输出 10000000。这几个用例过了，加法基本就稳了。很多人在进位循环结束后忘了检查carry，直接返回结果，导致99+1=00，这是高精度加法里出现频率第一的错误。

2.3 高精度减法：比较大小、借位与符号处理

减法比加法复杂一点，原因在于借位和符号。竖式减法是从低位开始，如果当前位的被减数小于减数，就要向高位借 1。实现之前必须先判断谁大谁小，因为负数的竖式计算规则不是简单地“符号留给外面，内部始终用大的减小的”。

先看比较函数。因为高精度数组是低位在前的，比较大小的逻辑是先比长度，长度不同则长度大的数更大；长度相同再从最高位往低位逐个比较：

// 返回 true 如果 a > b bool greater_big(const vector<int>& a, const vector<int>& b) { if (a.size() != b.size()) return a.size() > b.size(); for (int i = a.size() - 1; i >= 0; --i) { if (a[i] != b[i]) return a[i] > b[i]; } return false; // 相等 } // 高精度减法，前提 a >= b，结果仍为非负数 vector<int> sub(const vector<int>& a, const vector<int>& b) { vector<int> c = a; // 拷贝一份，直接在拷贝上修改 int n = a.size(); for (int i = 0; i < n; ++i) { int cur = c[i]; if (i < (int)b.size()) cur -= b[i]; if (cur < 0) { cur += 10; if (i + 1 < n) c[i + 1]--; // 向高位借 1 } c[i] = cur; } // 去前导零 while (c.size() > 1 && c.back() == 0) c.pop_back(); return c; }

实际的带符号减法可以这样封装：先比较a和b，如果a >= b，结果符号为正，直接sub(a,b)；否则结果为负，就sub(b,a)后在输出层打负号。不要试图在sub内部做符号，会让代码变得非常难读。

减法里的一个坑：借位后高位可能变成负数，下一轮循环会继续借位，链条会一直传递下去。我写的循环里，第i位借位会影响c[i+1]，而i+1在下一轮会被再次处理，所以链条是通的。但如果循环顺序写反了，从高位往低位处理，就会出现“借位不知道借到哪里”的混乱。这个模块写过一次就别改了，我后来所有高精度工具类都直接复用这两个基本函数。

3. 乘除与进阶计算：从乘法到除法再到阶乘幂

3.1 高精度乘法：双层循环与统一进位

高精度乘法比加减法上了一个台阶，因为它不再是单纯的一位对一位，而是要处理两位之间的交叉乘积。原理还是竖式：把a[i] * b[j]的结果累加到结果的第i+j位。只不过这里我们不是每乘一步就立刻进位，而是先把所有乘积都累加到位上，最后统一处理进位。这样做的好处是减少进位次数，避免大量无意义的取模操作。

核心实现如下：

vector<int> mul(const vector<int>& a, const vector<int>& b) { int n = a.size(), m = b.size(); vector<int> c(n + m, 0); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { c[i + j] += a[i] * b[j]; } } // 统一处理进位 int carry = 0; for (int i = 0; i < n + m; ++i) { int val = c[i] + carry; c[i] = val % 10; carry = val / 10; } // 结果长度可能虚高，去掉前导零 while (c.size() > 1 && c.back() == 0) c.pop_back(); return c; }

注意细节：a[i] * b[j]的结果在极端情况下可能达到 9 × 9 = 81，累加多次后c[i+j]可能超过 100。在逐位存储的版本里，单个 c 的元素理论上最多是 81 × 长度，长度大了就可能溢出int。不过如果长度不超过两千万位，int 还是够的；但在压位版本里中间结果会非常大，所以我会用long long做统计或者分段处理。这里为了基础版清晰，先用 int，但在注释里标注这是需要注意的地方。

还有一个性能点：这个双层循环是 O(n*m)，当两个数都是 10 万位时，1e10 次乘法会慢到无法接受。所以高精度乘法后续通常要接 FFT 优化，我放到后面专门说。

3.2 高精度除法：除以单精度与除以高精度

高精度除法的实现通常分两类：除以一个小整数（单精度）和除以另一个高精度大数（大数除大数）。

除以单精度是最简单的一种，因为除数小，我们可以从最高位开始逐位处理：每次把当前余数乘以 10 再加上当前位的数字，然后除以除数，得到商的一位，剩下的作为余数带入下一位。这个逻辑和手算除法的试商过程一模一样。

// 返回商，同时通过引用的余数返回 vector<int> div_mod_single(const vector<int>& a, int b, int& remainder) { vector<int> q(a.size(), 0); long long rem = 0; for (int i = a.size() - 1; i >= 0; --i) { rem = rem * 10 + a[i]; q[i] = rem / b; rem %= b; } while (q.size() > 1 && q.back() == 0) q.pop_back(); remainder = rem; return q; }

这里我想提醒一个容易忽略的问题：如果被除数本身为 0，除完之后返回的q可能是空 vector 或者只有 0。上面的实现先把 q 初始化为a.size()大小，所以不会为空，然后去前导零也保证了至少保留一位。但如果a本身就是空 vector（这在我早期的模板里可能出现），就要在函数开头做兜底判断。

至于大数除大数，最自然的方式是模拟长除法，但实现起来繁琐。更实用的是二分答案法：对于a / b，答案 q 必然落在 0 到 a 之间，我们二分 q，然后用高精度乘法判断q * b是否小于等于a。这种算法复杂度是 O(n^2 log V)，n 是被除数位数，V 是商的大小范围。当位数不多时，它比手写长除法更不容易出错。

二分法代码思路大概是这样：

vector<int> div_big(const vector<int>& a, const vector<int>& b) { // 先处理特殊情况：b 为 0 直接报错，这里不演示这类错误分支 vector<int> low(1, 0), high = a; while (!greater_big(low, high)) { vector<int> mid = add(low, high); mid = div_mod_single(mid, 2, ?); // 高精度除以2，也可以直接用移位实现 if (greater_big(mul(mid, b), a)) { high = sub(mid, vector<int>(1,1)); // 不能在 mid 上直接改，要先拷贝 } else { low = add(mid, vector<int>(1,1)); } // 需要做终止条件判断，这里只是演示框架 } return low; }

严格来说这个二分框架里终止条件的处理要非常小心，尤其是 mid 和 low/high 相邻时要防止死循环。我的经验是：直接在高精度运算基础上再封装一个带幂次的比较函数，然后在循环结束时多验证一次。这种方案在笔试和面试讲思路时足够用，但它不是最优实现；如果你要在一个高负载项目里频繁使用大数除法，我更推荐去用成熟的大数库，比如 GMP。

3.3 经典应用：大数阶乘、快速幂与组合数

有了加、减、乘、除这些原语之后，就可以拼装出很多实用算法了。第一个经典应用是大数阶乘。比如计算100!，用 long long 存会溢出，用高精度乘法循环乘就行了：

vector<int> factorial(int n) { vector<int> res(1, 1); for (int i = 2; i <= n; ++i) { vector<int> factor; int t = i; while (t > 0) { factor.push_back(t % 10); t /= 10; } res = mul(res, factor); } return res; }

每次把当前结果乘以下一个数，由于 n 本身是普通整数，所以构造因子时只要用普通除法拆位即可。时间复杂度是 O(n^2) 量级，n 到 10000 时已经有点慢，但 n 小于 1000 时体验很好。竞赛里经常用这种方法算组合数 C(n, k)，因为阶乘取模的问题会牵扯到逆元，而不取模的大组合数直接高精度乘除也能做，只是要把所有中间结果都控制在高精度层面。

第二个经典应用是快速幂配合高精度。像计算2^100这种，直接循环乘 100 次就完事，但如果要算2^100000，就必须用快速幂。把指数拆成二进制，每次把底数平方，遇到当前位为 1 就把结果乘上底数。核心代码很短：

vector<int> fast_pow(vector<int> base, int exp) { vector<int> result(1, 1); while (exp > 0) { if (exp & 1) result = mul(result, base); base = mul(base, base); exp >>= 1; } return result; }

这个版本的 base 可以是高精度，exp 是普通整数。如果你要算的是高精度大数的幂，指数本身也是大数，那么快速幂依然适用，但指数的二进制拆位就需要额外处理。我一般把指数转成 uint64_t，如果指数位数超过 64 位就改用高精度存储并通过高精度除以 2 来遍历二进制位。

这类进阶组合的通用价值在于：高精度不是孤立的一两个函数，而是一个可以叠加的组合框架。你先把加减乘除这些原语写稳，阶乘、幂、组合数、取模就都成了简单拼装。我在实际比赛中最常用到的正好就是“高精度阶乘 + 高精度组合数 + 高精度取模”这套组合，Gym 题里的 Extended Big Number 总结基本都是这套模板。

4. 常见问题与性能优化实录

4.1 五个高频 bug 现场

高精度算法代码量不大，但出错的频率出乎意料地高。根据我自己的排错记录和帮别人 review 的经验，下面五种 bug 出现频率最高，我直接整理成表，方便你对照自查：

这五个 case 基本就是我在代码 Review 时最常圈出的地方。尤其是第一个“加法忘进位”，几乎每个从零手写高精度的人都要踩一次。我的建议是，每一个函数写完都要做一个极小的测试脚本，用十组以内的高覆盖用例跑一遍，不要等整套模板写完再统一调，那样定位 bug 的成本会高很多。

4.2 压位优化：让高精度运算更快

逐位存储虽然直观直观，但性能确实拉胯。数组长度大，循环次数多，vector 的内存访问也不够友好。如果要做大规模的阶乘、大数的乘法，我建议上压位。

压位的思路是把几个十进制位打包进一个int里，比如万进制，即每个元素存储 0 到 9999 的数字，这样数组长度直接减小到原来的四分之一。进位处理时用的是 10000 而不是 10，模运算和除法也相应地改成 10000。这样加、减、乘的循环次数都少了四倍，而且内存占用也小了，cache 友好度提升明显。

压位版本的关键在于输入输出。输入时不能一个字符一个字符地存，而是从字符串末尾每 4 个字符切一段，转成整数后作为数组的一个元素存储。输出时，除了最高位那段，其余每段必须用setw(4) << setfill('0')补零到 4 位，否则像“10000”这种数字会输出成“1 0 0”这种错位形式。

压位版 load 和输出示例：

vector<int> load_base10000(const string& s) { vector<int> a; int len = s.size(); for (int i = len; i > 0; i -= 4) { int start = max(0, i - 4); a.push_back(stoi(s.substr(start, i - start))); } if (a.empty()) a.push_back(0); return a; } string to_string_base10000(const vector<int>& a) { stringstream ss; ss << a.back(); for (int i = (int)a.size() - 2; i >= 0; --i) { ss << setw(4) << setfill('0') << a[i]; } return ss.str(); }

这里的stoi在字符串段是 4 位时不会溢出，最大 9999，安全。进位操作则把%10改成%10000，把/10改成/10000。乘法中间结果用 long long 存，因为a[i] * b[j]最大约 1e8，累加多次可能接近亿级别，但远小于 2^63-1，所以用long long做累加是安全的。

压位的增益我实测过：计算 30000! 时，逐位版本大约需要 4 到 5 秒，压位到万进制后大概在 1 秒内。这个提升主要来自循环次数减少和内存减小。如果你的比赛环境内存限制较严格，压位几乎是必然选择。

4.3 选型思考：什么时候用现成库

有些读者可能会问：“C++ 里不是有__int128，也有 Boost 的 multiprecision，还有 GMP，为什么还要手写高精度？”这个问题我认真想过，答案是看场景。

__int128是 GCC 和 Clang 的扩展，能直接存储 128 位整数，最大约 1.7e38，比 long long 大得多，运算速度也接近原生整型。但首先它不是标准 C++，换到 MSVC 环境下就不一定能用；其次 128 位的范围依然有限，一旦数值超过这个界限还是得回到高精度路线。所以我的习惯是：中间结果确认不会超过 128 位的，就优先用__int128，性能最好；一旦预估位数超过几百位，直接上自己写的高精度模板。

Boost.Multiprecision 的cpp_int和 GMP 都非常成熟，功能强大，GMP 甚至在某些大整数运算上比自己写的模板快几个数量级。但引入它们往往意味着依赖管理复杂度上升：比赛环境不一定预装 GMP，跨平台编译也更容易出问题。写业务代码时，如果只是偶尔算一个大数，用 Boost 是最省心的。但如果你想真正掌握算法原理，或者需要在比赛中一个压缩包跑完所有代码，手写高精度仍然是必备技能。

我把常见方案整理成一张对照表：

选型时不用纠结，原则就是“性能够用、依赖可控、代码可维护”。手写高精度虽然性能一般，但它最大的优势是零依赖，在任意环境都能跑。

4.4 扩展场景

高精度的应用不止算法竞赛。金融系统里金额计算为了避免浮点误差，常用十进制定点存储，本质上就是一种高精度，只是基数换成了分、厘这类单位；加密算法里 RSA、ECC 都有大量的大数高频运算；区块链、哈希碰撞检测也离不开大数处理。如果你以后在业务代码里碰到“这个数字用 int 存不下”“浮点精度无法接受”这类需求，高精度模板就是你的底层工具箱。

再延伸一步，当高精度乘法遇到百万位级的输入时，O(n²) 的手写竖式乘法会显得非常吃力，这时候就该引入 FFT（快速傅里叶变换）或 NTT（快速数论变换），把乘法的复杂度降到 O(n log n)。我在前文提过的手写模板在竞赛够用，但真做超大乘法时，还是建议去了解一下 FFT 版本的实现。这又是独立的一大块知识体系，但基础的高精度原语依然通用。

最后再分享一个我自己的习惯：高精度模板里的add、sub、mul、div_mod_single、greater_big这几个函数，我会全部做成独立函数并且参数都用const vector<int>&，绝不直接在原参数上修改。这样一个函数出问题时，单测可以精确定位到某一环，而不用在几十层调用之间来回追。加法和乘法之间可以组合出幂和阶乘，减法与比较、除法之间可以组合出取模和整数除，这套组合真的是算法比赛里最常碰的核心工具。

写高精度最容易犯的错是急着把整套代码写出来再调试。我现在的流程是：先写一个逐位版本，跑通所有基础用例，再去写压位版本；压位版本出问题时，用逐位版本去对拍，几乎立刻就能看出是输出格式问题还是进位逻辑问题。这个“双版本对拍”的方法帮我省了不知道多少排查时间，建议你也试试。