第一次被高精度算法坑到是在算 50! 的时候。当时我还习惯用 int 变量一路乘下去结果 13! 之后数值就开始变得诡异到 17! 直接溢出成了一个负数。我还以为是编译器坏了后来才明白内置整数类型的上限就摆在那里想算更大的整数必须换一种存储思路。这个换思路的过程就是今天要聊的高精度算法。这篇文章针对两类人刚接触算法、在竞赛题里被大数运算反复折磨的新手以及日常开发里偶遇超过 long long 范围的整数计算、又不想为一个小功能引入重型依赖的开发者。咱们从最朴素的竖式运算出发把高精度加法和减法拆开讲透包括存储方式、进位借位、符号处理、测试用例设计和各种翻车现场。看完你能直接手写一套可用的模板也能理解为什么高精度代码要那样写。1. 为什么需要高精度运算内置整数类型的天花板有多低1.1 一个 21! 就把 long long 撑爆的例子很多人在学校里学的第一门语言是 C 或 C老师会告诉你 int 能存到 21 亿左右long long 能存到 9.22×10^18。这个范围听起来挺大但放到实际计算里其实很脆弱。举个最常见的例子阶乘。20! 2,432,902,008,176,640,000约 2.43×10^18还在 long long 范围内。21! 51,090,942,171,709,440,000约 5.11×10^19已经超出 signed 64 位整数的上限。也就是说你只要算到 21 的阶乘long long 就当场阵亡。斐波那契数列也一样第 92 项还在 long long 范围内第 93 项直接爆掉。竞赛题里更常见的是两个 1000 位的数字做加法这种情况别说 long long就是 __int128 也装不下。这种时候就需要高精度算法登场。1.2 浮点数为什么救不了场有人可能会想用 double 不就行了double 能表示到 10^308数字再大也不怕。但这里有个关键问题double 的精度是有限的它用 52 位来存有效数字超过 2^53约 9×10^15之后就不是每个整数都能被精确表示了。比如 9007199254740993 这个数double 存下来会变成 9007199254740992末尾直接丢失。如果你是在做科学计算这种误差或许可以接受但如果是在做精确的整数运算比如计算密码学里的大整数、判断两个大数是否相等这种精度损失就是致命的。所以高精度计算必须走另一条路不用一个变量装整个数而是把一个数拆成一位一位用数组装。1.3 高精度算法的核心思想用数组模拟竖式高精度算法的思想说穿了一文不值就是模拟你小学列竖式做加减法的方式。把大数按位拆开存进数组。从个位开始一位一位地做加法或减法。加法满十进一减法不够减就向高位借一。数组有多长就能表示多长的数理论上只要内存够几千位、几万位的数都能算。这也是高精度这个名字的由来——它不依赖硬件能直接表示的范围而是用软件方式突破上限换取任意大的整数运算能力。明白了这个出发点后面所有代码看起来都会很顺。2. 大数表示法读入、倒序存储与输出2.1 为什么不能直接读成整数高精度加法的第一步是怎么把一个大数读进来。你可能会想不就是一个数字吗用 cin n 读进来不就行了问题在于输入的数字本身可能就有几百上千位它根本装不进任何内置整数类型。所以唯一可靠的方式是用字符串读入。string s1, s2; cin s1 s2;读进来之后再把字符串里的每个字符转成数字存到 int 数组里。这一步是后面所有运算的基础也是新手最容易忽略的地方——你如果图省事直接拿字符串做运算字符和数字的转换关系会把你绕晕。2.2 倒序数组让进位和借位顺理成章字符串转数组的时候大多数人推荐的姿势是倒序存储也就是把个位放在数组下标 0 的位置十位放在下标 1依次类推。比如数字 1234存进数组之后是 a[0]4, a[1]3, a[2]2, a[3]1。为什么要倒序理由有三个竖式运算从个位开始倒序存储后运算循环可以直接从下标 0 开始不需要额外判断。加法产生进位、减法产生借位都在更高位进行。倒序存储时位数越高数组下标越大运算过程中向数组尾部扩展非常自然。如果正序存储进位和借位会发生在数组头部你不得不在每次操作时把整个数组往后挪复杂度凭空多出 O(n) 的移动成本。倒序存储本质上是用一个固定方向换来了读写方便。等你写多了会发现几乎所有高精度模板都是这个习惯你没必要跟它唱反调。2.3 字符串转数组的代码与输出套路下面这段代码定义了后面所有示例的基础工具#include bits/stdc.h using namespace std; const int MAXN 1005; // 根据题目需要调整一般多开一点 int a[MAXN], b[MAXN], c[MAXN]; // 三个全局数组默认全部清零 // 把字符串 s 倒序存入数组 dest返回实际长度 int strToArr(const string s, int dest[]) { int len s.size(); for (int i 0; i len; i) { dest[i] s[len - 1 - i] - 0; } return len; } // 倒序输出数组的前 len 个元素 void printArr(int arr[], int len) { for (int i len - 1; i 0; i--) { cout arr[i]; } cout \n; }注意几个细节字符转数字用的是s[len - 1 - i] - 0因为字符串里存的是字符 0 到 9减去字符 0 的 ASCII 值就得到对应的数字 0 到 9。全局数组默认初始化为 0这非常重要。后面运算时如果两个数长度不一样短的数的高位就自动按 0 处理不用你再费心补位。MAXN不要卡得太死建议比你预估的最大位数多出 5 到 10 个防止进位或借位时数组越界。提示如果你用的是局部数组记得用memset(a, 0, sizeof(a))手动清零否则里面是随机值运算结果会完全不可控。3. 高精度加法的实现进位链怎么处理3.1 加法核心循环的拆解加法是所有高精度运算里最温和的一个因为它只涉及两件事逐位相加、处理进位。核心逻辑就一行sum a[i] b[i] carry其中carry是上一位产生的进位。当前位的结果是sum % 10。新的进位是sum / 10。这个逻辑跟十进制竖式完全一致。sum的最大值是多少两个 9 相加再加进位 1最多是 19所以sum / 10只可能是 0 或 1不会出现进位大于 1 的情况。这是十进制加法的天然性质也让代码变得很简洁。3.2 手推一遍 999 1找到容易漏的进位光看代码不够我们手动推一遍最经典的进位例子999 1。初始状态a 数组存的是 [9, 9, 9]b 数组存的是 [1]len max(3, 1) 3。i0sum a[0] b[0] carry 9 1 0 10c[0] 0carry 1。i1sum a[1] b[1] carry 9 0 1 10c[1] 0carry 1。i2sum a[2] b[2] carry 9 0 1 10c[2] 0carry 1。循环结束carry 1说明最高位又产生了进位。这最后一步是新手最容易丢的。如果循环结束你不管 carry结果会变成 000正确答案 1000 就没了。所以必须在循环外面补一个判断如果 carry 不是 0就把它追加到结果数组的末尾。3.3 加法部分的完整代码void add(string s1, string s2) { int len1 strToArr(s1, a); int len2 strToArr(s2, b); int len max(len1, len2); int carry 0, cnt 0; for (int i 0; i len; i) { int sum a[i] b[i] carry; c[cnt] sum % 10; carry sum / 10; } if (carry) { c[cnt] carry; } printArr(c, cnt); }这里用cnt同时充当结果长度。它的初始值是 0每算完一位就加 1最后如果还有进位就再补一位。这样输出的时候直接传cnt就行不用再单独维护长度变量。时间复杂度和空间复杂度都是 O(n)n 是两个数中较长的位数。这个过程其实非常快1000 位的数字相加也就几千次简单操作在竞赛环境中属于微秒级运算。4. 高精度减法的实现借位、比较和符号4.1 减法的前置工作先比大小再决定谁减谁减法比加法多两个麻烦第一可能不够减需要借位第二结果可能是负数符号怎么处理。如果你在代码里直接写a[i] - b[i]遇到负数就抓瞎了。所以减法的标准做法是先比较两个数的绝对值大小让大数减小数最后再根据比较结果决定要不要加负号。比较的逻辑也很简单// 返回 1 表示 x y0 表示相等-1 表示 x y int cmpArr(int x[], int lenX, int y[], int lenY) { if (lenX ! lenY) { return lenX lenY ? 1 : -1; } // 长度相同从高位数组末尾往低位比 for (int i lenX - 1; i 0; i--) { if (x[i] ! y[i]) { return x[i] y[i] ? 1 : -1; } } return 0; }注意比较的顺序数组是倒序存的所以高位在下标大的位置必须从lenX - 1往下遍历。这个顺序反了比较结果就是错的。4.2 连续借位的模拟细节比较完成之后我们保证被减数的绝对值不小于减数。接着进入核心减法逻辑这里的关键是借位。// 用 a 减去 b结果存回 a返回结果长度 int subToA(int a[], int lenA, int b[], int lenB) { int len max(lenA, lenB); for (int i 0; i len; i) { if (a[i] b[i]) { a[i] 10; a[i 1]--; // 向高一位借 1 } a[i] - b[i]; } // 去掉前导零但至少保留一位 while (len 1 a[len - 1] 0) { len--; } return len; }借位的原理要理解清楚如果当前位a[i] b[i]就向高一位借 1借来的 1 在当前位相当于 10所以a[i] 10同时高一位减 1即a[i1]--。这里有个容易误解的点如果a[i1]恰好为 0被减成 -1 怎么办不用担心循环继续到 i1 的时候会检测到a[i1] b[i1]于是继续往更高位借。这个连锁借位是自动完成的也就是说1000 - 1这种连续借位的场景代码能正确跑出 999不需要单独写递归或特判。4.3 完整减法代码与负数输出减法的完整流程是这样void subtract(string s1, string s2) { int len1 strToArr(s1, a); int len2 strToArr(s2, b); int cmpRes cmpArr(a, len1, b, len2); if (cmpRes 0) { cout 0 \n; return; } if (cmpRes 0) { // a 比 b 小结果是负数先输出负号再算 b - a cout -; int newLen subToA(b, len2, a, len1); printArr(b, newLen); } else { int newLen subToA(a, len1, b, len2); printArr(a, newLen); } }这里我在cmpRes 0的分支里调用subToA(b, len2, a, len1)是把 b 当被减数、a 当减数。你可能注意到上面的subToA函数名暗示结果存回 a但在负数分支里结果存到了 b 数组里。为了教学清晰我把这个函数设计成第一个参数是存储目标。实际使用中你完全可以封装成返回 string 的形式但思路是一样的。还有两个细节必须处理相等的情况123 - 123比较结果是 0直接输出 0。如果漏掉这个分支后面减法循环会得到一堆 0最后被前导零清理逻辑删到只剩一个 0虽然结果碰巧对但中间过程会很危险而且容易在特殊用例上翻车。前导零清理后的长度while (len 1 a[len - 1] 0) len--这句必须放在借位循环之后否则1000 - 999 1会输出0001甚至更离谱的结果。5. 边界测试与常见翻车点用一组用例把自己逼疯5.1 五组必须跑的边界样例我自己写高精度模板的时候最大的教训是不要相信看起来对了。加减法代码不长但边界条件非常多任何一个没照顾到都会让你在评测机上白丢几十分。下面这组测试用例是我固定用来验证模板的每次写完先跑一遍场景AB加法期望减法期望普通进位99911000998连续借位100099919991结果为零1234512345246900长数减短数100001100019999负数结合借位1999910000-9998每个用例背后都对应一个具体的坑999 1考的是最高位进位有没有漏。1000 - 999考的是连续借位和结果前导零清理。很多新手算这个会输出0001就是因为没删前导零。12345 - 12345考的是相等情况的特殊处理不处理容易输出空串。1 - 9999考的是负号和借位同时出现漏了负号或者借位顺序错了都会错。5.2 前导零与输入自己带零的坑前导零的问题分两种。一种是结果里的前导零这个我们已经用while处理了。另一种是输入自带的前导零比如题目给的是00123而不是123。如果你直接把字符串转数组长度会变成 5高位存的是 0比较函数里长度判断就会出错——00123会被当成五位数和124比较时会错误地判断前者更大。稳妥的做法是在读入之后、转换之前统一去掉输入字符串的前导零void stripLeadingZeros(string s) { int pos 0; while (pos 1 s.size() s[pos] 0) { pos; } s s.substr(pos); }注意保留最后一个 0也就是说000应该变成0而不是空串。很多题目虽然保证输入无前导零但你没法确定每个平台的测试数据都那么好心加一个处理总没坏处。5.3 调试时怎么快速定位错在哪一步如果测试用例没通过不要盯着输出瞎猜。我常用的方法是在循环里加临时的输出把每一步的i、sum、carry或者a[i]、b[i]、借位后的值打出来手动比对竖式过程。比如加法你可以临时打印cout i i sum sum carry carry result_bit sum % 10 \n;减法同理打印借位前后的a[i]变化。通常跑一次999 1或1000 - 1就能立刻看出哪一位的逻辑出了问题。调试完记得把这些输出删掉别留在提交代码里。提示如果代码里有a[i1]--这类访问下标 i1 的操作一定要确保数组开得足够大否则最高位借位的时候可能越界访问出现本地运行正常、评测机上莫名崩溃的诡异现象。我的习惯是 MAXN 开成 1005题目说最多 1000 位那 1005 就稳稳够用。6. 加法减法之后的扩展压位、乘除与现成轮子6.1 压位存储同样代码把范围扩大四倍基础版本里数组每个元素存 0 到 9 的一位数字空间和时间的利用率都不高。实际工程和竞赛里更常用的是压位技巧让数组每个元素存四位数也就是万进制。加法的进位判断从sum / 10变成sum / 10000。当前位结果从sum % 10变成sum % 10000。读入字符串时从尾部开始每四位转成一个整数存入数组。输出时除了最高位那一组其他组不足四位要补前导零比如存的是[1234, 1]输出应该是11234而不是11234的错位版本。压位的收益非常直观长度缩小到原来的四分之一循环次数减少内存占用和运行时间都明显下降。等你把加减法跑通之后强烈建议自己实现一版万进制加法你会发现思路一模一样只是进位基数从 10 变成了 10000。6.2 乘除法的大致思路搞定了加减高精度乘法的核心思路其实也顺理成章模拟竖式乘法c[i j] a[i] * b[j]最后统一处理进位。高精度除法稍微复杂一些高精度除以低精度可以直接逐位试商高精度除以高精度则要用模拟竖式配合减法。这些内容放在后续篇幅展开比较合适。目前你需要知道的是加法减法是最底层的地基乘法会依赖加法除法会依赖减法把地基打牢后面都是水到渠成的事。6.3 高精度在不同领域的含义区分顺手澄清一个概念你在搜高精度的时候可能还会看到高精度遥感高精度定位高精度波形生成这类词。这些语境下的高精度指的是测量精度、浮点精度或时钟精度和我们这里说的高精度算法是两回事。算法领域的高精度核心诉求是突破内置整数类型的范围限制遥感、定位、波形生成里的高精度核心诉求是让测量误差更小、数值更接近真实值。两者都叫高精度但解法完全不同。如果你是为了竞赛或大整数计算搜到这篇文章那咱们讨论的就是同一件事。另外提一句如果你用的是 Python它的 int 本身就是任意精度的不需要手写Java 有BigIntegerC 也有boost::multiprecision::cpp_int。但理解底层实现依然重要因为并不是所有平台都允许你引入这些库而且手写一遍能让你对进位、借位这些基础概念有真正的体感而不是停留在会用 API的层面。说句实在话高精度加减法本身不难难的是养成对边界条件敏感的直觉。我自己写这套模板的时候第一次跑10000 - 1就翻车了原因就是借位循环里少看了一眼最高位。后来我把测试用例固定成上面那套表格每次写完直接跑一遍心里踏实很多。建议你也建一个自己的边界用例集以后不管写乘法、除法还是压位都能一键验证。下一篇咱们聊高精度乘法和除法想提前动手的话可以先想想乘法竖式里c[ij] a[i] * b[j]这个下标该怎么推。