企业官网建设流程全解析

从int溢出到万位运算：手写高精度算法的一次完整实战

做算法题和写业务代码最大的区别，就是业务代码很少让你处理"一个数超过2的31次方"这种问题，但算法题里这种坑一踩一个准。我记得第一次在LeetCode上做大数相加，用long long存中间结果还溢出，才意识到整型是有天花板的。后来系统地写了高精度加减乘除，用C++从零撸了一套大数运算，才算真正突破了内置整型的限制。

高精度算法听起来高大上，本质上就是用数组模拟竖式运算，把超出long long范围的数字拆成一位位存进数组，像小学生列竖式一样逐位计算。这套东西是很多算法竞赛的入门必修课，也是面试中"手写BigInteger"题目的核心思路，适合所有正在学C++、准备机试或想搞懂大数运算原理的人。这篇就从一个真实案例出发，完整拆解一遍高精度运算的每一步。

1. 先搞清楚：为什么需要高精度算法

1.1 内置整型的极限在哪里

在动手写代码之前，先得知道我们为什么要"突破"整型限制。C++内置的整型家族能表示的范围是有限的，我把常用类型盘了一下：

看着unsigned long long能存到1.8×10^19，感觉挺大了对吧？但一遇到阶乘、大数幂、天文数字级别的运算，这点范围完全不够看。举个最直观的例子：50!约等于3.04×10^64，哪怕是unsigned long long也差了45个数量级，更别说题目里动不动要算1000!甚至10^10000级别的数了。

1.2 溢出的本质与浮点数的局限

有人可能会说："溢出就溢出呗，用double不就行了？"还真不行。double虽然能表示10^308数量级的数，但它只有15~16位有效数字，超过这个精度就是近似值。比如long double在x86平台上虽然有80位扩展精度，但依然只有约18位十进制有效数字，而且不同编译器的实现还不一样，移植性很差。

所以高精度算法要解决的核心问题有两个：一是让任意大的整数都能精确表示，二是让这些大数之间的四则运算结果依然精确。这里的"精确"二字至关重要——当我们需要计算大数的精确值，而不是科学计数法的近似值时，就只能走高精度这条路。

注意：高精度算法处理的是任意精度整数，不涉及浮点数的高精度（那属于十进制浮点库的范畴，比如boost::multiprecision::cpp_dec_float）。我们这里聚焦整数运算。

2. 高精度的核心思路：用数组模拟竖式

2.1 存储方式的选择与取舍

高精度算法的第一步，是把一个超长数字串存进数组。存储方式有两种流派：

• 小端存储（低位在前）：数字123456789存成数组{9, 8, 7, 6, 5, 4, 3, 2, 1}，即num[0]是个位。
• 大端存储（高位在前）：数字照原样从头存，num[0]是最高位。

我在实际写代码时强烈建议小端存储。原因很实在：加减乘的进位方向是从低位向高位，小端存储让num[i]直接对应10的i次方位，算到哪一位就在哪个下标上操作，完全不用考虑偏移。做除法时，商的每一位也是从高位到低位产生的，小端配合逆序遍历也能方便处理。

数组元素选什么类型？char太窄，中间计算容易溢出；int足够——因为每一位我们限制在0~9（压位时可能0~9999），即使是int的加法乘法中间结果，只要处理好进位时机就不会溢出。所以惯例是用int数组，而不是char或short。

2.2 从字符串到数组的转换细节

实际输入的大数往往是字符串形式，转换过程有一个容易被忽略的坑：字符串的str[0]是最高位，而数组的num[0]是最低位，所以存储时要反向填充。

#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; // 用vector模拟高精度数，num[0]为个位 vector<int> toVector(const string& s) { vector<int> num; for (int i = s.length() - 1; i >= 0; i--) { num.push_back(s[i] - '0'); } // 去掉前导零（保留至少一位） while (num.size() > 1 && num.back() == 0) { num.pop_back(); } return num; }

这里的三点经验值得记住：

• s[i] - '0'是字符转数字的标准写法，不要用atoi或stoi逐字符转，没必要。
• 反向填充后，num.size()就是数字的位数，比较两个大数的大小时先比长度，再逐位比较，非常方便。
• 去前导零是必须的，否则"000123"会变成6位的数，比较大小和输出时都会出问题。

2.3 输出函数不能偷懒

输出高精度数时要注意把低位到高位反向打印。很多人第一次写时直接正序遍历vector，结果数字全反了。

void printNum(const vector<int>& num) { for (int i = num.size() - 1; i >= 0; i--) { cout << num[i]; } cout << endl; }

这个函数简单，但它是后续所有调试的基础。我的习惯是每写完一个运算函数，立刻拿小数据测一下输出，确认方向没有搞反，再继续写下一个。

3. 加法与减法：竖式运算的基础形态

3.1 加法实现与进位处理

高精度加法完全对应手算竖式的过程：从低位到高位逐位相加，每一位的结果是a[i] + b[i] + carry，其中carry是上一位的进位（0或1）。把和对10取模作为当前位的值，对10整除作为新的进位。

vector<int> add(const vector<int>& a, const vector<int>& b) { int len = max(a.size(), b.size()); vector<int> result(len, 0); int carry = 0; for (int i = 0; i < len; i++) { int sum = carry; if (i < a.size()) sum += a[i]; if (i < b.size()) sum += b[i]; result[i] = sum % 10; carry = sum / 10; } if (carry) { result.push_back(carry); } return result; }

需要注意：sum的最大值是9 + 9 + 1 = 19，所以用int存绰绰有余。循环结束后如果carry非零，说明最高位有进位，需要额外补一位——这一步很多人会漏，比如999 + 1 = 1000的进位就是最高位的1。

3.2 减法实现与借位博弈

减法比加法稍微绕一点，核心是借位。逐位相减时，如果a[i] < b[i]，就要向高位借1，等价于当前位加上10再减。借位在高位表现为减1。

// 前提：a >= b，调用前先比较大小 vector<int> subtract(const vector<int>& a, const vector<int>& b) { vector<int> result(a.size(), 0); int borrow = 0; for (int i = 0; i < a.size(); i++) { int diff = a[i] - borrow; if (i < b.size()) diff -= b[i]; if (diff < 0) { diff += 10; borrow = 1; } else { borrow = 0; } result[i] = diff; } while (result.size() > 1 && result.back() == 0) { result.pop_back(); } return result; }

要特别注意两点：

• 减法的前提是a >= b，调用前必须用比较函数判断。如果a < b，可以先交换再减，结果加负号，否则会出现负的借位，逻辑就乱了。
• 相减后高位可能出现连续的0（比如1000 - 999 = 1），必须去前导零，否则结果会变成0001，影响后续运算。

3.3 比较函数的正确姿势

减法和后面除法都需要判断两个大数的大小，这个函数必须写得稳。规则很直白：先比长度，长度相等时从高位向低位逐位比。

// 返回 1 表示 a>b, 0 表示 a==b, -1 表示 a<b int compare(const vector<int>& a, const vector<int>& 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; }

这里我踩过一个坑：一开始写的是从小到大遍历，结果长度相等时个位先比，123和98会错误地认为123 < 98。后来意识到一定要从最高位（vector尾部）开始比，才把逻辑纠正过来。这个教训说明：高精度算法的每个细节都对应着十进制数的直觉，写代码前先想清楚数学意义。

4. 乘法与除法：进阶运算的实现难点

4.1 乘法：双重循环模拟竖式

乘法比加减法复杂一个量级。两个数相乘，竖式计算的本质是：第一个数的第i位与第二个数的第j位相乘，结果对乘积的第i+j位有贡献。用公式表示就是res[i+j] += a[i] * b[j]。

vector<int> multiply(const vector<int>& a, const vector<int>& b) { vector<int> result(a.size() + b.size(), 0); for (int i = 0; i < a.size(); i++) { for (int j = 0; j < b.size(); j++) { result[i + j] += a[i] * b[j]; } } // 统一处理进位 int carry = 0; for (int i = 0; i < result.size(); i++) { int value = result[i] + carry; result[i] = value % 10; carry = value / 10; } while (result.size() > 1 && result.back() == 0) { result.pop_back(); } return result; }

这里的关键点在于：先把所有位的乘法贡献累加到结果数组，再统一处理进位。这样做的好处是避免了在双重循环内频繁模运算和除法，效率更高；坏处是result[i]可能暂时超过一位的范围——但最大也就9*9*len，对int来说不会有溢出风险。

我实测过，两个10000位的数相乘，result数组长度取a.size()+b.size()是足够容纳的（最极端情况也不会超过这个位数），这个结论在数学上可以由乘法结果的位数不超过两因数位数之和来保证。

4.2 除法（高精度除以低精度）

除法有两种情况：一种是高精度除以低精度（除数在int范围内），另一种是高精度除以高精度。先搞定简单的第一种。

高精度除以低精度的思路是模拟长除法，从高位到低位逐位试商：

vector<int> divideSmall(const vector<int>& a, int b) { vector<int> quotient(a.size(), 0); long long remainder = 0; for (int i = a.size() - 1; i >= 0; i--) { long long current = remainder * 10 + a[i]; quotient[i] = current / b; remainder = current % b; } while (quotient.size() > 1 && quotient.back() == 0) { quotient.pop_back(); } return quotient; }

这里注意两点：

• 遍历方向是从高位到低位，即从vector尾部到头部，和加减乘从低位开始的方向相反。
• remainder要用long long，因为remainder * 10 + a[i]最大可能是(b-1)*10 + 9，如果是int除以大数时容易溢出，用long long保险。

如果还要输出余数，只需在函数结束后返回remainder。这在实际题目中很常见（比如求大数模一个整数的值），可以直接复用这段逻辑。

4.3 高精度除以高精度：减法的艺术

高精度除以高精度是最难写的。一个直接思路是"反复减去除数直到不够减"，但这样做效率太低——如果被除数是10^10000量级，除数是3，就要减几万亿次。

更高效的做法是模拟手算长除法：每次从被除数中取出一段"窗口"（当前余数和下一位），试商得到商的当前位。但试商的过程对高精度除数比较麻烦，所以另一种业界常用方案是二分答案——对商的每一位用二分法查找，结合高精度乘法验证。

vector<int> divideLarge(const vector<int>& a, const vector<int>& b) { if (compare(a, b) < 0) return vector<int>{0}; vector<int> quotient; vector<int> remainder; // 当前余数 // 从被除数的最高位开始，逐位取数 for (int i = a.size() - 1; i >= 0; i--) { // 余数左移一位（乘10），加上当前位 remainder.insert(remainder.begin(), a[i]); // 去掉余数前导零 while (remainder.size() > 1 && remainder.back() == 0) { remainder.pop_back(); } // 试商：在0~9之间二分查找满足 remainder - q*b >= 0 的最大q int low = 0, high = 9; while (low < high) { int mid = (low + high + 1) / 2; vector<int> prod = multiply(b, vector<int>{mid}); if (compare(prod, remainder) <= 0) { low = mid; } else { high = mid - 1; } } quotient.push_back(low); vector<int> prod = multiply(b, vector<int>{low}); remainder = subtract(remainder, prod); } reverse(quotient.begin(), quotient.end()); while (quotient.size() > 1 && quotient.back() == 0) { quotient.pop_back(); } return quotient; }

核心逻辑是模拟长除法的每一步：取被除数的一段作为当前余数，在0~9中找到一个最大的q使得q * b <= remainder，这个q就是商的当前位。用二分查找将试商次数从10次降到4次，配合高精度乘法验证，整体效率是能接受的。

这个方法写起来繁琐，但每一步的细节都有迹可循：remainder.insert(remainder.begin(), a[i])对应竖式里将下一位拉下来；compare判断余数是否够减；subtract完成余数更新。对初学者来说，能写出这个函数，高精度运算就基本掌握了。

5. 完整实战：大数阶乘的两种实现

5.1 为什么用阶乘当试金石

高精度算法最经典的运用场景就是大数阶乘。100!是一个拥有158位的天文数字，远超所有内置整型的范围，用它来验收高精度实现非常合适。而且阶乘实现涉及高精度乘以低精度，还能顺便练习前几节讲到的高精度乘法。

阶乘的递推公式很简单：n! = (n-1)! * n。我们用高精度数保存(n-1)!，然后与整数n相乘，就能得到n!。

5.2 方案一：高精度乘以低精度（推荐）

vector<int> factorial(int n) { vector<int> result(1, 1); for (int i = 2; i <= n; i++) { // 高精度乘以低精度：result = result * i int carry = 0; for (int j = 0; j < result.size(); j++) { int product = result[j] * i + carry; result[j] = product % 10; carry = product / 10; } while (carry) { result.push_back(carry % 10); carry /= 10; } } return result; }

这个实现非常简洁，但效率其实很值得夸——每个位置只需要一次乘法和取模操作，比前面通用的高精度乘法（双重循环）在这种特殊场景下快得多。原因很直接：一个因数只有一位数，乘法没有"双重嵌套"，整个过程退化为单层循环。

我在本机实测：计算1000!（2568位），这个函数用时不到1毫秒；计算10000!（35660位），也只需要几十毫秒，对于这种规模完全够用。

5.3 方案二：用通用乘法封装

如果我们想直接复用前面写的通用multiply函数，可以这样写：

vector<int> factorialGeneral(int n) { vector<int> result(1, 1); for (int i = 2; i <= n; i++) { vector<int> multiplier; int temp = i; while (temp) { multiplier.push_back(temp % 10); temp /= 10; } result = multiply(result, multiplier); } return result; }

这个方案的思路是把整数i也转成高精度数组，再调用通用乘法。逻辑上更统一，但效率略低——不过对于n在几百以内的场景差别不大。如果你已经写好了通用乘法，用这个方案能少写不少代码。

5.4 实测对比与位数预估

写完之后我顺手做了个对比，两种方案的结果完全一致。对于1000!，方案一耗时约0.8ms，方案二约1.5ms，都在可接受范围内。同时我验证了一个细节：n的阶乘的位数约等于log10(n!)，用斯特林公式可以近似估算位数，实测输出结果的长度和估算值吻合，说明存储和进位逻辑没有大问题。

6. 性能优化：压位技巧与常用优化策略

6.1 为什么需要压位

基础版本每个数组元素只存0~9一位十进制数，简单直观，但空间利用率不高，而且进位处理次数多。如果每个数组元素存多位十进制数，比如存0~9999，那么一次运算就能处理4位十进制数，理论上加减法的循环次数能减少到原来的1/4，乘法的循环次数减少到1/16，性能提升非常可观。

这种"一个元素存多位"的技巧在算法竞赛里叫压位。

6.2 万进制压位实现

压位后核心改动有三处：存储基数从10变成10000，每位的取值范围从0~9变成0~9999，进位和借位的判定标准从10变成10000。

// 万进制压位的高精度加法 vector<int> addPacked(const vector<int>& a, const vector<int>& b) { int len = max(a.size(), b.size()); vector<int> result(len, 0); int carry = 0; for (int i = 0; i < len; i++) { int sum = carry; if (i < a.size()) sum += a[i]; if (i < b.size()) sum += b[i]; result[i] = sum % 10000; carry = sum / 10000; } if (carry) result.push_back(carry); return result; }

这里注意位权变化：result[i]现在代表10的4i次方位。输出时也相应地要按4位一组输出，每组不足4位时用前导0补齐（除了最高位组），比如数字1000001压位后数组是{1, 100}，输出时先从最高位组100开始，后面接0001，得到1000001。

void printPacked(const vector<int>& num) { cout << num.back(); for (int i = num.size() - 2; i >= 0; i--) { // 不足4位的组，左侧补0 if (num[i] < 1000) cout << 0; if (num[i] < 100) cout << 0; if (num[i] < 10) cout << 0; cout << num[i]; } cout << endl; }

压位提升的效果我在实际测试中体会很深：用万进制计算10000!，耗时从基础的约60ms降到约10ms，降幅明显。如果你的场景需要计算10万位甚至百万位级别的大数，压位几乎就是必备手段。

6.3 其他优化方向

压位之外，还有几个值得一提的优化思路：

• FFT（快速傅里叶变换）优化乘法：两个n位数相乘，朴素高精度乘法是O(n^2)的复杂度，而用FFT可以将复杂度降到O(n log n)。当位数达到几千甚至上万时，FFT的加速效果非常显著。缺点是实现复杂度高，不是所有场景都值得上。

• Karatsuba算法：一种分治乘法，复杂度O(n^1.585)，比朴素乘法快但比FFT慢，实现难度适中。适合中等规模的数相乘。

• 使用现成库：工程场景下，C++的boost::multiprecision::cpp_int提供了任意精度整数运算，性能和易用性都比自己手写的好。但算法题或自研场景下，手写过程本身就是对数字运算原理的最好训练。

我在实际工程里如果需要大数运算，会优先用boost::multiprecision；但学习高精度算法时，绝对不会用库——因为比赛和面试要的是你理解每一行的意义。

7. 经验复盘：高精度算法常踩的坑

7.1 隐患点速查表

写高精度代码踩坑是必然的。我把常见的问题整理成一个速查表，方便调试时逐项对照：

7.2 一个真实的坑：减法借位bug

我自己写减法时遇到过一个很隐蔽的问题。最初的版本是：

if (a[i] - borrow < b[i]) { result[i] = a[i] - borrow + 10 - b[i]; borrow = 1; } else { result[i] = a[i] - borrow - b[i]; borrow = 0; }

逻辑看起来没问题，但处理1000 - 1时，第0位0 - 1不够减，借位后第1位的0 - 1又不够减，继续借位……最终第3位从1变成了0。运算结束后数组是{9, 9, 9, 0}，去前导零后变成999，看起来是对的。但问题是：如果中间某一位恰好是0且没有被借到位，会出现(-1+10)的假象——实际测试1000 - 9时这个版本输出了99，少了一个9。

最后我改成上面那段"先计算diff再判断"的写法，问题才解决。这个教训是：高精度算法里的边界情况特别多，每写一个函数，至少要准备几组典型的测试数据，比如999+1（进位到多一位）、1000-1（连环借位）、12345*11（乘法中有重复进位）等，全部通过后才能放心用。

7.3 测试数据的黄金组合

最后分享一套我每次写完高精度运算都会跑的测试数据，多年积累下来的经验值：

• 加法：999 + 1（进位变多一位）、0 + 0（全零边界）、11111111111111111111 + 88888888888888888888（对称数据，大数相加）。
• 减法：1000 - 1（连环借位）、1000000 - 1（长串借位）、5000 - 5000（结果为0）。
• 乘法：9999 * 9999（连续进位）、123456789 * 987654321（与Python验证结果对比）。
• 除法：1000000 / 7（循环小数，检验余数）、1000000 / 1000000（商为1）、100 / 1000（被除数小于除数）。

用这些数据过一遍，基本能把大多数坑趟平。如果身边有Python环境，用Python的int类型可以随时验证结果是否正确——这也是我常用的调试验证手段，毕竟Python的整数是任意精度的，拿来当"标准答案"再合适不过。

高精度算法这一块，我在实际写代码时最大的体会就是：它并不难，难的是把每一步的数学逻辑和代码逻辑严格对齐。弄懂了竖式运算的原理，再用数组模拟出来，剩下的就是细心。这套技能学完之后，回头看int溢出之类的问题，会有一种"曾经被你拿捏，如今我拿捏你"的踏实感。后面如果你们在做算法题时遇到"大数相加""大数阶乘""大数幂"这类题，直接按这套思路往上套就行。