初识算法——高精度这是我在算法竞赛和日常开发里被“调教”得最久的一课。不管你是刚开始刷题、准备蓝桥杯这类竞赛还是工作中突然要处理大数运算都会发现一个尴尬的现状int不够用、long long也撑不住这时候就得靠高精度算法自己动手造轮子。这篇把高精度加减乘除的思路、代码、坑点从头到尾捋一遍希望能帮你少走弯路。1. 高精度算法的应用场景与核心思路1.1 哪些场景必须用到高精度先说最直观的场景计算两个长度超过几十位的整数。C里long long最多也就到9223372036854775807约等于19位十进制数。如果你要算50!、算Fibonacci(1000)、算两个百万位数字相乘原生类型直接躺平。算法竞赛里比如蓝桥杯、LeetCode这类平台经常会出大数相关的题目高精度就是绕不开的基础技能。除了教学和比赛实际工程里高精度也随处可见。大数运算在密码学、加密算法、科学计算里是核心依赖之一比如RSA密钥生成需要大素数相乘。虽然现代编程语言比如Python自带大整数Java有BigInteger、BigDecimal但底层实现原理依然是高精度算法。金融系统算金额也经常遇到精度问题虽然用的是定点数或Decimal但本质上解决的是同一个问题。也就是说你理解高精度就等于理解了这些基础设施的底层逻辑。还有一个容易被忽略的场景是“精度”而非“范围”。比如高精度定位、高精度测量电流霍尔传感器这类词虽然和高精度计算不是同一个东西但它们共享同一个词根“高精度”——精确到更细粒度。算法领域里高精度计算很多时候也是为了“不丢精度”不只是“不爆范围”。1.2 核心思路数组模拟手算竖式高精度算法的核心思想就一句话用数组模拟我们小学学过的竖式运算。加法竖式逐位相加、进位减法竖式逐位相减、借位乘法竖式逐位相乘、累加除法竖式逐位试商、余数传递。你把笔算过程翻译成代码就是高精度算法。实际实现时一般用数组或者vector来存数字的每一位。有一个细节比较关键存储顺序。我通常采用倒序存储也就是数字的最低位存在数组下标为0的位置最高位存在下标最大的位置。为什么要倒着存因为运算过程中会产生进位、借位最高位可能会变长倒序存储在数组尾部扩展非常方便不用整体移动数据。比如计算999 1结果是1000最高位从3位变成4位正序存储就得把整个数组往后挪倒序存储直接push_back一个新元素就行。这里也解释一下为什么推荐用vector而不是普通数组vector可以用push_back动态扩容用resize控制长度不用担心数组越界写高精度的时候爽很多。而且vector遍历起来和数组一样方便性能差距在竞赛可接受范围内。2. 手把手实现高精度加减法2.1 高精度加法从字符串到进位先说最容易的加法。思路把两个大数用字符串读入转成倒序的vector然后逐位相加并处理进位。伪代码级的实现大概是这样的#include bits/stdc.h using namespace std; vectorint add(vectorint A, vectorint B) { vectorint C; int carry 0; // 进位初始为0 for (int i 0; i max(A.size(), B.size()) || carry; 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; } return C; } int main() { string a, b; cin a b; vectorint A, B; for (int i a.size() - 1; i 0; i--) A.push_back(a[i] - 0); for (int i b.size() - 1; i 0; i--) B.push_back(b[i] - 0); vectorint C add(A, B); for (int i C.size() - 1; i 0; i--) cout C[i]; return 0; }这个代码里有几个点需要细讲。第一个是循环条件i max(A.size(), B.size()) || carry这个写法很高频意思是只要还有一位没处理或者还有进位循环就继续。这样能保证最后一位进位不会被漏掉。比如999 1的过程i循环到第4次时A和B都访问完了但carry还是1所以继续循环一次把carry放进去。第二个是输入转vector的写法a[i] - 0把字符转成数字。注意是从字符串末尾往前遍历这样存到vector里就是倒序了。这个转换写法我建议你写成肌肉记忆后面所有高精度题目都用得上。第三个注意点是输出从vector末尾往前输出打印的是正序数字。需要排除前导零的情况吗加法一般不会产生前导零除非两个数都是0。减法可能会所以减法里要做处理。2.2 高精度减法借位和比较大小减法比加法麻烦一点核心难点在于“谁大谁小”的判断。如果A比B小那结果应该是个负数你需要手动处理符号。我的做法是先写一个cmp函数判断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 sub(vectorint A, vectorint B) { vectorint C; int borrow 0; for (int i 0; i A.size(); i) { int temp A[i] - borrow; if (i B.size()) temp - B[i]; if (temp 0) { temp 10; borrow 1; } else { borrow 0; } C.push_back(temp); } // 去掉前导零保留最后一位 while (C.size() 1 C.back() 0) C.pop_back(); return C; }减法里borrow的处理逻辑和加法里cinarry是对称的。temp 0说明需要借位因为我们的倒序存储借位发生在低位处理完borrow 1下一轮循环就可以减掉这个借位。注意这里borrow只会是0或1因为十进制每一位最多借一位。前导零的排除是个高频坑。比如计算100 - 99结果是1如果不处理C里面会是[1, 0, 0]倒序是001正序输出就变成001了。所以要用while (C.size() 1 C.back() 0) C.pop_back();确保最高位不为0。注意C.size() 1的条件很重要如果两个数相等需要保留一个0不能把结果清空。减法调用时先比较大小bool flag cmp(A, B); if (flag) C sub(A, B); else { C sub(B, A); cout -; }这样符号问题就可以处理了。2.3 实操心得初始化与字符串转换这里分享几个我踩过几次的坑。第一个是字符串转vector时下标容易写错。我建议你直接在纸上画一遍“12345”转倒序的过程字符串下标[0]是‘1’[4]是‘5’转换后vector[0]是5vector[4]是1。多画几遍下标就不会乱了。第二个坑是vector长度问题。加法里max(A.size(), B.size()) || carry这个写法如果A和B都为空不会因为你从字符串转过来或者carry为0循环就停止。减法里直接i A.size()因为我们已经保证A是较大的那个不需要遍历B比A长的部分。第三个是类型问题字符转数字用-0但千万不要把char类型和int直接混淆。9 - 0的结果是57不是9这个错误我写初学代码时犯过不止一次。一个小技巧如果你担心vector长度不一致导致访问越界可以在进行运算前把A和B的size补齐到相同长度比如把短的直接补零这样代码看着更简洁。我给的代码是判断i B.size()两种风格都行看你个人习惯。3. 高精度乘法的进阶玩法3.1 朴素乘法两层循环模拟竖式乘法比加减法复杂一个档次因为要处理“错位相加”。小学学竖式时一位数乘多位数得到一行中间结果然后错位相加。代码实现也是这个逻辑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]; } } for (int i 0; i C.size() - 1; i) { if (C[i] 10) { C[i 1] C[i] / 10; C[i] % 10; } } while (C.size() 1 C.back() 0) C.pop_back(); return C; }这个实现思路是先用两层循环把每一位的乘积累加到对应位置最后统一处理进位。注意乘积数组的长度是A.size() B.size()这是理论上的最大位数。比如999 * 999两个三位数相乘最大可能是6位数998001所以长度设为6没问题。为什么不边乘边进位因为如果A[i] * B[j]很大乘积可能大于一位数边乘边进位的话C[ij]可能还会被之后的循环再次累加容易产生连锁进位处理起来麻烦。统一进位更清晰也更不容易出错。举个例子A [9, 9]倒序表示99B [9, 9]。两层循环累加完C [81, 162, 81]。然后从头进位C[0]81C[1] 8C[0]1C[1]170C[2] 17C[1]0C[2]98C[3] 9C[2]8最后C[3]9。结果是C [1, 0, 8, 9]倒序即9801正确。注意这里统一进位的方法i最外层到C.size() - 2因为最后一个元素没有更高位可以进位了。如果你写到i C.size()会数组越界这是很多人容易踩的坑。3.2 乘法优化压位和FFT朴素乘法的时间复杂度是O(n*m)如果A和B都很长比如几万位这个复杂度就非常感人了。面试或者竞赛中如果遇到大数乘大数会有两种常见优化思路。第一种是压位优化。因为每步进位都是按10进制来算的但我们可以按10000进制来算也就是说vector的每个元素不是0-9的个位数而是0-9999的四位数。这样log10倍的效率提升代码改动也不大。高位和低位的区别只是进位基数从10变成10000乘法的C[ij] A[i] * B[j]不用改进位时用/10000和%10000就行。输出时需要特殊处理比如某一位的值是5但实际应该输出0005。第二种是FFT快速傅里叶变换优化。把乘法转化为卷积运算时间复杂度降到O(n log n)。这个做竞赛的应该听说过写起来代码量大不少像我这种日常刷题的一般用不到就懒得写。但知道有这个方向和原理就行看到相关的题的时候心里有数。3.3 乘法中的边界条件处理乘法有几个边界条件需要单独考虑。第一个是乘数为0的情况。任何数乘0都是0。如果你乘法代码最后有while (C.back()0) pop_back()的处理那C会变成一个空vector所以要用C.size() 1作为条件避免全部pop掉保留一个0。第二个是乘数长度不对称的情况。比如A很长B很短两层循环依然能正确处理因为短的vector访问到不存在的下标时被循环条件挡掉了。第三个是“压位”输出时的格式问题。如果采用压位输出时要补零。比如某一位是37但是4位压位那要输出0037。这里容易出错我的建议是十进制压位用printf(%04d)或者手动补前导零。4. 高精度除法复杂但思路清晰4.1 高精度除以低精度一个循环搞定高精度除法分两种情况除数分母在基础整数类型范围内和除数也是高精度。先讲简单的高精度除以低精度。思路是从最高位开始逐位处理每一位的“当前值”等于上一位的余数*10 当前位数字然后做除法得到当前位的商和新的余数。用代码表达就是vectorint div(vectorint A, int b, int r) { vectorint C; r 0; for (int i A.size() - 1; i 0; i--) { r r * 10 A[i]; C.push_back(r / b); r % b; } reverse(C.begin(), C.end()); while (C.size() 1 C.back() 0) C.pop_back(); return C; }注意这里遍历顺序是正序从最高位开始和加减乘不一样。因为除法必须从高位往低位算余数一直传递下去。C这里存的是“正序”的商所以最后要reverse一下再去除前导零。举个例子1234 / 3。i从3开始A[3]4表示千位1倒序存储时A[2]2我具体推演一下。A倒序存储时A[0]4、A[1]3、A[2]2、A[3]1。上面代码里for (int i A.size() - 1; i 0; i--)i3时r01011商0余1i2时r110212商4余0i1时r01033商1余0i0时r01044商1余1。C初始为[0,4,1,1]reverse后[1,1,4,0]pop_back掉末尾0得[1,1,4]即商114余数1。正确。这里有个细节如果被除数本身就小于除数比如100/999上面会得到商0余100也是正确的。4.2 高精度除以高精度模拟长除法如果除数和被除数都是高精度那就不能简单地用除法符号了。思路还是模拟长除法也就是小学时学的“试商”过程。核心逻辑从被除数的最高位开始每次尝试将当前“余数”和一位被除数拼起来然后用高精度比较和减法来“猜”这一位的商。这个过程类似二分找商或者直接顺序尝试0-9找出最大的k使得“除数 * k 当前被除数”。代码写起来会比较长关键步骤是用一个remainder代表当前余数高精度。循环每次把remainder * 10 被除数当前位得到当前被除数。用二分或顺序枚举0-9找到一个最大的k满足divsor * k 当前被除数。商的一位就是k余数更新为当前被除数 - 除数 * k。其中需要实现两个辅助函数高精度乘法前面已经讲了、高精度比较cmp前面减法那节已经讲了。这个写一遍下来相当于把前面所有高精度操作复习一遍。但说实话高精度除以高精度的代码复杂度和出错率比前面几个都高。如果只是在竞赛中遇到我会先想题目有没有其他解法比如用费马小定理、用二进制拆分等方式绕开大除法。如果确实需要建议先用小的测试用例把代码跑通比如123456789 / 321再逐步增大规模。4.3 除法中的经典坑余数为0与前导零除法代码里“前导零”的处理和减法很像但有一个额外要注意的点如果商的某一位是0比如被除数中间有0比如10002 / 9商的第2位就是0在正序存储时如果不小心pop掉所有0会把中间的零也去掉。所以pop零时必须在reverse之后先判断长度再pop掉末尾的零且不能把结果全是0的情况处理成空vector。余数传递的时候也要注意余数可能很大不能用int存最好也用高精度。比如高位余数是999999...乘10之后再加当前位可能位数又变多了。所以高精度除以高精度余数也得是vector。另一个经典坑被除数和除数相同长度但被除数比除数小时试商结果为0余数为被除数本身。这块如果比较函数写得不对很容易算错。5. 高精度算法的常见坑与排查技巧实录5.1 典型Bug速查表问题现象根本原因解决方法计算结果多出前导零减法或乘法没有处理前导零在返回前while (C.size() 1 C.back() 0) C.pop_back()高精度加法最后一位进位丢失循环条件没包含or carry循环条件写成i max(A.size(), B.size())字符串转vector时结果颠倒遍历方向反了确认for (int i s.size() - 1; i 0; i--)两个很大的数相乘时结果错误乘积数组长度不够初始设置为A.size() B.size()输出结果全部为0时变成空过度pop_back保留末尾一个0用size() 1判断除以0导致崩溃未处理被0除除法前检查b是否为0是则报错5.2 我的排查思路我调试高精度算法时有一个固定套路。第一步先拿小数据测试比如两个两位数相加、相减、相乘用笔算验证结果。这一步通过后再测试边界数据比如9991、1000-999、999*999、100000/3。这些边界数据最容易暴露前导零和进位问题。第二步是用Python当作“验证机”。反正在本机跑个Python脚本很轻松算个几百位的加减乘除完全没问题。我写C高精度代码然后用Python算同样的用例比对输出效率比我手工心算高。这个方法强烈推荐尤其适合竞赛练习。第三步是加调试输出。在关键运算的循环里打印出每一步的中间结果。比如加法里打印每一次的sum和carry乘法里打印左右两层循环后C的状态。看着中间结果能迅速锁定是哪个环节的进位错了。5.3 提升信心的自测用例我把自己常用的自测用例整理一下你写完代码可以直接拿去测试加法9999 1 10000减法1000000 - 1 999999减法1 - 999 -998乘法123456789 * 987654321用计算器对一下除法123456789 / 9 13717421除法100000 / 999 100余100这些用例能覆盖大多数基础Bug。注意减法里1 - 999这种负数情况你如果没实现负号处理建议也补上一个-的输出逻辑不然后面写题会吃亏。6. 高精度算法的场景延展与学习路径6.1 从高精度计算到高精度优化“高精度”这个词在算法领域还有更广义的理解不只是大整数计算还包括提高计算精度的各种手段。比如搜索热词里有“高精度定位”、“高精度遥感”、“MPPT算法”和“高精度测量电流霍尔传感器”这些本质上都是在追求“更高的精度分辨率”。但我个人觉得如果你刚接触“高精度”先把大数计算吃透最重要。因为它是算法竞赛里最基础、最核心的工具之一而且所有其他高级算法多项式、FFT、数论、加密都可能建立在大数运算之上。基础不牢后面都是空中楼阁。6.2 从加减乘除迈向更高级的算法学完高精度加减乘除之后你可以自然衔接几个方向大数阶乘涉及高精度乘法和循环、大数开方用牛顿迭代加高精度乘除、高精度与数论结合比如大数取模、常系数线性递推以及FFT优化乘法。这些内容都是在“初识高精度”之后的进阶路径。如果目标是竞赛建议把高精度封装成一套完整的模板包括字符串转vector、高精度比较、加、减、乘、除、取模。我自己的模板里还会额外封装“类型转换”比如long long转成高精度vector因为比赛中经常要用到。模板写好后自己能默写出来速度和准确性就都上去了。6.3 聊聊语言选择如果你用的是Python内置大整数根本不需要手写高精度刷题时直接用int就行。但C就没这个福利认真手写是必须的。Java的BigInteger虽然好用但在竞赛中有时需要优化性能所以了解底层原理也有价值。我的建议是如果用C做题高精度必须手写如果为了快速验证可以用Python做参考。另外说下Julia这种语言搜索热词里也出现了“julia高精度浮点数和整数”。Julia原生支持任意精度的数值计算不过性能和C高精度模板比还是有差距。学过C高精度再看这类语言内置能力你会更能体会底层逻辑。结尾聊点实在的我在刚开始学高精度的时候总觉得自己在写“幼稚的模拟题”不就是小学竖式嘛能难到哪去结果一顿操作猛如虎一提交全是错。后来仔细排查才发现不是思路问题是细节问题进位没进对、前导零没删干净、数组越界、字符转数字忘记减‘0’。我自己的体会是高精度算法是“思路容易细节致命”的典型代表刷题遇错时千万别急着看题解先自己把中间过程打印出来对着竖式一步一步猜很快就能定位问题。希望你也能在一次次的调试中把高精度变成肌肉记忆。