1. 从一个算错的阶乘说起为什么大整数运算绕不开去年有人在群里贴了一段代码说他的程序算 25! 的结果是负数。代码本身没有任何语法错误循环写得也对long long也加上了但输出就是一个负数。这个问题在算法笔记里出现频率极高本质就是定长整型装不下动态增长的数字而我们要做的就是自己造一个能装下任意位数的容器这就是大整数运算。它解决的是超出语言原生整型表示范围的高精度计算问题适合正在刷算法题、准备笔试的人也适合在工程里需要处理超长整数精度的人来参考。我先说清楚这篇总结面向什么人如果你只会写a b而从来没想过为什么long long也有上限那这篇会帮你补上底层那一课如果你已经背过模板但每次遇到减法负号、乘法数组越界就翻车这篇会把你踩过的坑一个个摊开讲如果你是做工程而不是刷题的我也会讲清楚什么时候该自己写、什么时候直接用语言内置的大数类型更划算。大整数运算这件事说穿了不复杂把数字拆成一位一位存到数组里然后模拟小学竖式的计算过程。但真正写起来细节多得吓人——进位往哪加、借位怎么补、结果前导零怎么去掉、负数怎么标记、数组要开多大。算法笔记里那些看似背下来就行的模板其实每一条约定背后都有理由我这次就按照为什么这么设计的顺序把它从头到尾捋一遍。提醒一句本文的代码以 C 为主因为它的数组控制能力最能体现底层逻辑同时我也会穿插 Python 和 Java 的对照帮助你在实际工程中做取舍。2. 存储约定所有实现的起点都在这一层2.1 低位在前还是高位在前这个选择影响后面所有代码几乎所有大整数模板都会把最低位存在数组下标 0 的位置也就是低位在前、高位在后的顺序存储。原因很实在加法和乘法都是从个位开始往上算的进位也是往高位走。如果你把最高位放在下标 0那么每次计算都要反向遍历进位方向也变成数组下标递减代码里到处是i--和边界判断非常容易写错。假设要存数字 12345两种存法对比如下存储方式数组内容下标 0 起加法遍历方向进位方向代码易错点低位在前5, 4, 3, 2, 1下标递增下标递增输出时要反向打印高位在前1, 2, 3, 4, 5下标递减下标递减遍历边界与进位判断极易出错低位在前唯一的不便就是输出从最高位开始倒着打印。但这只是输出层的一行循环比起在运算里到处处理反向下标这点代价完全可以接受。算法笔记中的模板基本都是这个约定不是我偏好它而是它确实让从低位算起这件事变得自然。2.2 把长度和符号一起封装比裸数组靠谱得多很多人一开始喜欢用int a[1000]加一个int len裸着写函数参数传三个数组、长度、符号。写到第三个函数时你就会发现参数顺序老记混改一处忘一处。我的建议是一开始就用结构体或类封装把数组、长度、符号三件事绑在一起函数只传对象返回对象。struct BigInt { vectorint d; // 低位在前每位存 0~9 int sign; // 1 表示非负-1 表示负数 BigInt() : sign(1) {} };这里有两个设计决策值得说明。第一为什么符号单独存而不是用最高位带符号因为大整数的加减法需要先比较绝对值大小如果把符号和数值混在一起比较逻辑会变得极其别扭。第二为什么默认 sign 是 1 而不是 0因为 0 这个值在语义上属于非负用 1 表示非负可以让判断简单只有显式赋值为 -1 才是负数省掉大量if (sign 0)的分支。2.3 读入和输出前导零是新手第一个翻车点输入用string读然后从最后一位开始往d里倒序塞这一步大家都会。坑在于前导零输入0001235如果原样塞进去长度是 7 位输出时就是0001235很多在线判题系统直接就判错。所以读入后必须做一次trim把高位的 0 全部剥掉只留最低位的一个 0当数值就是 0 的时候。void trim() { while (d.size() 1 d.back() 0) d.pop_back(); if (d.size() 1 d[0] 0) sign 1; // 0 统一按非负处理 }输出时的处理方向相反先打印符号负数才打再打印最高位然后从次高位开始逐位补前导零。如果你做了后面要讲的压位优化这里必须用printf(%04d, x)这种带宽度格式而不是直接cout x否则内部的1000会被打成1结果直接错位。还有一个容易被忽略的细节读入超长串比如十万位时cin s配合默认的同步设置会很慢我一般会加ios::sync_with_stdio(false); cin.tie(nullptr);输出部分改用字符缓冲或者putchar逐位输出。刷题时遇到过一万位整数的题目输出部分没优化直接超时的例子不少。3. 加减法进位链和借位链才是真正的难点3.1 加法看起来最简单但循环边界最容易写错高精度加法的核心循环只有几行从低位开始对应位相加加上进位取模得到当前位除以 10 得到新进位。循环条件必须写成i lenA || i lenB || carry三个条件缺一不可。漏掉carry的人最多结果是999 1算出000而不是1000。BigInt addAbs(const BigInt a, const BigInt b) { BigInt c; int carry 0; for (size_t i 0; i a.d.size() || i b.d.size() || carry; i) { int sum carry; if (i a.d.size()) sum a.d[i]; if (i b.d.size()) sum b.d[i]; c.d.push_back(sum % 10); carry sum / 10; } return c; }这里的sum用int就够了因为每位最大是 9 9 1 19。但如果后面你改成压位存储每格存四位十进制数单个位置最大就是 9999 9999 1int依然能装下但乘法就不行了这个后面会细说。位宽选择要和运算类型匹配这是压位优化里最容易出错的地方。3.2 减法的真正难点不在借位而在符号判定加法不用管符号减法必须管。a - b可能是负数而我们的数组只能存绝对值。所以标准做法是先比较|a|和|b|如果|a| |b|就做|a| - |b|符号取a.sign否则做|b| - |a|符号取-a.sign。这套大减小、小的符号取反的逻辑是所有大整数库的标准套路。比较绝对值大小的时候不能直接比数组要先比长度trim之后长度不同就一定不等长度相同再从高位往低位逐位比。这两步顺序颠倒就会出错因为123的数组是[3,2,1]45是[5,4]如果你直接从下标 0 开始比会得出3 5是错的结论——长度不同的时候长度本身就是最大的信息。借位链的处理和加法类似只是把减换成借一当十BigInt subAbs(const BigInt a, const BigInt b) { // 保证 |a| |b| BigInt c; int borrow 0; for (size_t i 0; i a.d.size(); i) { int cur a.d[i] - borrow - (i b.d.size() ? b.d[i] : 0); if (cur 0) { cur 10; borrow 1; } else borrow 0; c.d.push_back(cur); } c.trim(); return c; }3.3 一份必须逐个跑过的边界用例清单我自己的习惯是写完加减法先把下面这张表里的用例全部手工跑一遍跑通了再写乘法。这些用例是我见过出错率最高的用例考察点常见错误结果0 0结果为零时的长度处理输出空串或00999 1进位溢出到新的一位0001000 - 999连续借位贯穿多位1015 - 5结果为 0 的符号归正输出-00 - 7小减大后的符号翻转结果为正数 7000123 0前导零读入处理输出带前导零-0这个坑特别值得说。当a和b绝对值相等、符号相反时做减法会得到长度为 1、内容为 0 的结果如果你沿用a.sign或者-b.sign就可能把符号设成 -1然后输出-0。所以在trim里加一句值为 0 时符号强制归正是必须的不是锦上添花。我踩过的坑早期版本的减法里我为了省事在subAbs内部直接改了a.sign结果同一个对象被后续运算复用符号就污染了。大整数对象一旦构造出来就当不可变对象用所有运算返回新对象这样能省掉大量隐蔽的调试时间。4. 乘法下标规律吃透了代码就三行4.1 竖式乘法的下标对应关系高精度乘法的核心是一句话a的第i位乘以b的第j位结果累加到c的第i j位。为什么是i j因为第i位代表的量级是 10^i第j位代表 10^j乘起来量级是 10^(ij)自然落在c的第ij位。这条规律记住了乘法就没什么玄学。BigInt mulAbs(const BigInt a, const BigInt b) { vectorlong long c(a.d.size() b.d.size(), 0); for (size_t i 0; i a.d.size(); i) for (size_t j 0; j b.d.size(); j) c[i j] (long long)a.d[i] * b.d[j]; long long carry 0; for (size_t i 0; i c.size(); i) { carry c[i]; c[i] carry % 10; carry / 10; } // carry 理论上已经为 0但保留判断更保险 ... }数组开多大是这里最致命的问题。两个长度分别为n和m的数相乘乘积最多n m位所以数组必须开n m。开n m - 1的人非常多因为直觉上两个三位数相乘最多六位但n m - 1 5999 × 999 998001是六位直接越界。4.2 累加用的容器必须能装住中间值上面代码里c用long long而不是int原因很明确下标ij位置上会累加最多min(n, m)个乘积每个乘积最大 81。如果数字有一万位单个位置可能累加到 810000 左右int勉强够但如果你做了压位每格存 0~9999单个乘积最大就是9999 × 9999 ≈ 1e8累加几十次就到1e9量级int就悬了。所以乘法的中间累加容器一律用long long这是几乎零成本的保险。高精度乘低精度一个大数乘一个int则简单得多直接每位乘、每位进位BigInt mulSmall(const BigInt a, int k) { BigInt c; long long carry 0; for (size_t i 0; i a.d.size() || carry; i) { long long cur carry (i a.d.size() ? (long long)a.d[i] * k : 0); c.d.push_back(cur % 10); carry cur / 10; } c.trim(); return c; }这个版本在算阶乘、算组合数、做大数快速幂的时候用得极多因为它比全量竖式乘法快一个数量级还不用开nm的临时数组。我在写阶乘那类题目时基本只实现这一个乘法就够了。4.3 什么时候才值得上 KaratsubaO(n²)的竖式乘法在位数到几万的时候会明显变慢。以一万位乘一万位为例内层循环是一亿次现代机器大概零点几秒到一秒勉强能过位数十万就彻底不行了。这时候有两条路Karatsuba 分治复杂度降到约O(n^1.585)或者用 NTT/FFT 做多项式乘法复杂度O(n log n)。我的实际建议是算法题里几乎用不到除非题目明摆着考这个。Karatsuba 的实现难点在于三路递归的加减法组合而大整数的加减本身又是一堆借位符号逻辑两件事叠在一起调试成本非常高。真要在工程里处理十万位以上的乘法直接用成熟库或者语言内置类型比自己手写靠谱得多。位数规模推荐方案理由千位以内竖式 O(n²)常数小代码短不易错万位左右压位竖式常数降一个数量级够用十万位以上分治或 NTT平方复杂度撑不住5. 除法与取模试商逻辑是全篇最烧脑的部分5.1 高精度除低精度从高位开始这跟加减乘都不一样前面三个运算都是从低位往高位算除法反过来——从最高位开始。因为除法的本质是从高位开始每次取一部分被除数看能减掉几个除数。高精度除单精度整数的写法非常固定// 返回商余数通过引用带回 BigInt divSmall(const BigInt a, int k, int rem) { BigInt q; q.d.assign(a.d.size(), 0); long long r 0; for (int i (int)a.d.size() - 1; i 0; --i) { r r * 10 a.d[i]; q.d[i] (int)(r / k); r % k; } q.trim(); rem (int)r; return q; }这段代码里r用long long是有道理的r最大是k-1乘 10 加 9 之后最大约10k如果k接近int上限int就会溢出。用long long一劳永逸。注意商数组是预先开好长度再按位填而不是push_back。因为高位可能算出 0比如100 / 9最高位商是 0如果边算边push_back顺序就反了。这个细节很容易被忽略然后你会得到一个位数对不上、顺序颠倒的商。5.2 高精度除高精度减法模拟和二分试商各有取舍两个大数相除最朴素的办法是减法模拟不断从被除数里减去除数减了几次商就是几。这在被除数远大于除数的时候会慢到不可接受比如10^1000 / 1要减10^1000次显然不行。改进方案是按位试商从被除数的最高位开始每次把当前余数乘 10 加上下一位然后在这个部分被除数上试商商的范围是 0 到 9如果压位的话是 0 到 BASE-1。试商有两种实现一种是从 9 往下试用乘法回代比较找到最大的那个能减掉的另一种是二分。从 9 往下试最多 10 次比较实际写起来更直观我一般用这个。// 伪代码展示试商骨架 BigInt divBig(const BigInt a, const BigInt b) { BigInt q, r; // q 为商r 为当前余数 for (int i a.d.size() - 1; i 0; --i) { r mulSmall(r, 10); r addSmall(r, a.d[i]); // 余数补上当前位 int k 0; while (cmpAbs(r, b) 0) { // 能减就减统计次数 r subAbs(r, b); k; } q.d.push_back(k); } reverse(q.d.begin(), q.d.end()); q.trim(); return q; }这个写法在压位之后效率还可以每次试商最多 BASE 次减法但纯十进制下每位最多减 9 次位数一多还是慢。真正高效的做法是把试商换成用当前余数的前几位除以除数的前几位估一个商再回代修正这就是长除法的手工思路。算法笔记里通常会给出这个优化版本但代码量翻倍我的建议是先写对朴素版能过题就收工卡时间了再优化。5.3 取模和整除判定在实际题目里的组合套路取模本身不需要单独实现a mod b a - (a / b) * b有了除法和乘法就能算。但工程里更常见的需求是大数对一个普通整数取模这种情况根本不用构造大整数对象直接边读边取模就行mod 0 for ch in s: mod (mod * 10 int(ch)) % MOD这个套路在处理十万位数字串对某个数取模时是标准解法时间复杂度 O(n)空间 O(1)比构造完大整数再取模优雅得多。很多题目里的判断能否被 3 整除判断是否为 11 的倍数都能用这个思路在 O(n) 内解决完全不需要大整数类。6. 压位优化让常数小一个数量级的实用技巧6.1 进制基数怎么选这一步决定了会不会溢出压位的意思是不再一位存一个数字而是一位存多个十进制位。比如BASE 10000数组下标 0 存的是最低四位下标 1 存接下来的四位。这样长度缩小到原来的四分之一循环次数跟着减少速度提升是很实在的。基数选择有严格约束加法时单格最大是2 * (BASE - 1) 1乘法的单格累加最大可能到(BASE - 1)^2 × 位数。如果BASE 10^9单格乘积约10^18已经接近long long上限9.2 × 10^18累加两次就溢出。所以稳妥的取法是基数单格最大乘积累加安全性输出格式10^41e8非常安全可累加数千次%04d10^81e16累加百次内安全%08d10^91e18基本不能累加%09d我一般用10^4虽然压缩比不是最高但它给long long留的余量足够大写起来不用担心边界。要是你追求极致用10^9配合__int128做中间累加也能跑但那种写法在不同编译器上的兼容性要自己测。6.2 输出格式是压位版本最容易翻车的地方压位之后输出必须这样写printf(%d, d.back()); // 最高位不补零 for (int i (int)d.size() - 2; i 0; --i) printf(%04d, d[i]); // 其余每格补足四位如果你图省事写成cout d[i]那么内部存的是3的格子本该输出0003结果只输出3整个数字的位数就错乱了。这个 bug 我在第一次写压位时踩过输出结果看起来数字都对但位数不对排查了半天才发现是补零的问题。7. 语言内置大数别急着造轮子7.1 Python 的整数天然无限精度但有个转换上限Python 的int不分长短2 ** 100000直接就能算出来这是它在大数场景下最大的优势。但很多人不知道的是从 Python 3.11 起整数和字符串互相转换有默认的位数上限约 4300 位超过会抛ValueError。也就是说你可以算出那个巨大的数但打印它的时候会报错。import sys sys.set_int_max_str_digits(1000000) # 放开转换位数限制 print(2 ** 100000)这个限制是为了防止某些场景下超长整数转换拖慢程序属于安全措施。我第一次遇到的时候完全没头绪明明算都算完了结果在print那一行崩了。跑大数题目之前先把这一句加上能省掉一次莫名其妙的调试。7.2 Java 的 BigInteger 和 BigDecimal后者才是真坑Java 的BigInteger用起来很顺手add、subtract、multiply、divide、mod都是现成的还支持gcd、pow、modPow这些高阶操作。BigInteger是不可变对象每次运算返回新实例这点和前面我建议的封装思路一致。真正的坑在BigDecimal。它的divide方法如果除不尽而且你没有指定精度和舍入模式会直接抛ArithmeticException。这不是 bug是设计如此——它不知道你想保留几位小数所以拒绝瞎猜。BigDecimal a new BigDecimal(10); BigDecimal b new BigDecimal(3); // a.divide(b); // 抛出 ArithmeticException a.divide(b, 10, RoundingMode.HALF_UP); // 正确写法还有一个必须记住的常识new BigDecimal(0.1)和new BigDecimal(0.1)是两个不同的值。前者会把你用二进制浮点表示的那个0.1一个近似值原封不动地装进去得到一个带很长尾巴的数字后者才精确等于十进制 0.1。工程里凡是涉及金额、利率、计量一律用字符串构造 BigDecimal这条规矩比任何技巧都重要。7.3 金融和工程场景能用整数就别用小数我做过一个跟金额相关的需求早期版本用浮点数存钱结果对账的时候出现了几分钱的差异查了两天才定位到是浮点累加误差。后来改成所有金额以分为单位用整数存问题立刻消失。大整数运算在工程里最典型的用途就是这个把小数问题转化成整数问题用精确整数运算替代浮点近似。这个思路适用于很多场景百分比统一用万分之一或百万分之一为单位存整数时间统一用最小单位微秒、纳秒存整数坐标统一放大固定倍数存整数。代价是你需要在输入输出层做单位换算收益是所有中间计算都是精确的不会有累积误差。场景浮点方案大整数方案金额累加有累计误差分单位整数精确比例计算舍入方向不确定定点放大后整数除可控大数阶乘溢出或丢精度大整数精确大数取模无法直接算边读边模O(n)8. 一份可复用的实现骨架与错误对照8.1 结构设计要点回顾把前面所有内容收拢成一个可用的骨架核心就四件事低位在前的vectorint、独立的符号位、每次运算后trim、所有运算返回新对象。加减法要区分绝对值运算和符号决策两个层次乘法注意数组开nm和累加用long long除法注意从高位遍历和商数组预开长度。这四条守住了剩下的基本是体力活。如果你是给工程而不是给题目写我还会加两条一是实现compare作为独立方法因为比较在加减法里反复用到二是给所有构造函数都做trim保证任何时刻对象都是规范形式这样你就不用担心某个中间结果带着前导零流进下一步。8.2 高频错误对照表现象根本原因修法输出带前导零读入或运算后没 trim构造和运算后统一 trim999 1得000循环条件漏了 carry加上|| carry输出-0零值符号没归正trim 里强制 sign 1乘法结果位数不对数组开成nm-1改成nm乘法结果混乱累加用了 int换long long压位后位数错乱补零格式写错%04d补足宽度除法商顺序反了边算边 push_back预开长度按位填小数除不尽崩溃BigDecimal 未指定精度传 scale 和舍入模式Python 打印大数报错转换位数上限set_int_max_str_digits8.3 复杂度速查加减法 O(n)竖式乘法 O(n²)高精度除低精度 O(n)高精度除高精度朴素版 O(n²) 到 O(n³) 之间取决于试商方式压位后各复杂度的常数约降为 1/k²k 为每格位数。这些数字不用背但心里要有数当位数上万时O(n²) 的乘法就是瓶颈其他运算都还能扛。9. 我个人在这块内容上的几点体会写大整数运算这类代码最大的感受是想清楚比写快重要。这些算法的逻辑本身并不深奥全是小学竖式但每一条约定——低位在前、符号独立、数组开 nm、除法从高位走——都是一次次越界和输出错误换来的。我现在的习惯是先把边界用例表列出来再动手写代码写完立刻用手算结果对照比写完再调试快得多。另外说一个我自己的取舍刷题的时候我只实现加、减、乘小整数、除小整数这四个因为绝大多数题目用这四个组合就够了全量的大数乘除法写出来又长又容易错性价比不高。真遇到需要大数除大数的题我会先想想能不能用取模、质因数分解或者别的方式绕过去。绕不过去的时候先把朴素版写对拿部分分再考虑优化这个顺序比一上来就追求最优解稳妥。最后分享一个检查技巧写完任何大整数运算函数先用随机生成的小数字跟原生整型对拍。比如随机生成两个 1 到 1000 的数分别用大整数函数和int算一遍比对结果字符串。对拍几百组不出错基本就能确认加减乘的逻辑没问题除法对拍时记得同时检查商和余数因为余数错了商往往看起来是对的问题会被掩盖很久。