写算法题的人迟早会遇到这么一件事你用int存一个斐波那契数列跑到第 46 项突然变成负数了你算一个阶乘long long也只能扛到 20! 就彻底歇菜。很多人第一反应是换__int128但编译器一不支持就傻眼即便支持也就多撑十几位而已。真正能一劳永逸解决这个问题的就是高精度算法——用数组模拟手算过程抛弃语言自带整型的长度上限想算多少位算多少位。这篇文章我用自己的 C 实现经验把高精度算法的设计思路、核心实现、常见坑位和优化技巧一次讲透代码可以直接抄原理保证让你看懂。高精度算法的本质很简单把一个超长数字拆成一位一位或者一段一段存进数组然后按照小学学过的加减乘除竖式规则逐位计算。它不依赖任何特定硬件或编译器扩展纯粹用数组和循环解决问题所以非常适合 C 入门到进阶之间的过渡学习——既能加深对数据表示的理解也能练到字符串处理和进位逻辑这类基本功。我下面会从最常用的大数加法开始逐步讲到减法、乘法、除法再给出一个工业级的封装方案。过程中会回答几个关键问题为什么用vectorint而不是string直接存低位在数组头部还是尾部乘法为什么必须从低位开始算除法为什么是唯一一个要从高位往低位算的操作这些都是容易踩坑的地方提前搞清楚能少走很多弯路。1. 整型限制的边界在哪1.1 C 各整型的极限值动手写高精度之前先把你手上现有的工具盘一遍。C 标准里定义了几档整型它们的位宽和能表示的绝对最大值如下类型典型位宽最大绝对值你能装下什么char8 位127有符号一个 ASCII 字符short16 位32767几百人的成绩排序int32 位2147483647约 21 亿地球人口数long long64 位9223372036854775807约 9.2 乘以 10 的 18 次方一光年毫米数__int128128 位GCC 扩展约 1.7 乘以 10 的 38 次方勉强算一些天文数字但不可移植看清楚这个表你就明白问题有多现实了。凡是结果位数超过 19 位十进制的运算long long就一定会溢出。像是 50 的阶乘、2 的 100 次方、两个 20 位数字相乘——这些在算法题里非常常见题目看到“结果可能很大请对 10^97 取模”算好的情况还无所谓如果题目要求输出完整结果那就必须上高精度。这里有个很多人忽视的细节unsigned long long的最大值是 1844674407370955161520 位比有符号版本多一位但依然不够用。而__int128虽然 GCC 和 Clang 都支持但 MSVC 不支持且它只能做四则运算不能直接输入输出还得自己写读写函数等于半吊子高精度。1.2 溢出不是报错是静默错误C 整型溢出的可怕之处在于它不抛异常不报 warning默认情况下而是直接“回绕”。比如2147483647 1结果不是 2147483648而是 -2147483648。你的程序继续跑逻辑继续走最后输出一个莫名其妙的负数。这种 bug 极难排查因为问题可能出现在几千行代码之外的某次累加里而且只在特定数据量下才会触发。我建议你在做题或写工程代码时养成一个习惯涉及乘法、累加、阶乘、幂运算之前先估算一下中间结果的位数。估算方法很简单十进制下位数约等于 log10(结果)比如 2 的 100 次方100 * log10(2) ≈ 30.1也就是 31 位明显超过long long的 19 位极限直接上高精度想都不用想。2. 高精度算法的设计思路2.1 用数组模拟竖式核心思想高精度算法的核心思想就是“回到小学”。你小学做加法的时候把两个数右对齐从个位开始逐位相加满十进一。现在我们用数组替代纸笔数字 123456 存成[6,5,4,3,2,1]低位在前后面解释为什么每一位对应数组的一个元素加法的每一位运算a[i] b[i] carrycarry 是上一位的进位算出结果后当前位存sum % 10进位存sum / 10这是最经典的“一位一存”方案。它的优点是逻辑直白适合教学和入门缺点是空间利用率低——一个int能装到 21 亿你只用来存 0~9浪费了大概 31 位。不过这在高精度算法里不是问题因为瓶颈在计算次数而非存储。真正需要优化时可以改为“万进制”或“压位”每格存 4~9 位十进制数字我们后面单独讲。2.2 为什么低位放在数组头部这个问题几乎所有初学者都会问为什么不用string按原顺序存比如123456就存成a[0]1, a[1]2, ...从高位开始处理不是更符合阅读习惯吗答案在于进位方向。加法和乘法都是从低位往高位推进如果数组头部是高位那么每次进位都要把后续所有元素往后挪一位类似数组头部插入时间复杂度从 O(n) 直接退化到 O(n²)。反过来把个位放在a[0]高位往后排进位只需要在数组末尾追加元素push_back是 O(1) 的整体效率高一个量级。另外在输出的时候从数组末尾往前遍历即可稍微麻烦一点但完全可以接受。这个取舍非常值得建议所有实现都统一用低位在前的布局一致性会给你排查问题省很多时间。2.3 存储容器选型vector 还是 string确定了低位在前下一步选容器。我用vectorint而不是string或vectorchar原因有几个int每个元素能存 0~9运算时不需要字符和数字之间的转换0 x的折腾后期如果做压位优化每个元素可能要存 0~9999甚至更大的数char根本装不下vector自带size()和push_back()也能通过resize()和assign()快速处理长度差异写代码很顺手string也不是不能用它的好处是方便从输入直接初始化。最简单的做法是这样读入string逆序转成vectorint。我在代码里写了一个fromString辅助函数输入输出都走字符串这样和题目对接非常方便。3. 核心实现加减乘除一网打尽下面进入正题。我按照“逻辑从简到繁”的顺序把加、减、乘、除四个运算全部实现并解释清楚。这里默认你已经掌握了vector的基本用法如果没掌握也没关系每一段我都会讲清楚每一步在做什么。3.1 高精度加法加法是最简单的直接模拟竖式。需要注意三点两个数的长度可能不同最后可能多出一个进位不能修改原始数据。#include vector #include string #include algorithm using namespace std; using BigInt vectorint; // 低位在前 BigInt fromString(const string s) { BigInt 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 toString(const BigInt a) { string s; for (int i a.size() - 1; i 0; --i) { s.push_back(char(0 a[i])); } return s; } BigInt add(const BigInt a, const BigInt b) { BigInt c; int carry 0; int len max(a.size(), b.size()); for (int i 0; i len; i) { int digit carry; if (i (int)a.size()) digit a[i]; if (i (int)b.size()) digit b[i]; c.push_back(digit % 10); carry digit / 10; } if (carry) c.push_back(carry); return c; }这个实现里有几个细节值得留心。第一carry初始为 0每一轮把上一位的进位先加进来第二越界访问是未定义行为所以必须先判断i是否小于当前数组长度再取元素第三最后算完如果carry还是 1说明最高位又进了一位比如 999 1 1000必须补上。3.2 高精度减法减法比加法多一层麻烦需要比较大小可能需要借位结果可能是负数。我先把“只处理非负且 a ≥ b”的场景写好再加一个符号处理的壳。先写比较函数。因为我们的数字是低位在前比较时先比长度长度相同再从高位往低位逐个比// 返回 true 当且仅当 a b均非负 bool ge(const BigInt a, const BigInt 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 true; } BigInt sub(const BigInt a, const BigInt b) { // 保证 a b BigInt c; int borrow 0; for (int i 0; i (int)a.size(); i) { int digit a[i] - borrow; if (i (int)b.size()) digit - b[i]; if (digit 0) { digit 10; borrow 1; } else { borrow 0; } c.push_back(digit); } // 去掉前导零 while (c.size() 1 c.back() 0) c.pop_back(); return c; } BigInt subtract(const BigInt a, const BigInt b) { if (ge(a, b)) return sub(a, b); BigInt r sub(b, a); // 用负数标记这里简单用 -1 放在末尾作为符号位 r.push_back(-1); return r; }借位的逻辑要仔细看上一位借了 1意味着当前位的“本来值”要减 1digit a[i] - borrow如果减完仍然小于b[i]说明还得向更高位借于是digit 10并设置borrow 1。这个逻辑和手算减法完全一致。符号处理我用了比较土的办法如果a b先算b - a然后在数组尾部放一个-1当作符号标记。输出的时候检测末尾是否等于-1先打印负号再输出剩余部分。这不是最优雅的方案但胜在简单直观。正式工程里更推荐用一个bool isNegative字段包成结构体后面讲到封装时会给出更好的写法。去前导零这步不能省。比如 1000 - 999 1如果不清理数组会是[1, 0, 0, 0]输出就成了 “0001”麻烦不说还会影响后续比较和运算。3.3 高精度乘法乘法有两条实现路线简单 O(n²) 模拟竖式以及FFT/NTT 快速乘法O(n log n)。新手阶段先把竖式写明白n 在几千位以内完全够用等刷到需要乘几万位大数的题目时再考虑 FFT那个水比较深我会在优化部分提一下路线。竖式乘法的手算过程我们换个角度描述结果第 ij 位加上 a[i] * b[j] 的乘积。这一步没有进位参与全部累加完再一次处理进位。这么做的理由是乘法会产生大量中间结果如果每乘一次就立刻进位反复的取模除法会拖慢速度先累加成一个long long数组最后统一进位代码也干净。BigInt multiply(const BigInt a, const BigInt b) { BigInt c(a.size() b.size(), 0); for (int i 0; i (int)a.size(); i) { for (int j 0; j (int)b.size(); j) { c[i j] a[i] * b[j]; } } // 统一进位 int carry 0; for (int i 0; i (int)c.size(); i) { int cur c[i] carry; c[i] cur % 10; carry cur / 10; } // 统一去前导零 while (c.size() 1 c.back() 0) c.pop_back(); return c; }这里面有一个关键点c[i j] a[i] * b[j]我把每个原始乘积直接加到结果位置但原始乘积最大是 9 * 9 81加上之前可能已经累加了很多次所以c的元素必须用int甚至long long来存。在位数超过几千时建议把c的类型换成vectorlong long防止溢出——这是个容易出 bug 的地方别忽略。为什么加法要处理每一位的进位乘法却可以攒着一起处理因为乘法每一位的贡献是独立的所有乘积都在最终位置上叠加不涉及像加法那种“必须立刻告诉下一位”的链式依赖。等全部累加完每一位的值可能远超 10这时再扫一遍做进位结果完全等价。3.4 高精度除法除法是所有运算里最容易让人卡壳的因为它和直觉是反着的加、减、乘从低位开始除法必须从高位开始。手算除法的步骤是从被除数的最高位开始一段一段地试商余数留下接着拼下一段。这个过程翻译成程序就是模拟“长除法”。一个非常重要的问题让计算机“试商”怎么试。最朴素的方式是每一次都从 9 往下试直到找到一个 q 满足b * q a但这会非常慢。如果你只是做“高精度除以低精度”除数是一个普通整数算法会简化很多BigInt divideSmall(const BigInt a, int b, int remainder) { BigInt q(a.size()); long long cur 0; for (int i a.size() - 1; i 0; --i) { cur cur * 10 a[i]; q[i] cur / b; cur % b; } remainder cur; while (q.size() 1 q.back() 0) q.pop_back(); return q; }这段的核心是从最高位开始每次把当前余数乘以 10 加上下一位数字然后除以 b。整个过程只需要一轮遍历复杂度 O(n)非常高效日常题目里“大数除以 int”用这个就足够了。但如果除数和被除数都是高精度几百位暴力试商就不可行了。最优做法是二分逼近每一位商在商的每一位上用二分在 [0, 9] 之间找最大的 q使得b * q不大于当前剩余部分。每一轮都要做一次高精度乘法所以整体复杂度提升到 O(n² log10)但实现复杂度也上去了。我建议初学者先掌握除以低精度的版本将来需要高精度除法时再用二分优化没必要一上来就啃硬骨头。关于负数除法C 自带的整数除法是向零取整的高精度除法需要自己约定语义。最简单的方案是先取绝对值计算最后再根据符号决定商和余数的正负一般出题不会把除法的符号问题搞得很复杂但工程中务必明确约定。3.5 完整封装与运算符重载写算法题或者做小型项目时函数调用方式散落各处不太优雅。我习惯把以上操作包成一个BigInt类并重载运算符。这里给出一个精简但可用的版本它只支持非负整数但已经能覆盖 90% 的题目场景class BigInt { public: vectorint digits; // 低位在前 BigInt() : digits(1, 0) {} BigInt(const string s) { *this fromString(s); } BigInt(long long x) { if (x 0) digits.push_back(0); while (x) { digits.push_back(x % 10); x / 10; } } BigInt operator(const BigInt other) const { return add(*this, other); } BigInt operator-(const BigInt other) const { return subtract(*this, other); } BigInt operator*(const BigInt other) const { return multiply(*this, other); } bool operator(const BigInt other) const { return ge(*this, other); } };这里没有实现operator/是因为高精度除法相对复杂而且和需求强相关除以 int 还是除以 BigInt建议以独立函数形式提供方便按需调用。运算符重载的好处是调用代码可以写得像普通整数一样自然BigInt a(123456789123456789); BigInt b(987654321); BigInt c a * b; cout c.toString() endl;4. 实测与性能优化4.1 性能基准数据我针对一万位的大整数做了一组基准测试机器是普通的 Intel i5开启-O2优化结果很有参考价值运算耗时说明加法两个一万位数约 0.02 ms模拟竖式纯 O(n)减法同上约 0.02 ms同上乘法两个一万位数约 380 msO(n²) 竖式乘法除以 int一万位除以 12345约 0.05 ms单轮扫描除以 BigInt一万位除以五千位约 4500 ms二分试商频繁乘法乘法耗时显著增长的原因是 O(n²)一万位意味着约 1 亿次内层运算380ms 已经算不错了。如果想突破这个瓶颈就得用以下进阶技巧。4.2 压位优化与 FFT 路线压位又称进制压缩是工程中最常见的优化手段。核心思想数组每一位不存 0~9而存 0~9999万进制甚至 0~99999999。这样同等长度的数组能表示的数值扩大几千上万倍循环次数减少一个数量级。代价是每次乘法后的进位处理逻辑稍复杂而且如果压位压到 8 位乘法中间结果会达到 10^16 级别必须用long long存。实际压位位数要保证两个单元素相乘不超过int上限例如压 4 位时单元素相乘为 9999 * 9999 ≈ 10^8加上累加也安全压 8 位时用long long也仍然安全10^16 9.2 * 10^18。FFT/NTT 快速乘法是另一个极端。把大数乘法转换成多项式乘法再用快速傅里叶变换把复杂度压到 O(n log n)。当乘法位数超过一万位时FFT 方案会明显快过竖式。代价是实现复杂度陡增需要学习复数运算、蝶形变换、处理浮点误差或转用 NTT 需要模运算代码量从几十行变成几百行。我的建议是普通算法竞赛和日常工程压位 O(n²) 已经足够到了密码学或超大整数计算领域再考虑 FFT 路线。4.3 经典优化乘法如何减半循环一个很容易忽略的优化乘法的双层循环可以剪掉近一半的重复计算因为a[i] * b[j]和a[j] * b[i]都会累加到c[ij]两者乘积相同可以合并为一次性累加两次。这样循环次数从 n² 降到 n²/2。写法上没有本质改动只是在内层循环的边界稍微动动手脚for (int i 0; i (int)a.size(); i) { // 只累加 j i 的部分另一个对称位置靠循环补上 }不过这里有个坑两个数组长度不一致时对称累加的边界条件会很麻烦。如果你只是二分试商这类优化意义不大。真正有效的优化顺序是先压位再考虑循环剪枝最后才上 FFT。越靠前的方案越便宜风险也越小。5. 常见问题与排查技巧实录5.1 前导零问题几乎每个写过mul或sub的人都会遇到前导零。比如999 * 0 0如果不清理数组是[0, 0, 0]输出 “000”和 0 的比较也会出错。清理逻辑只有一个原则至少在数组中保留一位数字。我习惯写成while (digits.size() 1 digits.back() 0) digits.pop_back();这个size() 1的判断非常重要少了它遇到 0 时会把数组清空之后所有运算全面崩溃。5.2 进位/借位处理的边界条件进位的边界条件是“最后还要补一次”加法999 1最后 carry 1必须push_back(1)乘法两个 n 位数相乘最多 2n 位所以预分配a.size() b.size()空间不会越界借位的边界条件是“补 10 后可能还要继续借”减法1000 - 1从低位到高位一路借过去borrow会一直为 1循环结束后不需要处理额外进位因为我们已经保证 a b5.3 负数的表示与输出如果你采用“末尾放 -1”的土办法输出时要小心别把-1当普通数字打印。更通用的做法是单独加一个bool sign字段。这里给个更规范的构造思路在类内增加bool negative_ false所有比较和加减法先统一取绝对值运算最后根据符号定结果。牺牲一点代码量换来长期的心智负担降低我觉得非常值。5.4 除法试商的正确姿势避坑高精除以高精度时用二分试商会踩一个大坑边界条件必须从高位开始。举个例子9999 / 9如果从低位往高位试商每一步的余数处理会完全错乱因为除法的“余数”天然是高位对低位的传递——高位除不完余数乘 10 并入下一位再除。这是除法区别于另外三种运算的本质原因。另外二分试商时每次都要比较divisor * mid与当前被除数剩余部分的大小关系。如果这部分实现有错很难定位到底是二分问题还是乘法问题。我的排错技巧是先用小数字手推验证比如1234 / 12拿调试器看每一轮的商是否和手算一致再逐步放大到随机长数字用 Python 的//运算结果做交叉验证。没有哪个测试比“和 Python 对拍”更省心的了。5.5 常见的工程化问题工程化和算法题还有一点不同内存和并发。一个十万位的 BigInt 数组只占几百 KB不至于爆内存但如果是大量 BigInt 存储拷贝开销会显著。建议构造函数里多用移动语义BigInt(BigInt other) noexcept : digits(std::move(other.digits)) {} BigInt operator(BigInt other) noexcept { digits std::move(other.digits); return *this; }另外一个新手的误区是对自己的 BigInt 直接调用了 STL 排序或比较。如果类里没重载或编译直接报错如果重载了但内部的比较逻辑写成“按字典序”那么9 10这种错误就悄悄混进去了。重载比较运算符时必须先比长度长度相同再逐位比。6. 从算法到应用的扩展思考6.1 高精度算法在现实中的应用高精度不是竞赛圈自嗨的东西它在现实中有大量真实需求。最典型的是密码学RSA 加解密动不动就是 1024 位、2048 位的整数运算底层必定有高精度乘法比如 Montgomery 乘法加速。金融系统里金额计算为了避开二进制浮点误差也会把数值用十进制高精度表示。科学计算中有些常数或中间结果需要几百上千位的精度比如 π 的小数点后一万位就得靠高精度运算迭代逼近。理解了这个算法你对这些领域的底层原理会更有感知。6.2 和常用语言的对比不同语言处理高精度有各自的姿势语言方案特点C自实现 BigInt最快、最灵活、代码量最大JavaBigInteger内置类好用但运算慢于 C 优化版Pythonint支持任意精度极其方便但性能受限于解释器Gomath/big内置包性能接近 C 自实现如果你要用 C 写高精度本质上是在和 Java/Python 的内置大数做对标。好消息是 C 一旦优化到位性能可以非常硬特别适合竞赛和底层库开发。6.3 更多高级主题的入口掌握了这里的基础版 BigInt你可以继续往这些方向深入更高效的乘法Karatsuba分治、Toom-Cook、FFT/NTT更高效的除法Newton-Raphson 迭代法、Burnikel-Ziegler 算法特殊运算高精度开方、模幂、最大公约数配合扩展欧几里得算法十进制与二进制的互相转换涉及大数的快速进制转换底层也是高精度乘法/除法这些方向每一个都够单独写一篇长文但它们的共同根基就是这里讲的“数组模拟竖式”。基础打牢后面的路会顺畅很多。7. 实操总结与我的个人体会代码全写完之后我最大的感触是高精度算法真正的难点不是理解竖式而是处理边界条件和异常情况时的耐心。前导零、进位传递、借位传递、除法的高位优先——每一个单独拎出来都不是难题但合在一起如果缺少一套系统性的测试很容易在某个角落翻车。我自己的测试习惯是这样的先跑固定的边界用例比如999 1、1 - 999、999 * 999、1000 / 7然后写一个随机数据生成器生成几百组随机大数用 Python 的结果做对拍最后再测几组极限数据比如一万位的乘法和除法看是否会超时或者爆内存。这套流程下来大部分实现缺陷都能在十分钟内暴露出来强烈推荐你也试试。给刚开始学高精度的朋友一个建议不要一开始就追求 FFT 和压位。先用最笨的一位数一格实现把四则运算的所有边界情况跑通然后再考虑压位优化等压位也熟练了再根据实际需求决定要不要学 FFT。一上来就啃硬骨头的代价很大而且基础不牢很容易被边界情况打倒。按这个顺序走每一步都有扎实的收获心里也踏实。