你见过程序跑着跑着突然变成负数的诡异场景吗我在处理一个需要算 50! 的算法练习时第一次意识到C 的整型类型再能装也有天花板long long最大也只有 9.2×10¹⁸而 50! 是 65 位十进制数后者比前者大了几十亿亿倍。那一刻我理解了凡是数字可能超过整型上限的题目本质上都需要一套“高精度算法”来兜底用 C 实现的核心思路只有一句话把数字拆开装进数组而不是指望某个内置类型一次搞定。这篇文章会从为什么整型会爆掉讲起用一份可直接运行的 C 代码把高精度加减乘除完整实现出来再给出大阶乘、高精度幂的实战例子。环境只需要 VS Code MinGW项目只用了 C17 标准库里的vector和string不依赖任何第三方库。1. C 整型的真实上限数学题没给面子时的难题1.1 一张表看懂内置整型有多“短”先看一组数据范围这是我在决定手写高精度之前反复确认过的类型十进制位数上限典型数值量级int10 位±2.147×10⁹long long19 位±9.22×10¹⁸unsigned long long20 位1.84×10¹⁹20 位听起来不少但数学题从来不跟你商量。100!有 158 位1000!有 2568 位10000!更是直接冲到 35660 位。用long long去硬算这些连“溢出”都是轻的更准确说是从第一项开始就存不下。有一类算法练习题非常典型求斐波那契数列第 2000 项、计算组合数 C(4000, 2000)、判断一段超长数字的质因子。这些题目表面上是“思维题”实际上都在考同一个底层能力也就是大数存储与运算。你如果只会内建整型遇到这类题只能干瞪眼。1.2 为什么不用现成的大数库非要自己造轮子现在 C 生态里不缺大数工具Boost 里有cpp_int还有 GMP、OpenSSL BIGNUM 之类的高性能大数库。你要是做企业级项目直接调库一点问题都没有。但这里有一个关键区别调库只能让你“算出结果”无法让你理解“结果怎么算出来的”。高精度算法的本质是模拟小学数学竖式。竖式这套东西我们一年级就会但把它转化成代码需要解决几个基础问题数字怎么存、进位怎么处理、借位怎么处理、除法怎么一位一位试商。这些问题一旦搞明白以后看 GMP 源码、看密码学代码里的大数运算会顺畅很多。而且对大多数 OJ 题和算法学习场景来说引入 Boost/GMP 反而笨重。手写一个精简版高精度类几十行代码就能覆盖常用运算编译快调试也直观。我建议你至少手写一遍经历过那些昏天黑地的“前导零没清干净”“借位忘了减 1”之后才谈得上真正掌握。2. 高精度算法的底层逻辑用数组复刻手工竖式2.1 为什么数组必须倒着存数字很多人第一次写大数类会习惯性把数字正着放比如123456存成d[0]1, d[1]2, ... d[5]6。这个方案不是不能用但计算时会把自己坑死。竖式运算是从低位开始的。加法要先加个位乘法也是从低位乘起进位永远朝更高的位走。如果我们强调“数组头部是低位”那么进位就等价于在数组尾部追加元素。vector的尾部push_back是 O(1) 操作头部插入是 O(n) 操作那个效率差距在位数达到几千上万时会非常刺眼。所以我的约定是倒序存储d[0]存个位d[size-1]存最高位。这样一来个位加完产生的进位直接 push 到d末尾数字位数增加只需要在尾部追加不挪动已有元素输出时反向遍历一把即可虽然多一步倒序但计算效率核心优势保住了。2.2 好用的基准一位十进制数还是四位十进制数这是另一个重要的设计决策。一个vectorint里的每个 int我们可以让它只存 0 到 9 的一个数字也可以让它一次存 0 到 9999。两种方案都叫“进制转换”但取舍完全不同方案一位表示范围优点代价BASE 100~9逻辑简单debug 直观进位一目了然位数多内存占用大运算慢 4 倍左右BASE 100000~9999同一份代码性能提升约 4 倍内存更小乘法中间变量必须用long long打印时需要补零入门阶段我强烈建议先用 BASE 10。跑通加减乘除之后再把整个类的base改成 10000你会发现算法结构完全不动只是进位处理从%10变%10000乘法累积从int换成long long。用 10000 而不是 10⁹是因为 10000² × 10000 大约是 10¹²放在long long里非常安全而如果用 10⁹ 进制乘积直接逼近 10²⁷long long直接溢出还得引入__int128属于给自己上强度。3. BigInt 核心实现存储、比较、加法与减法3.1 类骨架与字符串构造我写的这个类完整考虑了正负号但为了讲清楚主逻辑下面的运算函数先假设参与运算的非负整数。符号位处理我会在除法章节专门补充一套口诀。#include algorithm #include iostream #include stdexcept #include string #include utility #include vector class BigInt { public: std::vectorint d; // 倒序存储d[0] 是个位 bool neg false; // 负号标记 BigInt(long long x 0) { if (x 0) { neg true; x -x; } if (x 0) d.push_back(0); while (x 0) { d.push_back(x % 10); x / 10; } } BigInt(const std::string s) { int i 0; if (s[0] -) { neg true; i 1; } for (int j (int)s.size() - 1; j i; --j) d.push_back(s[j] - 0); trim(); } void trim() { while (d.size() 1 d.back() 0) d.pop_back(); if (d.size() 1 d[0] 0) neg false; } bool isZero() const { return d.size() 1 d[0] 0; } std::string toString() const { std::string s; if (neg) s -; for (int i (int)d.size() - 1; i 0; --i) s char(0 d[i]); return s; } };有一点容易翻车BigInt(0)必须保证d里至少有一个 0否则trim()会把数组清空后续所有for循环直接越界。我习惯让每个合法对象都满足“d至少有一个数字”这个不变量。3.2 比较函数先比长度再比高位比较很好写但符号处理需要先统一。这里我先给绝对值比较int compareAbs(const BigInt a, const BigInt b) { if (a.d.size() ! b.d.size()) return a.d.size() b.d.size() ? -1 : 1; for (int i (int)a.d.size() - 1; i 0; --i) { if (a.d[i] ! b.d[i]) return a.d[i] b.d[i] ? -1 : 1; } return 0; } bool lessThan(const BigInt a, const BigInt b) { if (a.neg ! b.neg) return a.neg; // 负的一律小于正的 int cmp compareAbs(a, b); if (a.neg) return cmp 1; // 负数绝对值越大实际值越小 return cmp -1; }为什么比较要先比位数而不是直接从头扫因为倒序存储下最高位在数组末尾数组长度本身就携带了数量级信息。一个 10000 位的数再怎么说也不可能小于一个 9999 位的数省掉一轮逐位扫描在比较被反复调用时很有意义。3.3 加法进位传递是唯一主角加法模拟的就是最朴素的竖式个位相加超过 9 就向上进 1。BigInt addAbs(const BigInt a, const BigInt b) { BigInt r; int carry 0; int n std::max(a.d.size(), b.d.size()); for (int i 0; i n || carry; i) { int sum carry; if (i a.d.size()) sum a.d[i]; if (i b.d.size()) sum b.d[i]; r.d.push_back(sum % 10); carry sum / 10; } r.trim(); return r; }这里循环条件写成i n || carry非常关键它天然处理了最高位还有进位的情况。比如 999 1两数都只有 3 位但在i 3时carry仍为 1循环继续多生成一个数字输出就是 1000完全正确。3.4 减法借位和“谁减谁”定符号先想清楚a - b如果a b结果应该是负数。在实现层面我直接交换用绝对值大的减绝对值小的然后打上负号标记。BigInt subAbs(const BigInt a, const BigInt b) { // 调用前提compareAbs(a, b) 0 BigInt r; int borrow 0; for (int i 0; i a.d.size(); i) { int cur a.d[i] - borrow; if (i b.d.size()) cur - b.d[i]; if (cur 0) { cur 10; borrow 1; } else borrow 0; r.d.push_back(cur); } r.trim(); return r; } BigInt operator-(const BigInt a, const BigInt b) { if (compareAbs(a, b) 0) return BigInt(0); if (compareAbs(a, b) 0) return subAbs(a, b); BigInt r subAbs(b, a); r.neg true; return r; }减法最常见的 bug 是trim()执行不彻底。比如 1000 - 999按位相减会出现一段 0如果不把高位的空零清掉toString()会输出0001甚至0999。我写完后都会用一个固定测试集去查1000 - 999 11000 - 1000 01 - 1000 -999这三个用例过了借位逻辑基本稳了。4. 乘法实现竖式展开与“乘小整数”的工程智慧4.1 大数乘以大数双重循环加统一进位乘法竖式是两层循环模拟a的第i位乘b的第j位贡献到结果的第ij位。全部累加完之后统一处理进位。BigInt mulAbs(const BigInt a, const BigInt b) { BigInt r; r.d.assign(a.d.size() b.d.size() 1, 0); for (int i 0; i a.d.size(); i) for (int j 0; j b.d.size(); j) r.d[i j] a.d[i] * b.d[j]; for (int i 0; i 1 r.d.size(); i) { r.d[i 1] r.d[i] / 10; r.d[i] % 10; } r.trim(); return r; }这里我多分配了一个位a.d.size() b.d.size() 1。原因是中间列的累加值可能很大进位不是简单的一次“除以 10”而会形成一串进位传递。多一个位只是让边界更宽松最后trim()会清掉多余的零。用 BASE 10 时单格累加最多是 9 × 9 × 位数比如位数几百时单格也就几万int完全撑得住。但如果你把 BASE 改成 10000累加最高可达 10000² × 10000 10¹²那就必须用long long累加了。4.2 大数乘以小整数阶乘场景的救命函数很多使用高精度的经典题并不是动不动就“两个一万位的数相乘”而是一个大数反复乘以一个普通整数。最典型的就是阶乘。如果算n!时每次都调用mulAbs那复杂度会变成 O(n³) 级别的灾难。但提供一个mulSmall让大数只和普通int相乘单次复杂度只是 O(位数)整道题立刻降维BigInt mulSmall(const BigInt a, int k) { BigInt r; long long carry 0; for (int i 0; i a.d.size() || carry; i) { long long cur carry; if (i a.d.size()) cur 1LL * a.d[i] * k; r.d.push_back(cur % 10); carry cur / 10; } r.trim(); return r; }算10000!的位数大约是 35660 位用mulSmall循环 10000 次每次处理 35660 位总操作量是 3.5 亿次以内。以现代 CPU 的速度毫秒级到秒级就能跑完。如果丧心病狂地让两个一万位数相乘操作量直接是 1 亿次但这只是单次大数乘法的开销循环多次就崩了。所以“把大数运算拆成合适原语”是工程里的一等大事。4.3 复杂度评估竖式乘法到底能扛多少位我经常在社区里看到有人拿 100000 位大数做乘积写个双重循环直接卡死。竖式乘法的复杂度是 O(n × m)其中n、m是两个数的十进制位数。1000 位乘 1000 位正好 100 万次乘加现代机器随手算完100000 位乘 100000 位那就是 10¹⁰ 次直接进入分钟级内存分配开销还得翻倍。如果真遇到百万位乘法有三个进阶路线Karatsuba 分治把一次大乘法拆成三次更小的乘法复杂度降到 O(n^1.585)Toom-Cook 算法继续拆成更多块常数变大但渐进更优FFT/NTT把点值乘法甩给快速傅里叶变换复杂度 O(n log n)这是 GMP 等库压箱底的东西。但我不建议你第一版就去追这些先把 O(n²) 的竖式写对再在需要性能时逐个替换。很多题目或者项目里千位级数字的竖式乘法绰绰有余。5. 除法与取模长除法模拟、试商过程和符号约定5.1 从高位试商把余数“乘 10 加下一位”加法、减法、乘法都是从低位开始唯独除法要从高位开始这也是最容易翻车的地方。想想你在纸上做除法先拿被除数的前几位判断够不够除够除就写商余数继续落位。模拟过程是这样的从被除数的最高位开始维护一个“当前余数”。每轮先把余数乘 10再加被除数的一位然后循环减去除数减几次商的那一位就是几。std::pairBigInt, BigInt divmod(const BigInt a, const BigInt b) { if (b.isZero()) throw std::runtime_error(divide by zero); BigInt q, r(0); q.d.assign(a.d.size(), 0); for (int i (int)a.d.size() - 1; i 0; --i) { r mulSmall(r, 10); r addAbs(r, BigInt(a.d[i])); int cnt 0; while (compareAbs(r, b) 0) { r subAbs(r, b); cnt; } q.d[i] cnt; } q.trim(); return {q, r}; }这里隐含了一个可以放心使用的性质因为每轮进入循环前都有r b所以r * 10 digit 10 * b 9减b的次数最多只有 10 次不可能出现减几十次还减不完的情况。因此cnt一定落在 0 到 9 之间完美适配十进制一位商。5.2 负数参与除法时的符号约定上面代码只处理了非负数。真实场景里肯定会遇到-100 / 7这种输入我的处理口诀是取两个数的绝对值去调divmod商的符号 两个数符号的异或结果余数的符号我习惯跟随被除数数学教材里的余数定义更倾向为正余数但工程和不同语言各有约定需要提前在接口文档里写明。一个极高价值的提醒是C内建%和数学余数的行为是有差异的。内建%结果的符号跟着被除数走但很多人会默认它等价于“正余数”然后在高精度库上栽跟头。写自己的BigInt时符号策略必须明确写注释否则后来维护代码的人一定会被坑。5.3 除法实现里的隐藏雷区第一除数为 0 必须第一时间抛异常不要等到循环里做减法减出负数才意识到不对。第二q.d.assign(a.d.size(), 0)之后商数组长度可能和被除数相同但高位会出现多余 0。比如1000 / 9商是 111数组长度本来是 4最后通过trim清成 3 个数字别忘了这一步。第三r mulSmall(r, 10)不能省。有人想当然写成r.d.insert(r.d.begin(), 0)这种操作既慢又容易搞错方向因为倒序存储下“乘 10”应该是在数组头部插一个 0。最稳妥的做法永远是调用现成的mulSmall不要自己手动动底层数组。第四除法性能比加减乘差很多。单次除法的实现里套了mulSmall、addAbs、subAbs多个 O(n) 操作整体 O(n²)。想优化时可以引入二分试商甚至牛顿迭代但一般场景没必要。6. 实战验证大阶乘、高精度幂与现场测试6.1 大阶乘用 mulSmall 的经典案例有了上面的类算大阶乘只需要几行BigInt factorial(int n) { BigInt fac(1); for (int i 2; i n; i) fac mulSmall(fac, i); return fac; }我实测过10000!的输出35660 位运行耗时远小于直觉。因为全程没有出现大数乘大数每次乘法都是大数乘一个小整数这是最理想的使用姿势。如果你想顺手验证正确性可以针对性比较几个小数据5! 120、10! 3628800、20! 2432902008176640000。最后这一个正好超出unsigned long long的 20 位上限也是很多手写高精度程序第一次露馅的地方。6.2 高精度快速幂算法题里的大杀器有些题目会要求计算2^1000、3^5000这种结果。用朴素循环乘上几千次复杂度不太好看。标准做法是快速幂BigInt powBig(const BigInt base, int exp) { BigInt result(1), b(base); while (exp 0) { if (exp 1) result mulAbs(result, b); b mulAbs(b, b); exp 1; } return result; }这里要注意2^1000只不过 302 位powBig很快但10^1000000这种又是指数又大的话最终结果有 1000001 位乘法代价会迅速失控。所以高精度快速幂更适合用在位数适中的题目或者配合“对大数取模”把中间结果压小。取模本身就是高精度除法的一半divmod(...).second现成可用。RSA、大数验签等场景里经常做大数模乘和模幂原理就是我前面写的这套除法与乘法只是工程上为了性能会套 CRT、蒙哥马利模乘之类的加速。6.3 在正式项目里继续扩展的方向这个教学版的 BigInt 已经能解决绝大多数算法题和原型验证。如果要在自己的 C 项目里继续使用我建议按下面顺序增强把 BASE 从 10 改成 10000并同步修改输出函数低位不足四位时补零实现完整的operator、operator-把符号位处理封装进函数而不是调用方自己管重载和输入输出流方便直接读写类内部使用移动构造和移动赋值避免大数拷贝带来的开销加一组单元测试覆盖边界0 0、1 - 1、999...99 1、1000...00 - 1、负数乘以负数等。我个人的习惯是每实现一个高精度算法都会写一个很小的testBigInt()函数把所有容易出错的边界用例都塞进去跑一遍。别小看这个动作它能帮你省下无数次由于“前导零没清”和“符号位没统一”造成的夜间调试。最后分享一个实际心得如果只是为了快速完成一个需要超大整数功能的需求直接上boost::multiprecision::cpp_int或 GMP 是更聪明的选择但如果你想真正理解计算机怎么处理超出硬件字长的运算亲手把竖式翻译成 C 代码绝对是一门绕不开的必修课。把这份代码跑起来你会发现在“整型溢出”这个经典问题上你比大多数人多了整整一层理解。