企业官网建设流程全解析

你见过程序跑着跑着突然变成负数的诡异场景吗？我在处理一个需要算 50! 的算法练习时第一次意识到，C++ 的整型类型再能装也有天花板：long long最大也只有 9.2×10¹⁸，而 50! 是 65 位十进制数，后者比前者大了几十亿亿倍。那一刻我理解了，凡是数字可能超过整型上限的题目，本质上都需要一套“高精度算法”来兜底，用 C++ 实现的核心思路只有一句话：把数字拆开装进数组，而不是指望某个内置类型一次搞定。这篇文章会从为什么整型会爆掉讲起，用一份可直接运行的 C++ 代码把高精度加减乘除完整实现出来，再给出大阶乘、高精度幂的实战例子。环境只需要 VS Code + MinGW，项目只用了 C++17 标准库里的vector和string，不依赖任何第三方库。

1. C++ 整型的真实上限：数学题没给面子时的难题

1.1 一张表看懂内置整型有多“短”

先看一组数据范围，这是我在决定手写高精度之前反复确认过的：

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 好用的基准：一位十进制数还是四位十进制数

这是另一个重要的设计决策。一个vector<int>里的每个 int，我们可以让它只存 0 到 9 的一个数字，也可以让它一次存 0 到 9999。两种方案都叫“进制转换”，但取舍完全不同：

入门阶段我强烈建议先用 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::vector<int> 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 = 1
• 1000 - 1000 = 0
• 1 - 1000 = -999

这三个用例过了，借位逻辑基本稳了。

4. 乘法实现：竖式展开与“乘小整数”的工程智慧

4.1 大数乘以大数：双重循环加统一进位

乘法竖式是两层循环模拟：a的第i位乘b的第j位，贡献到结果的第i+j位。全部累加完之后统一处理进位。

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::pair<BigInt, 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++ 代码，绝对是一门绕不开的必修课。把这份代码跑起来，你会发现在“整型溢出”这个经典问题上，你比大多数人多了整整一层理解。