1. 为什么竞赛和工程里都绕不开手写高精度刚接触算法竞赛或者需要处理超大数运算的工程场景时很多人第一反应是找现成的库比如某些大数类或者语言自带的任意精度整数。但实际用下来你会发现现成库要么依赖太重要么在特定平台上不可用要么性能不符合题目对时间复杂度的苛刻要求。于是手写一套高精度模板就成了绕不过去的基本功。高精度运算的核心矛盾其实很朴素C内置的int、long long能表示的整数范围有限long long最多也就到 9.2×10^18 这个量级。一旦涉及几百位甚至上万位的整数加减乘除内置类型直接溢出连结果都存不下。这时候就需要用数组或者字符串来模拟“竖式运算”的过程把每一位单独存起来手动处理进位和借位。我见过不少初学者一上来就想着用__int128或者各种奇技淫巧去绕结果遇到真正的大数题目还是得老老实实回来写高精度。与其反复造轮子不如一次性把加减乘、高精度除低精度以及取模这几个最常用的操作封装成一套结构清晰、可复用性强的模板。这篇文章就把我自己在多个项目和比赛里打磨出来的高精度模板拆开讲透从存储结构的选择到每一位的进位处理再到除法取模的边界情况全部配上可运行的代码和实测经验。适合阅读的人群很明确正在准备算法竞赛、需要处理大整数运算的开发者以及想理解竖式运算如何映射到代码里的学习者。哪怕你之前没写过高精度跟着思路走一遍也能自己写出来。2. 存储结构的选择为什么我最终放弃了字符串2.1 字符串存储的便利与陷阱用string存大数是最直观的做法每一位就是一个字符0到9直接对应数字。读取输入的时候不用做任何转换cin s就完事了。输出的时候也简单直接打印字符串即可。这种方案在只做加减法的时候确实够用代码写起来也短。但问题出在运算过程中。字符串的每一位是字符类型做算术运算时必须先减去0转成整数算完再转回字符。这个转换在循环里反复执行不仅代码啰嗦还容易在进位处理时写错。更麻烦的是字符串的长度是固定的虽然可以用push_back动态扩展但频繁的插入删除操作在性能上并不理想。我早期写的一份高精度加法模板就是用字符串做的在数据量大的时候明显比数组版本慢一截。还有一个容易被忽略的点字符串存储时数字的高位在索引小的位置低位在索引大的位置。做竖式运算需要从低位往高位处理也就是要从字符串末尾往前遍历。这个反向遍历的逻辑在加减乘里都要重复写增加了出错概率。2.2 向量加低位优先存储的实战方案我最终采用的方案是用vectorint来存每一位数字并且低位存在数组的前面也就是v[0]是个位v[1]是十位以此类推。这个顺序和人类阅读的习惯相反但它带来的好处是巨大的做加减乘的时候直接从索引 0 开始往后遍历进位自然地向高位传递不需要任何反向遍历。struct BigInt { vectorint digits; // digits[0] 是个位 bool negative; // 符号位本文暂只讨论非负整数 };每一位存成int而不是char省去了反复的字符转换。vector的动态扩容特性让进位导致的位数增长变得自然push_back一个进位值就行。输出的时候从最高位往低位反向打印虽然多了一步反向遍历但输出只发生一次不影响运算性能。这里有个细节值得说每一位到底存一位数字还是存多位数字存一位数字实现简单进位逻辑清晰但空间利用率低。有些高性能模板会采用压位的方式比如一个int存 4 位或 9 位数字减少数组长度从而提升运算速度。对于绝大多数题目和工程场景一位一存已经足够压位带来的复杂度提升和调试难度不值得。除非你明确遇到了性能瓶颈否则我建议先用一位一存的方案把逻辑跑通。2.3 前导零的处理策略不管用哪种存储方式前导零都是必须处理的问题。比如计算1000 - 999结果应该是1但如果存储时保留了高位那些零输出就会变成0001。我的做法是在每次运算结束后统一做一个去除前导零的操作从最高位开始检查只要最高位是 0 且数组长度大于 1就把它删掉。void trim(vectorint v) { while (v.size() 1 v.back() 0) { v.pop_back(); } }注意循环条件是v.size() 1保证至少保留一位。如果结果本身就是 0数组里应该只剩一个 0不能被删空。这个trim函数在加法、减法、乘法、除法之后都要调用是保证结果正确的关键一步。我踩过的坑之一就是忘了在减法后调用trim导致100 - 100输出000而不是0。3. 加减乘三种运算的进位与借位逻辑3.1 高精度加法从低位到高位的逐位累加加法的逻辑最直接两个数的每一位分别相加再加上来自低位的进位结果的当前位是和对 10 取模新的进位是和除以 10。用低位优先的存储方式直接从索引 0 开始遍历循环条件是两个数都还没遍历完或者进位不为零。vectorint add(const vectorint a, const vectorint b) { vectorint res; int carry 0; int n max(a.size(), b.size()); for (int i 0; i n || carry; i) { int sum carry; if (i a.size()) sum a[i]; if (i b.size()) sum b[i]; res.push_back(sum % 10); carry sum / 10; } return res; }这段代码里i n || carry这个循环条件很关键。它保证了即使两个数都遍历完了只要还有进位循环就会继续把最后的进位加到结果里。比如99 1遍历完两位后进位还是 1循环会再执行一次把 1 加到结果的最高位。实测下来这个加法模板处理一万位的数字耗时在毫秒级别完全够用。需要注意的是如果两个数长度差异很大比如一个几千位一个几位循环里每次都要判断i a.size()和i b.size()有轻微的性能损耗。如果追求极致性能可以先把两个数补齐到相同长度再运算但代码会稍微复杂一点一般场景没必要。3.2 高精度减法借位处理与结果符号的判断减法比加法多了一个麻烦需要判断结果的正负。如果被减数小于减数结果应该是负数。我的处理方式是先写一个比较函数判断两个数的大小关系然后在减法函数里根据比较结果决定是否交换两个操作数并设置符号位。int compare(const vectorint a, const vectorint 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; }比较的时候先比位数位数多的数一定大。位数相同就从最高位往低位逐位比较找到第一个不同的位就能确定大小。这个比较函数在减法和后面的除法里都会用到。减法的核心是借位当前位不够减的时候向高位借 1当前位加 10 再减。用低位优先的存储方式借位自然地向高位传递。vectorint sub(const vectorint a, const vectorint b) { vectorint res; 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; } res.push_back(diff); } trim(res); return res; }这里假设a b调用前已经通过compare保证了这一点。borrow变量记录当前位是否向高位借了 1。注意循环只遍历到a.size()因为a的位数一定大于等于b。减法结束后必须调用trim否则像1000 - 999这种结果会带上前导零。3.3 高精度乘法双重循环与进位累加乘法的思路是模拟竖式乘法用第二个数的每一位去乘第一个数的每一位把结果累加到对应的位置上。具体来说a[i] * b[j]的结果应该加到res[ij]这个位置上。vectorint mul(const vectorint a, const vectorint b) { vectorint res(a.size() b.size(), 0); for (int i 0; i a.size(); i) { for (int j 0; j b.size(); j) { res[i j] a[i] * b[j]; } } int carry 0; for (int i 0; i res.size(); i) { int temp res[i] carry; res[i] temp % 10; carry temp / 10; } trim(res); return res; }这个实现分两步走第一步把所有乘积累加到res数组的对应位置上此时res里的每一位可能远大于 9第二步从低位到高位统一处理进位。这种写法的好处是进位逻辑只写一次代码清晰不容易出错。结果数组的长度初始化为a.size() b.size()这是因为两个数相乘的结果位数最多是两者位数之和。比如 99×999801两位乘两位得到四位。初始化时多留一位是安全的最后trim会把多余的零去掉。实测中我发现如果两个数位数都很大比如各一万位双重循环就是一亿次操作耗时会明显上升。这时候可以考虑用快速傅里叶变换来优化乘法但那是另一个话题了。对于常规题目O(n²) 的乘法完全够用。4. 高精度除低精度与取模的配合4.1 为什么除法只做“高精度除低精度”完整的两个高精度数相除实现起来相当复杂需要模拟长除法的试商过程代码量和调试难度都远超加减乘。但在实际题目和工程场景中绝大多数除法需求都是“高精度数除以一个普通整数”比如把一个几百位的大数除以 7 求商和余数。这种场景下除数可以用内置的int或long long表示实现起来简单很多。所以我这套模板的策略是加减乘支持两个高精度数运算除法只支持高精度除低精度。如果确实需要两个高精度数相除可以先用这套模板实现一个高精度乘低精度再配合二分或者牛顿迭代来逼近商但那是进阶用法本文不展开。4.2 从高位到低位的逐位除法除法和加减乘不同它需要从高位往低位处理。因为竖式除法是从被除数的最高位开始每次取一位和余数组合再除以除数。用低位优先的存储方式就需要从数组末尾往前遍历。pairvectorint, long long divmod(const vectorint a, long long b) { vectorint quotient(a.size()); long long remainder 0; for (int i a.size() - 1; i 0; i--) { long long cur remainder * 10 a[i]; quotient[i] cur / b; remainder cur % b; } trim(quotient); return {quotient, remainder}; }这段代码同时算出了商和余数一举两得。remainder用long long存储因为每次迭代时remainder * 10 a[i]最大是(b-1)*10 9只要b在int范围内这个值就不会溢出long long。商数组的长度初始化为和被除数相同因为商的位数最多和被除数一样。计算完成后同样要trim去掉前导零。余数直接返回不需要额外处理。4.3 取模运算的独立封装与复用取模其实就是除法的一部分但很多时候我们只关心余数不关心商。为了代码复用我通常把取模单独封装成一个函数内部调用divmod然后只返回余数。long long mod(const vectorint a, long long b) { long long remainder 0; for (int i a.size() - 1; i 0; i--) { remainder (remainder * 10 a[i]) % b; } return remainder; }这个版本比调用divmod再取余数更高效因为它不需要存储商数组省去了一次vector的分配和写入。在只需要余数的场景下直接用这个函数。这里有个容易踩的坑如果除数是负数取模的结果符号在不同编译器下可能不一致。我的建议是取模前先把除数转成正数最后根据需要对结果调整符号。本文讨论的都是非负整数所以不涉及这个问题但你在实际使用时要注意。5. 实测中暴露的边界问题与性能取舍5.1 零值、相等值和单数字的特殊情况高精度运算里最容易出 bug 的地方不是复杂的进位逻辑而是那些看起来不起眼的边界情况。我整理了几个必须专门测试的场景场景输入示例预期结果常见错误加零0 00输出空字符串减自身123 - 1230输出 000乘零0 × 9990数组越界或输出空除一456 ÷ 1456商数组多出前导零取模自身789 % 7890余数计算错误零值的处理尤其关键。当输入是0时存储数组里应该只有一个0而不是空数组。如果读取输入时不小心把0存成了空数组后续所有运算都会出问题。我的做法是在读取输入后立即调用trim保证0被正确表示为[0]。相等值的减法也是高频错误点。compare函数返回 0 时减法结果应该是[0]但如果不调用trim可能会得到[0, 0, 0]这样的数组。输出时就会变成000。5.2 大数运算的时间与空间实测数据为了给你一个直观的性能参考我用这套模板做了一组实测。测试环境是普通的开发机编译器开启 O2 优化。运算类型数字位数耗时加法10000 位小于 1 毫秒减法10000 位小于 1 毫秒乘法1000 位约 5 毫秒乘法5000 位约 120 毫秒除法10000 位 ÷ int小于 1 毫秒取模10000 位 % int小于 1 毫秒从数据可以看出加减法和除低精度的性能都非常好一万位的数字基本是瞬间完成。乘法的 O(n²) 复杂度在位数增大时增长明显五千位乘法已经需要一百多毫秒。如果你的场景涉及上万位的乘法就需要考虑压位或者更高级的算法了。空间方面一位存一个int一万位的数字占用约 40KB 内存完全可以接受。如果换成压位存储同样位数的内存占用可以降到几分之一但代码复杂度会上升。5.3 压位优化的适用场景与代价压位是指一个数组元素存多位数字比如一个int存 4 位因为10000在int范围内。这样数组长度缩短为原来的四分之一乘法的双重循环次数减少到十六分之一性能提升非常明显。但压位带来的代价也不小。首先进位和借位的基数从 10 变成了 10000所有涉及取模和除法的地方都要改。其次输出的时候需要把每个元素按四位补零输出不能直接打印。最后调试难度大幅上升一旦出错很难定位是哪一位的问题。我的建议是先用一位一存的版本把逻辑跑通确保所有边界情况都正确。如果实测发现性能确实不够再考虑压位优化。不要一上来就追求压位那样很容易在调试上浪费大量时间。6. 把这套模板用起来的几个实操建议6.1 输入输出的规范化处理输入一个大数时最稳妥的方式是按字符串读入然后从末尾往前遍历把每个字符转成数字存进vector。这样天然就是低位优先的顺序。vectorint readBigInt() { string s; cin s; vectorint v; for (int i s.size() - 1; i 0; i--) { v.push_back(s[i] - 0); } trim(v); return v; }输出的时候反向遍历从最高位开始打印。void printBigInt(const vectorint v) { for (int i v.size() - 1; i 0; i--) { cout v[i]; } }注意trim在读取后就要调用保证像000这样的输入被规范化为[0]。输出函数不需要额外处理因为trim已经保证了没有前导零。6.2 运算符重载让代码更自然如果不想每次都写add(a, b)、sub(a, b)这样的函数调用可以把BigInt封装成一个结构体重载、-、*、/、%运算符。这样代码写起来就像内置类型一样自然。struct BigInt { vectorint digits; BigInt operator(const BigInt other) const { BigInt res; res.digits add(digits, other.digits); return res; } // 其他运算符类似 };运算符重载的代价是每次运算都会创建一个新的BigInt对象涉及vector的拷贝。如果对性能敏感可以改用引用传参和原地修改的方式但代码可读性会下降。我个人的习惯是在竞赛中直接用函数在工程项目中用运算符重载看场景取舍。6.3 常见调试技巧与验证方法高精度代码的调试有个很实用的技巧用 Python 做对照验证。Python 内置了任意精度整数可以轻松算出正确结果。你可以写一个小脚本随机生成大数分别用 C 模板和 Python 计算对比结果是否一致。import random a random.randint(10**100, 10**101) b random.randint(10**50, 10**51) print(a b) print(a * b)把 Python 的输出和 C 的输出对比如果一致就说明模板正确。这个方法比手动构造测试用例高效得多能覆盖大量随机情况。另一个技巧是在关键步骤打印中间结果。比如在乘法的进位处理循环里打印每一步的temp和carry看看是否符合预期。虽然会拖慢运行速度但调试阶段非常有用。最后提醒一点高精度模板写完后一定要用极端数据测试比如全 9 的数、位数相差很大的数、结果需要大量进位的数。这些边界情况才是 bug 的高发区。我在实际使用中每次修改模板后都会跑一遍固定的测试集确保没有引入回归问题。