C++高精度算法实现：从vector存储到加减乘除的完整思路

做算法题做久了你会发现一个挺反直觉的现象C 里long long明明已经是 64 位有符号整型却经常被一些看似不起眼的题目卡住。比如计算 100 的阶乘、斐波那契数列的第 200 项或者把两个 100 位的数字加在一起内置整型直接溢出。高精度算法就是为了突破整型限制而存在的那套手写大数运算核心思路说白了就是回到小学竖式在 C 里把每一位数字存进数组然后用加减乘除去模拟人工计算的过程。这篇文章我把它拆开讲清楚存储怎么设计、进位怎么处理、加减乘除代码怎么写以及我在实际调试里踩过的坑。适合正在备赛的算法竞赛学生也适合想搞懂大数运算底层原理的 C 入门者。1. 高精度算法的整体设计与思路拆解1.1 内置整型是怎么被“突破”的先看一组实际数字long long能表示的最大有符号整数是 9223372036854775807也就是大约 9.2 乘以 10 的 18 次方。对于很多业务场景这个范围足够用可一旦涉及阶乘、大数乘法、密码学里的模运算这个上限立刻变成瓶颈。举个最经典的例子20!是 2432902008176640000已经接近long long边缘到了21!就直接溢出成负数了。这时候如果你还在用内置整型要么换语言要么就得自己实现高精度算法。所谓高精度算法本质上是用一个数组或容器来模拟一个更长的整数。数组里的每个元素代表十进制下的一位数字通过自定义的加减乘除函数把“进位”“借位”“对齐”这些细节全部接管过来。这样做的结果是你不再受 64 位寄存器的限制理论上只要能分配内存就能计算任意长度的整数。这也是为什么它经常出现在算法竞赛里被当成一种必须掌握的“基础数据结构”。1.2 存储方案为什么是 vectorint 加小端序存储大数有很多种做法我见过有人用string、有人用char[]、有人用dequeint但最稳定、最省心的方案还是std::vectorint。原因其实很朴素vector支持随机访问尾部插入效率高而且配合std::reverse和std::to_string用起来非常顺手。这里有个关键的设计决策——顺序问题。我们习惯把数字从左往右写最高位在最前面但高精度运算的代码里我强烈建议采用“小端序”也就是索引 0 存放个位、索引 1 存放十位、索引 2 存放百位以此类推。这一点特别重要因为加法、减法、乘法都需要从最低位开始往前算进位也是从低位往高位传播的。如果你把高位放在索引 0每次进位都得做整体移位复杂度会变得很难看。反过来让低位在索引 0打印输出时再反过来遍历一次就行。用生活化的比喻来说这就好比做竖式加法。你先对齐个位逐列相加超过 10 就进一。存储上的“小端序”就是让你在程序里也能从左边的“个位列”开始处理不需要每次都把整串数字搬来搬去。1.3 为什么不用现成的大数库肯定有人会问C 里不是有boost::multiprecision、GMP 这种东西吗直接cpp_int不就完事了这个问题的答案是分场景的。在工程开发里我完全支持直接用现成库安全可靠不说性能还远超手写实现。但在算法竞赛、面试或者学习底层原理的场景中情况完全不同。很多评测系统不允许链接外部大数库boost::multiprecision虽然功能强大但并不是所有环境都默认支持而且有些判定还会限制头文件和编译选项。更关键的是高精度算法本身是一个极其经典的“数据结构 模拟”训练手写一遍能让你真正理解什么是进位、什么是借位、什么是复杂度而不是只会调库。所以我建议的做法是平时练习必须手写真正掌握后工程里再放心用库。2. 核心细节解析与实操要点2.1 字符串转数字数组解析和反转高精度算法的输入通常是一串特别长的数字这时候long long根本读不下必须先用string接收再逐个字符转换成数字。我习惯写成这样一个工具函数vectorint toBigInt(const string s) { vectorint a; int start 0; if (s[0] -) start 1; // 先处理负号本文主要讲非负大数 for (int i s.size() - 1; i start; --i) { a.push_back(s[i] - 0); } while (a.size() 1 a.back() 0) a.pop_back(); // 去掉前导零 return a; }这里有一个很多新手容易忽略的细节字符型数字减掉0之后得到的才是真正的整数值。7的 ASCII 是 550的 ASCII 是 48所以7 - 0 7。为什么大家都会在这一步犯错因为一旦你记成s[i] - 0或者干脆atoi(s[i])编译阶段就会报错或者得到莫名其妙的结果。别问我是怎么知道的。2.2 加法里的进位一轮循环搞定高精度加法是最容易理解的操作但恰恰是它的“进位”逻辑决定了你后面所有运算的写法。核心伪代码逻辑是这样的vectorint add(const vectorint a, const vectorint b) { int carry 0; vectorint result; int n max(a.size(), b.size()); for (int i 0; i n || carry; i) { int sum carry; if (i a.size()) sum a[i]; if (i b.size()) sum b[i]; result.push_back(sum % 10); carry sum / 10; } return result; }为什么sum % 10是当前位、sum / 10是进位因为十进制下每一位最大只能放 9超过 9 就要往高位移。sum的取值范围在 0 到 19 之间所以sum % 10落回当前位sum / 10最多也是 1。循环条件里加了|| carry这是为了处理最高位相加后产生新进位的情况比如999 1 1000如果循环只跑 3 次最高位的 1 就会被丢掉。这算是最常见的低级错误之一。2.3 减法里的借位与前导零清理减法比加法麻烦一点因为不仅要处理借位还要保证结果非负。我的做法是把减法拆成“比较大小”和“大数减小数”两层这样思路最清晰。vectorint subtract(vectorint a, const vectorint b) { // 调用方应当先保证 a b int borrow 0; for (int i 0; i a.size(); i) { int cur a[i] - borrow; if (i b.size()) cur - b[i]; if (cur 0) { cur 10; borrow 1; } else { borrow 0; } a[i] cur; } while (a.size() 1 a.back() 0) a.pop_back(); return a; }这里的技巧是“借位”不是先借再说而是先把当前位的值算出来如果小于 0就直接加 10同时把borrow置 1。为什么不提前判断因为提前判断会让代码多出一堆分支而且很容易漏掉“借位之后下一位还要再减 1”的连锁反应。先算后借的思路就是让系统自动完成这条链。清理前导零这一步是必须的。比如100 - 99如果没有最后那个while结果会变成001打印出来就成了“001”。虽然数值上没问题但会让后续比较大小、除法这些依赖数字长度的函数全部出错。2.4 比较函数一切高级运算的地基减法要保证a b除法要判断当前余数是否够除快速幂里比较大小也经常出现所以高精度比较函数必须写得又稳又快。int compare(const vectorint a, const vectorint b) { if (a.size() ! b.size()) { return a.size() b.size() ? 1 : -1; } for (int i a.size() - 1; i 0; --i) { if (a[i] ! b[i]) { return a[i] b[i] ? 1 : -1; } } return 0; }因为是小端序最高位在最后所以比较时必须从末尾倒着往前扫。先比长度是有道理的位数多的一定更大不需要逐位比较只有长度相同时才需要从最高位往下依次比较。这一点和字符串的字典序比较很像但要注意方向反了。3. 实操过程与核心环节实现3.1 完整可跑的高精度加减法代码理论说了这么多直接上完整代码。下面的实现里我把刚才的工具函数串起来写成一个简单的高精度运算类#include iostream #include vector #include string #include algorithm using namespace std; vectorint toBigInt(const string s) { vectorint a; for (int i (int)s.size() - 1; i 0; --i) { a.push_back(s[i] - 0); } while (a.size() 1 a.back() 0) a.pop_back(); return a; } void printBigInt(const vectorint a) { for (int i (int)a.size() - 1; i 0; --i) { cout a[i]; } cout \n; } vectorint add(const vectorint a, const vectorint b) { vectorint c; int carry 0; for (int i 0; i max(a.size(), b.size()) || carry; i) { int sum carry; if (i a.size()) sum a[i]; if (i b.size()) sum b[i]; c.push_back(sum % 10); carry sum / 10; } return c; } int compare(const vectorint a, const vectorint b) { if (a.size() ! b.size()) return a.size() b.size() ? 1 : -1; for (int i (int)a.size() - 1; i 0; --i) { if (a[i] ! b[i]) return a[i] b[i] ? 1 : -1; } return 0; } vectorint subtract(vectorint a, const vectorint b) { int borrow 0; for (int i 0; i a.size(); i) { int cur a[i] - borrow; if (i b.size()) cur - b[i]; if (cur 0) { cur 10; borrow 1; } else { borrow 0; } a[i] cur; } while (a.size() 1 a.back() 0) a.pop_back(); return a; } int main() { string s1 987654321987654321; string s2 123456789123456789; vectorint a toBigInt(s1); vectorint b toBigInt(s2); cout 加法结果: ; printBigInt(add(a, b)); if (compare(a, b) 0) { cout 减法结果: ; printBigInt(subtract(a, b)); } else { cout 减法结果: -; printBigInt(subtract(b, a)); } return 0; }实际跑一遍的话加法结果是 1111111111111111110减法结果是 864197532864197532。两个 18 位数相加结果轻松突破了常规整型的“体感上限”这就是高精度的意义。3.2 高精度乘法两层循环加统一进位乘法看起来复杂拆开之后其实也就三步先逐位相乘累加再一次进位最后清前导零。用竖式来理解就是你把第一个数的每一位分别去乘第二个数的每一位乘完之后对齐相加。代码实现如下vectorint multiply(const vectorint a, const vectorint b) { if (a.size() 1 a[0] 0) return vectorint{0}; if (b.size() 1 b[0] 0) return vectorint{0}; vectorint c(a.size() b.size(), 0); for (int i 0; i a.size(); i) { long long carry 0; for (int j 0; j b.size() || carry; j) { long long cur c[i j] carry; if (j b.size()) cur (long long)a[i] * b[j]; c[i j] cur % 10; carry cur / 10; } } while (c.size() 1 c.back() 0) c.pop_back(); return c; }这里有两个极其容易踩坑的点。第一a[i] * b[j]的乘积最大是 9 乘 9 等于 81但是如果直接用int存累加值在多次累加后很容易溢出尤其是在做“压位”优化时一不留神就是负数的乱码。所以我直接把cur声明成long long从根源上避免溢出。第二两层循环里c[i j]的下标为什么是i j因为大数的第 i 位和第 j 位相乘结果会落在第 ij 位上这是十进制乘法的基本对齐规则。如果下标写错得到的结果会是灾难性的。乘法的时间复杂度是 O(n²)n 是数字位数。对于 1000 位的数相乘大概要跑一百万次循环在竞赛环境下还能接受。如果想要更快的方案见后面压位优化。3.3 高精度除法逐位求商的模拟竖式高精度除法是四个运算里最费劲的一个因为它不像加减法那样好对齐也不像乘法那样有整齐的两层循环。我推荐的做法是“模拟竖式”也就是从最高位开始每次“拖”下来一位试试当前余数够不够除再逐位确定商。vectorint divide(const vectorint a, const vectorint b, vectorint remainder) { vectorint quotient(a.size(), 0); remainder.clear(); for (int i (int)a.size() - 1; i 0; --i) { remainder.insert(remainder.begin(), a[i]); while (remainder.size() 1 remainder.back() 0) remainder.pop_back(); int digit 0; int low 0, high 9; while (low high) { int mid (low high) / 2; vectorint mul multiply(b, vectorint{mid}); if (compare(remainder, mul) 0) { digit mid; low mid 1; } else { high mid - 1; } } quotient[i] digit; vectorint mul multiply(b, vectorint{digit}); remainder subtract(remainder, mul); } while (quotient.size() 1 quotient.back() 0) quotient.pop_back(); return quotient; }你可能好奇为什么这里要用二分法求商的一位。因为除法本质上是反复试探“当前余数最多能容纳多少倍除数”而对一位数字而言商只可能是 0 到 9所以直接二分 0 到 9 非常快。更朴素的做法是循环从 9 到 1 逐个试但二分法看起来更“聪明”代码也简洁。不过要提醒一句我这里为了主流程清楚调用了multiply和subtract这会让单次除法的时间复杂度偏高。如果比赛里对性能要求高可以改成“手动试商”或者整块减法但那是优化阶段该做的事。先保证正确再谈效率。3.4 压位优化从剥 10 到剥 1e9如果你只写到“每一位存一个 int”其实已经能解决绝大多数高精度题目了但你会发现一个问题内存占用高、循环次数多10000 位的数字跑起来很吃力。于是就有了“压位”的玩法。简单来说数组每个元素不再只存一位十进制而是存多位十进制。我比较推荐的压位方案是每格存1000000000也就是 1e9以内的数字即 9 位一压。为什么是 9 位而不是 18 位因为 1e9 小于int的最大值 2147483647单独存一格不会溢出而乘法累加时用long long接住也很安全。这样做的直接收益是同样一个 1000 位数原来要存 1000 个元素压位后只要存 112 个元素运算循环次数直接少一个数量级。压位后的加法进位逻辑要从% 10改成% BASE减法借位改成 BASE乘法列式也改成按块相乘。打印时是最容易出错的点除了最高位那一格其他每一格如果数值不满 9 位必须补前导零输出。比如某个格子里是 42直接输出 42 铁定错正确格式是000000042。这一块的调试经验就是写一个专门的格式化打印函数别偷懒直接遍历输出。3.5 完整主函数和测试验证一个没有测试验证的高精度代码等于没写。我的习惯是写一个主函数放几组手工可算的数据然后用 Python 的任意精度做交叉验证。比如int main() { vectorint a toBigInt(999999999999); vectorint b toBigInt(1); cout 加: ; printBigInt(add(a, b)); // 1000000000000 cout 减: ; printBigInt(subtract(a, b)); // 999999999998 vectorint c toBigInt(123456789); vectorint d toBigInt(987654321); cout 乘: ; printBigInt(multiply(c, d)); // 121932631112635269 vectorint remainder; vectorint q divide(d, c, remainder); cout 除: ; printBigInt(q); cout 余: ; printBigInt(remainder); return 0; }123456789乘以987654321的结果我背得特别熟是121932631112635269因为我拿它测过无数遍。一旦结果对不上问题多半出在进位、反转顺序、前导零这三件事上。测试时还要刻意挑边界全是 9 的大数、一长串零、结果恰好是 0这些都是最容易触发隐藏 bug 的样本。4. 常见问题与排查技巧实录4.1 反转顺序的锅个位到底放哪里我第一次写高精度的时候就是把数字原样存在数组里最高位在索引 0结果加法怎么跑怎么错。后来才明白低位放在索引 0 才是正解。这个错误的诡异之处在于如果你的数字是对称的比如121测试能过一旦数字不对称比如123 4结果就乱七八糟。排查方法很简单打印看看数组里到底存了什么比对着想象中该有的顺序改代码快得多。4.2 前导零清理不及时减法、除法、乘法结束后都容易出现前导零。比如1000 - 999 1如果不清理结果是0001后续再和1比较大小因为长度不一样compare函数会直接认为0001更大这就完全错误了。我建议把“清理前导零”做成一个独立小函数所有产生新向量结果的地方都调用一遍不要靠脑子记。void trim(vectorint num) { while (num.size() 1 num.back() 0) num.pop_back(); }4.3 乘法累加时的溢出陷阱只要不压位加法减法里的数都很小int完全够用。但乘法里a[i] * b[j]之后还要叠加上之前的进位和c[i j]的旧值就容易达到几百甚至几千。如果压位到 1e9累加量甚至能到 1e18 附近这时候int真的要爆。我在赛场上遇到过最尴尬的一次就是压位乘法跑了十分钟结果一验证发现全是负数第一反应是内存越界排查半天才发现是int溢出。从此之后我的原则是只要涉及乘法和压位累加一律用long long。4.4 除法的除数为零和商的位数除法最容易出错的场景是除数为零直接崩溃。实际题目里一般不会给这种数据但自己的测试代码里可能会不小心出现。我的做法是在divide函数开头加一个检查如果b.size() 1 b[0] 0直接抛异常或打印错误。另一个容易忽略的点是商的长度可能比被除数短很多比如1000 / 500 2。由于我的循环固定从被除数的最高位跑到最低位生成的quotient长度和被除数一样但高位都是 0所以最后必须做一次trim否则打印会得到0002。4.5 调试高精度代码的黄金对照法高精度算法最怕的就是“看起来很对但答案差一点”。我的调试方法是三层对照。第一层找几个手工能算的简单样例比如99 1、100000 - 1、123 * 456跑一遍确认主流程没大问题。第二层用 C 内置整型算一遍随机小数据再用我的高精度代码跑一遍对比结果。// 随机小规模对照示例 long long a_val 12345, b_val 6789; vectorint a toBigInt(to_string(a_val)); vectorint b toBigInt(to_string(b_val)); vectorint c multiply(a, b); long long expected a_val * b_val; // 再把 vector 转回 long long 对比第三层如果身边有 Python直接用 Python 的int当裁判生成几组随机大数打印 Python 结果和你 C 结果逐一对比。这当然不能直接提交到评测系统但作为本地验证工具效率极高。5. 进一步扩展高精度不只加减乘除最后再聊几个高精度相关的扩展方向这些内容我在比赛和实际工程里都用得上。第一个是“高精度快速幂”。当指数很大时普通循环乘法会超时这时就要把快速幂的思路搬过来只不过把“底数”和“结果”都换成高精度向量。核心公式是result result * base或base base * base指数按二进制位移逐步处理。代码写起来其实就是把long long换成vectorint操作符替换成自己写的multiply。第二个是“高精度斐波那契数列”。斐波那契数列增长极快第 100 项就已经超过long long范围第 1000 项更是天文数字。用高精度加法就能轻松算出。这里要提醒的是千万别用递归否则光是函数调用栈就能把自己压垮。直接写成迭代反复调用add就行。第三个是“大数阶乘的压位优化”。阶乘是典型的“越算越大”场景在 10000 的阶乘面前不压位的高精度几乎跑不动。解决方案就是在前面讲的压位 1e9 基础上用乘法循环累乘同时把中间结果尽量保持在数组长度较短的状态。这里有个经验是10000!的十进制位数大概是 35660 位不压位需要 35660 个 int压位后只需要 3962 个元素内存和循环次数都大幅下降。说实话高精度算法的实现细节并不难难的是把它写对、写稳、写成自己能快速调用的工具。很多选手在赛场上不敢写高精度就是怕代码太长、bug 太多。我个人的体会是与其抱着一堆库函数做重复劳动不如把一套干净利落的高精度模板背下来再配合完善的测试样例遇到大数题直接秒套。这个模板一旦建立起来后续的快速幂、进制转换、同余运算都能在此基础上快速扩展。