2. 高精度加法的实现思路2.1 从个位开始逐位相加高精度加法的核心是“模拟竖式”。用数组的第0位存个位第1位存十位依此类推。两数相加时从第0位开始逐位相加如果某一位的和大于等于10就向高位进1当前位保留对10取余的结果。举个例子计算 123 456个位3 6 9 十位2 5 7 百位1 4 5 结果 579这个过程没有任何难度但要注意的问题是“进位链”。比如计算 999 1个位9 1 10写0进1 十位9 进位的1 10写0进1 百位9 进位的1 10写0进1 千位补上进位1结果为1000如果只在循环结束后判断一次最高位就会漏掉连续进位的情况。所以在实现时循环结束后要检查进位标志如果还有进位需要额外往高位补一位。2.2 加法完整实现// a 和 b 为倒序存储的大数返回同样倒序的结果 vectorint add(vectorint a, vectorint b) { vectorint c; int carry 0; int len max(a.size(), b.size()); for (int i 0; i len; i) { int sum carry; if (i a.size()) sum a[i]; if (i b.size()) sum b[i]; c.push_back(sum % 10); carry sum / 10; } if (carry) c.push_back(carry); return c; }这里的参数用vectorint而不是C风格的数组主要是为了方便管理长度和内存。用vector时不需要手动记录长度size()直接给出答案传参也不会有数组退化为指针的坑。2.3 加法的时间复杂度加法是O(n)的n是参与运算数字的位数。对于大整数的加法这已经是最优复杂度了因为每一位都必须被扫描到。实测中两个10万位的数字相加在普通机器上不到1毫秒就能算完性能完全不是问题。注意所有高精度运算的输入都必须是倒序存储的。如果输入是正序字符串需要反转后再传入。这一步很多人会忘我就踩过这个坑——用正序数组做加法结果错得离谱。3. 高精度减法的实现思路3.1 先比较大小再逐位相减减法比加法多一个关键步骤先判断两个数谁大谁小。如果被减数小于减数结果需要加负号并且交换两数让大数减小数。这样处理可以避免在逐位运算时出现负数把借位逻辑简化成只做正数减法。比较大小的函数也很简单先比长度长度相等再逐位从高位到低位比较// 返回 true 表示 a b bool cmp(vectorint a, vectorint b) { if (a.size() ! b.size()) return a.size() b.size(); for (int i a.size() - 1; i 0; i--) { if (a[i] ! b[i]) return a[i] b[i]; } return true; }3.2 减法完整实现vectorint sub(vectorint a, vectorint b) { // 调用前确保 a b vectorint c; int borrow 0; for (int i 0; i a.size(); i) { int cur a[i] - borrow; if (i b.size()) cur - b[i]; if (cur 0) { cur 10; borrow 1; } else { borrow 0; } c.push_back(cur); } // 去掉前导零比如 100 - 99 001需要去掉前面的0 while (c.size() 1 c.back() 0) c.pop_back(); return c; }这里最经典的坑就是“前导零”。计算 1000 - 999 1如果不处理前导零结果是 0001 反过来是 1000长度是4位完全错误。所以最后必须把高位多余的0全部删掉只保留最低位的0比如 0 - 0 0 的结果是单0。3.3 减法中的借位细节借位处理我用了borrow标志位。每一轮运算时先把上一位的借位减掉然后判断当前位是否小于0。小于0就加10同时置借位为1不小于0就置借位为0。这个逻辑看起来简单但实际操作时容易出问题。比如计算 1000 - 1个位0 - 1 0加10得9借位1 十位0 - 1 0加10得9借位1 百位0 - 1 0加10得9借位1 千位1 - 1 0借位0 结果0999去掉前导零得999每一步都必须严格依赖上一步的借位状态顺序千万不能乱。提示减法的返回值统一不带负号负号由调用方根据cmp结果自行处理。这样函数本身保持简洁调用处逻辑也更清晰。4. 高精度乘法的实现思路4.1 双重循环逐位相乘乘法的原理是模拟手工竖式乘法。用a的第 i 位乘以 b 的第 j 位结果累加到结果数组的第 ij 位上最后统一处理进位。为什么是ij因为a的第 i 位代表10^ib的第 j 位代表10^j两者相乘就是10^(ij)所以结果放在第 ij 位。这个位置关系是乘法实现的核心。4.2 乘法完整实现vectorint mul(vectorint a, vectorint b) { vectorint c(a.size() b.size(), 0); for (int i 0; i a.size(); i) { for (int j 0; j b.size(); j) { c[i j] a[i] * b[j]; } } // 统一处理进位 int carry 0; for (int i 0; i c.size(); i) { int cur c[i] carry; c[i] cur % 10; carry cur / 10; } // 去掉前导零 while (c.size() 1 c.back() 0) c.pop_back(); return c; }这个实现是最直观的O(n^2)复杂度。两个1000位的数相乘需要约100万次乘法运算现代电脑跑起来毫秒级完成。两个100000位的数相乘就是10^10次运算在竞赛环境下就比较吃力了需要考虑使用FFT优化。4.3 乘法的知识点拆解乘法这里有两个易错点。第一个是结果数组的长度。a有m位b有n位乘积最多有mn位。最坏情况如 999 × 999 998001正好6位最小情况如 100 × 100 10000只有5位。所以开a.size() b.size()的空间最稳妥最后用前导零清理。第二个是进位不能立即处理。有人会在内层循环里每次加完就立刻处理进位这在数学上没问题但容易让位上的值临时超过9必须在所有位上的乘法完成后统一处理。否则会出现某个位置的累加值还在继续增长进位却已经提前处理走了的错误。4.4 一个细节乘法和高精度与低精度的混合运算如果只是一个大数乘以一个普通的int不超过10^9完全不需要走双重循环。可以只做一层循环把每一位和这个int相乘然后统一进位vectorint mulInt(vectorint a, int b) { vectorint c; long long carry 0; for (int i 0; i a.size(); i) { long long cur (long long)a[i] * b carry; c.push_back(cur % 10); carry cur / 10; } while (carry) { c.push_back(carry % 10); carry / 10; } while (c.size() 1 c.back() 0) c.pop_back(); return c; }这里的long long不能省。因为a[i] * b最大是9 × 10^9 9×10^9再加上进位可能超过int的范围。用int直接乘会溢出这是一个隐蔽的bug。竞赛中很多“大数乘以小整数”的题目都能用这个函数搞定效率远高于通用乘法。5. 高精度除法的实现思路5.1 除法是唯一没法用竖式直接模拟的加减乘都可以直接模拟竖式但除法不同。大整数除以大整数如果按竖式一位一位试商需要不断做乘法和减法每次都涉及大量的高位运算效率很低。竞赛中更实用的方案是二分法对于大整数 a 除以 b通过二分商 q使得q * b a (q1) * b这样 q 就是整除结果。由于乘法已经实现了二分配合乘法可以直接复用已有代码。5.2 二分法求商的实现vectorint div(vectorint a, vectorint b) { // 边界如果 a b商为 0 if (!cmp(a, b)) return vectorint{0}; vectorint low(1, 0), high(a); // 注意 high 的初始值可以取 a 本身也可以取 1 后不断翻倍直到超过 a // 这里更简单的做法high 从 1 开始不断翻倍直到 high * b a vectorint one(1, 1); high one; while (cmp(mul(high, b), a)) { high add(high, high); // 翻倍 } // 注意这里 high 可能已经超过 a 了用 high 作为上界即可 vectorint ans; while (cmp(high, low)) { vectorint mid add(low, high); // mid / 2这里如果用高精度除以2可以用位运算或直接位移 mid divByTwo(mid); if (cmp(mul(mid, b), a)) { ans mid; low add(mid, one); } else { high sub(mid, one); } } return ans; }这里引入了一个辅助函数divByTwo把大数除以2。除以2可以简单地从高位到低位逐位处理模拟二进制移位vectorint divByTwo(vectorint a) { vectorint c(a.size(), 0); int carry 0; for (int i a.size() - 1; i 0; i--) { int cur a[i] carry * 10; c[i] cur / 2; carry cur % 2; } while (c.size() 1 c.back() 0) c.pop_back(); return c; }5.3 用乘法和减法实现除法的替代方案二分法实现起来代码量不小另一种常用方案是“试商法”从被除数的最高位开始逐步取被除数的一段尝试找最大的 q 使得q * b不大于当前余数。这个方案本质上是模拟竖式除法但每步都要做一个高精度比较和减法复杂度比二分法略好但代码更复杂。对于初学者我的建议是直接上二分法。因为二分法不需要额外的除法逻辑只需要把加法、减法、乘法、比较都复用起来写起来其实更省心。5.4 除法的性能分析二分法的复杂度是O(log(商)) * O(乘法)。商每增加一位二分的轮数就增加约log2(10)≈3.32轮。对于商有1000位的除法需要约3300轮二分每轮做一次高精度乘法时间复杂度O(n^2)总复杂度约O(n^2 log n)对于千位级别的大数来说完全够用。注意如果只求整数商推荐二分法。如果还需要余数可以先求商再用 余数 被除数 - 除数 × 商 来计算。直接实现带余除法也可以但是代码会复杂很多。6. 完整模板与使用注意事项6.1 整合全部函数代码把以上所有功能整合为一个文件包括字符串转换、比较、加减乘除函数。我给你一份完整的可直接使用的模板#include bits/stdc.h using namespace std; // 字符串转倒序vector vectorint toVector(string s) { vectorint v; for (int i s.size() - 1; i 0; i--) { v.push_back(s[i] - 0); } return v; } // 倒序vector转字符串 string toString(vectorint v) { string s; for (int i v.size() - 1; i 0; i--) { s char(0 v[i]); } return s; } // a b bool cmp(vectorint a, vectorint b) { if (a.size() ! b.size()) return a.size() b.size(); for (int i a.size() - 1; i 0; i--) { if (a[i] ! b[i]) return a[i] b[i]; } return true; } vectorint add(vectorint a, vectorint b) { vectorint c; int carry 0; int len max(a.size(), b.size()); for (int i 0; i len; i) { int sum carry; if (i a.size()) sum a[i]; if (i b.size()) sum b[i]; c.push_back(sum % 10); carry sum / 10; } if (carry) c.push_back(carry); return c; } vectorint sub(vectorint a, vectorint b) { vectorint c; int borrow 0; for (int i 0; i a.size(); i) { int cur a[i] - borrow; if (i b.size()) cur - b[i]; if (cur 0) { cur 10; borrow 1; } else { borrow 0; } c.push_back(cur); } while (c.size() 1 c.back() 0) c.pop_back(); return c; } vectorint mul(vectorint a, vectorint b) { vectorint c(a.size() b.size(), 0); for (int i 0; i a.size(); i) { for (int j 0; j b.size(); j) { c[i j] a[i] * b[j]; } } int carry 0; for (int i 0; i c.size(); i) { int cur c[i] carry; c[i] cur % 10; carry cur / 10; } while (c.size() 1 c.back() 0) c.pop_back(); return c; } vectorint mulInt(vectorint a, int b) { vectorint c; long long carry 0; for (int i 0; i a.size(); i) { long long cur (long long)a[i] * b carry; c.push_back(cur % 10); carry cur / 10; } while (carry) { c.push_back(carry % 10); carry / 10; } while (c.size() 1 c.back() 0) c.pop_back(); return c; } vectorint divByTwo(vectorint a) { vectorint c(a.size(), 0); int carry 0; for (int i a.size() - 1; i 0; i--) { int cur a[i] carry * 10; c[i] cur / 2; carry cur % 2; } while (c.size() 1 c.back() 0) c.pop_back(); return c; } vectorint div(vectorint a, vectorint b) { if (!cmp(a, b)) return vectorint{0}; vectorint one(1, 1); vectorint high(1, 1); while (cmp(mul(high, b), a)) { high add(high, high); } vectorint low(1, 0); vectorint ans; while (cmp(high, low)) { vectorint mid add(low, high); mid divByTwo(mid); if (cmp(mul(mid, b), a)) { ans mid; low add(mid, one); } else { high sub(mid, one); } } return ans; } int main() { string s1, s2; cin s1 s2; vectorint a toVector(s1); vectorint b toVector(s2); cout 加法: toString(add(a, b)) endl; cout 减法: ; if (cmp(a, b)) { cout toString(sub(a, b)) endl; } else { cout - toString(sub(b, a)) endl; } cout 乘法: toString(mul(a, b)) endl; if (b.size() 1 b[0] 0) { cout 除法: 除数不能为0 endl; } else { cout 除法: toString(div(a, b)) endl; } return 0; }6.2 使用时的几个注意事项使用这份模板有几个容易踩的坑。第一字符串传入时不能包含负号或非数字字符。如果需要处理负数先用负号标志位把符号摘出来再去掉负号后调用这套函数最后根据符号规则拼结果。直接传入-123字符-转成数字后会变成负数完全错乱。第二sub函数要求调用前确保 a b。不满足时要么交互参数要么加负号这个判定的责任在调用方。很多bug就出在这里——a和b长度相同但高位比较没做完整导致减法结果出现负数。第三div函数的二分初始上界从1开始翻倍直到high * b a这样可以保证上界一定大于真实商。如果直接用a作为上界虽然也能跑通但第一轮二分的mid会特别大白白多了几轮运算翻倍法更快一些。6.3 关于代码格式与编程风格的调整如果你在在线评测系统中提交#include bits/stdc.h基本都能用。但如果你的编译器更老建议改成标准头文件#include iostream #include vector #include string #include algorithm using namespace std;bits/stdc.h是GCC特有的头文件把C标准库几乎所有内容都包含了。本地用没问题但在一些非GCC的评测环境中可能编译失败。竞赛选手为了方便可以继续用但如果做项目开发还是建议用标准头文件更稳妥、编译也更快。6.4 手写 vector 还是用字符串直接操作我知道有些模板会直接用string来存储大数减法进位时在字符串上直接改字符。这样做也不是不行但有几个明显的缺点字符串的插入和删除是O(n)的需要频繁移动字符性能差。字符类型参与算术运算必须- 0和 0代码里到处是转换容易晕。字符串操作出错时字符编码问题还会带来额外的调试负担。用vectorint的话vector的push_back和pop_back都是O(1)摊还的内存连续性能比 string 好了不止一点。总体上用vectorint是多数竞赛选手和开源大数库的一致选择建议不要走 string 的弯路了。7. 实测验证与常见问题排查7.1 用边界数据测试模板写完模板一定要跑至少这五组数据第一组简单数据12345 98765 111110111110 - 12345 9876512345 * 98765 1219253925。这组数据用来验证基础逻辑。第二组边界数据999 1 10001000 - 999 1999 * 999 998001。这组数据专门测试进位和借位的连续传递。第三组大数乘法123456789 * 987654321 121932631112635269。这个乘积可以直接用普通计算器验证用来检查高精度乘法的进位是否有误。第四组大数除法12345678987654321 / 12345 999648398188余数可以自己验证。这个测试检查二分除法是否正确收敛。第五组零值处理0 0 05 - 5 00 * 123 0123 / 1 123。这些用例帮你排查前导零清除是否正确特别是结果就是0时是否保留了最低位的0。7.2 高频报错排查速查表症状可能原因解决方案加法结果多了前导0循环结束后没处理进位或存储顺序错误检查carry是否有值结果需倒序输出减法结果出现负数未先比较大小就直接调用sub调用前用cmp判定必要时交换参数乘法结果位数不对结果数组开太小a.size()b.size()是最低要求确保数组长度足够处理完进位后再清理前导零除法结果不对或死循环二分边界处理错误检查low和high更新逻辑确保区间收敛输入带前导零没有清理字符串前导零转vector前先去掉前导0或对结果统一去前导零出现乱码或负数数字字符转数字用了s[i]而不是s[i]-0检查所有字符转换处确认减了字符0mulInt乘大数溢出直接用了int没有转long long每步强制转换为long long确保乘法不溢出7.3 我用实测踩过的坑写这套模板的时候我犯过的最经典的错误是减法最后清理前导零时用了while (c.back() 0) c.pop_back();结果计算 5 - 5 0 时把唯一的0也弹掉了最后返回空数组输出直接崩溃。这个bug排查了很久罪魁祸首就是清理条件少加了c.size() 1。后来我养成了一个习惯所有清理前导零的循环一律写while (c.size() 1 c.back() 0)。无论是减法、乘法还是除法中间过程都用这个写法再也没出过问题。另一个坑是二分除法中high的初始值如果用1那cmp(mul(high, b), a)在 a 特别大时会做很多次翻倍运算。比如a有10万位b只有1位时翻倍需要约 log2(10^100000) ≈ 332192 轮每一轮都要做一次完整的mul(high, b)即便每轮乘法很快累计起来也让人等得着急。所以如果商用很大二分上界直接从 a 开始会更快或者用high a配合一次比较即可不必从1翻倍。如果你要处理的是10万级以上的大数还需要考虑内存占用。每个数字用int存10万位的数大约是400KB内存尚可接受。但如果是100万位的数大约是4MB乘法中间结果的vector还会更大这时就要考虑用char或short来存储每一位节省内存甚至考虑用FFT优化乘法。7.4 性能与代码的取舍这套模板的核心目标是竞赛或日常开发中快速解决问题所以我在设计时把“正确性”放在第一位性能其次。加法、减法、乘法都是O(n)或O(n^2)对常规长度的数字毫无压力。除法用二分法虽然复杂度稍高但代码可读性和正确性更可控更不容易在紧张的比赛环境中写错。如果未来需要处理极大数字可以考虑引入FFT加速乘法或者使用现成的GMP库但那就是另一个故事了。在需要“从零手写高精度”的场景下这份模板已经足够扎实。8. 个人经验总结写高精度模板这类代码最忌讳的就是一开始就追求完美和过度优化。我的做法是先把加减乘除四个函数分别写出来每写一个就用几组简单数据验证确认无误后再整合到一起。这样出问题时定位非常快不必在一个大文件里大海捞针。另外一个建议是一定要给模板配上几组固定的“回归测试数据”。每次改动代码后把这几组数据跑一遍能快速发现是否引入了新的问题。比如上文提到的五组数据就是我的固定回归集谁改了我的代码我都会用这几组数据先验一遍。最后想补充一个使用习惯负数处理、进制转换比如10进制转16进制高精度、浮点数高精度计算都不在这份模板范围内。如果你有这些需求建议在这个模板基础上逐步扩展而不是推倒重写。毕竟核心的存储结构和进位逻辑都是通用的扩展起来会非常快。这套高精度模板我已经用了很多年从最初的纯C数组版本到现在的vector版本踩过的坑基本都写在上面了。如果你照着写一遍还遇到问题欢迎对照排查表逐步检查——绝大多数bug都是出在边界条件、前导零清理和进位传递这三个地方。把这些地方看好高精度运算就能成为你的基本功而不是阻碍你拿分的瓶颈。