1. 高精度减法到底在解决什么问题1.1 当 int 和 long long 都不够用的时候我先说一个很典型的使用场景也是我最早接触高精度减法的契机。当时在写一个简单的表达式计算器本来以为整数运算用long long就万事大吉了结果用户输入了一个 20 位的数字做减法程序直接溢出输出变成了负数。那一刻才意识到内置数据类型的天花板是真实存在的。很多初学者会问什么情况下能用到高精度减法其实不只是在算法竞赛、OJ 做题很多业务场景也会碰到。比如身份证号、银行卡号的某段数值处理比如大文件分片后的偏移量计算再比如区块链场景里的整数哈希比对都会出现超过 64 位整数范围的数字。在 C 里unsigned long long最大也只能存到18446744073709551615约 1.8×10¹⁹一旦数值超过这个范围内置类型就无能为力了。高精度减法是高精度运算系列里最基础、也最容易被忽视的一块。很多人学高精度直接从加法跳到乘法减法只是草草看两眼结果真到用的时候在借位、负数、前导零这些细节上疯狂翻车。这篇就专门把减法拆开揉碎从原理到实现再到踩坑一次讲清楚。1.2 高精度减法和加法、乘法的核心区别高精度运算的本质就是回到小学列竖式的方法把大数字拆成一位一位的数组来模拟人工计算。这个思路对加减乘除都适用但减法有自己的特殊性。先说加减的区别。加法只需要从低位到高位逐位相加超过 10 就进位逻辑非常线性。减法却涉及到借位而且可能出现结果前面一堆零的情况处理完还要去掉前导零。更麻烦的是减法结果可能是负数——这是加法和乘法理论都不需要额外操心的问题乘法结果要么正要么零加法同号也很少考虑负数场景。一旦要考虑负数就必须先判断被减数和减数谁大然后决定计算结果的正负符号并且在输出时把负号加上。再一个区别是减法的“每一步”操作其实比加法更简单但控制流程更复杂。加法的每一位最多就是a[i] b[i] carry而减法的每一位是a[i] - b[i] - borrow一旦小于 0 就要向高位借 1。这里面的borrow状态会在整个遍历过程中传递稍微不留神就会算错。我见过不少人写减法代码看起来没问题跑简单样例也对但一到类似1000 - 999的用例就出问题就是因为借位链和去除前导零的处理顺序不对。所以在实现上减法不能直接照搬加法的模板需要单独设计一套流程。这篇文章里我会把每一步的思考过程都记录下来包括为什么不先反转字符串、为什么要预先比较大小、借位状态怎么传播这些才是高精度减法真正的难点所在。2. 核心思路拆解从字符串到数组的逆向思维2.1 为什么用字符串存储大整数在 C/C 里做高精度运算第一步永远是解决“怎么存”的问题。int存不下、long long也存不下那就只能用数组或者字符串。常规做法是用字符串读入大整数然后逆序存到int数组里。为什么逆序因为减法和加法都是从低位开始运算的。如果正序存储低位在数组末尾高位在数组开头计算到最高位之后可能还要进位/借位数组前面就要不断插入元素效率低而且代码复杂。逆序之后数组下标 0 就是最低位逐位运算时下标一路递增非常自然。还有一个细节字符串读入后下标 0 是最高位字符形式。如果要直接按正序操作得先把字符串反转或者从字符串从后往前遍历存入数组。我个人习惯是先反转字符串再存数组这样后面逻辑清晰不会在循环边界上绕来绕去。2.2 比较大小减法必须先解决符号问题加法和乘法不需要提前比较两个数的大小——反正结果符号是确定的同号为正异号为负再单独处理。但减法不同a - b和b - a的结果互为相反数。如果每次都硬着头皮用小的减大的然后算完再补救很容易出错。常规做法是写一个比较函数compare(a, b)判断两个数字字符串或两个数组的大小关系先比较长度。长度长的数字更大因为位数多代表值更大不考虑前导零的情况下。长度相同时从高位到低位逐位比较找到第一个不同的数字谁大谁就更大。如果所有位都相同则两个数相等。这个比较函数写完之后减法主流程就分成两种情况a b直接算a - b结果为正。a b算b - a然后在结果前面加负号。这样处理之后后面的逐位减法就永远不需要考虑“减出负数”的问题——因为在a b的前提下每一位在借位之后的结果一定是非负的。这个判断是整个高精度减法正确性的基石。2.3 借位机制逐位计算与状态传递核心计算过程其实很简单但细节很重要。假设两个数组a和b都已经逆序存储la和lb分别是有效长度我们保证a b那么逐位减法可以这样描述对于第i位从 0 开始diff a[i] - borrow - b[i]这里borrow是上一位借位状态0 或 1。如果diff 0说明不够减需要向高位借 1那么diff 10 borrow 1否则borrow 0然后把diff存入结果数组。这里有一个隐藏问题b可能比a短。比如1000 - 999中b是三位数a是四位数遍历到第 3 位时b[3]不存在需要按 0 处理。所以循环条件不能两个数组一起走到头而是应该遍历a的所有位对b越界位置补 0。借位状态的传播是整个算法的灵魂。最高位如果还需要借位说明a b但我们在入口处已经保证了a b所以不会发生这种情况。这也是为什么预先比较大小这么重要——它让借位逻辑变得非常简单。2.4 去除前导零小数减大数相关细节减法结果容易出现前导零。最典型的例子1000 - 999 1如果直接按数组逐位打印结果是0001这是错的。所以计算完成后必须把结果数组中高位的 0 全部去掉直到只剩一位。有一种特殊情况要单独注意123 - 123 0。如果老老实实去掉前导零最后数组里应该只剩一个0不能是空数组。所以循环条件是while (len 1 result[len - 1] 0) { len--; }这个len 1的边界条件很关键。没有它遇到结果为 0 的情况len会一路减到 0后面打印的时候就傻眼了。2.5 负数结果的处理顺序再看a b的情况。入口判断之后我们交换a和b的值再执行同样的逐位减法然后输出时在结果前面加一个负号。这里有一个容易踩的坑交换操作必须在比较之后、计算之前完成否则比较判断就没意义了。而且交换是在数组层面进行的如果传入的是字符串建议直接用swap(a_str, b_str)交换字符串再重新转换为数组这样更省心。另外输出负号的位置也要注意。结果是负数的场景比如1 - 9999 -9998先输出-再输出去掉前导零后的数字部分。不能输出成-09998前导零处理必须放在负号拼接之前完成。3. 完整实现C 手写高精度减法的全过程3.1 从字符串到数组输入处理的标准姿势先定义数据结构。我用vectorint存储数字每位存 0-9 的值。读入字符串后将其逆序转换#include iostream #include string #include vector #include algorithm using namespace std; // 将字符串数字转为逆序数组低位在前 vectorint strToVec(const string s) { vectorint res; for (int i s.size() - 1; i 0; --i) { res.push_back(s[i] - 0); } return res; }这里有一个细节值得说明为什么要用vectorint而不是vectorchar虽然每个元素都是 0-9但用int在后续运算中不需要每次做类型转换代码更干净性能影响也可以忽略不计。在算法竞赛中很多选手习惯用vectorchar省内存但个人建议新手先用int搞清楚逻辑再优化不迟。3.2 比较函数的实现与测试要点比较函数可以基于字符串实现也可以基于数组实现。如果后面还要反复用到比如高精度除法里也要比较建议直接做在数组上因为数组逆序存储后比较逻辑和字符串差不多只是方向反了字符串从下标 0 开始是高到低数组从size()-1开始是高到低。// 比较两个逆序数组返回 true 表示 a b bool compareVec(const vectorint a, const 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; // 完全相等 }注意这里的等号处理。如果两个数完全相等compareVec返回true也就是说后续计算会走a - b的分支结果为 0。这个结果没问题但在主流程中一定不要漏掉a b返回true的情况否则会错误地走到负数分支输出-0这就是一个隐藏的逻辑 bug。测试比较函数时除了常规的123 45、999 1000一定要测123 123和1000 999这类边界用例。很多初写高精度的人会在相等情况下栽跟头因为长度相同、逐位比较到最后没有不同位却返回了false。3.3 减法主函数借位链与边界处理接下来是核心的减法函数// 计算 result a - b调用前保证 a b vectorint subVec(const vectorint a, const vectorint b) { vectorint result; int borrow 0; for (size_t i 0; i a.size(); i) { int bVal (i b.size()) ? b[i] : 0; int diff a[i] - borrow - bVal; if (diff 0) { diff 10; borrow 1; } else { borrow 0; } result.push_back(diff); } // 去除前导零保留至少一位 while (result.size() 1 result.back() 0) { result.pop_back(); } return result; }这里有几个要点逐一说明循环条件是i a.size()因为已经保证a b所以a的长度一定不小于b遍历a的所有位是安全的。bVal的补 0 逻辑放在了循环内部当i超过b的长度时按 0 处理。这比在外部把b填充到和a一样长更简洁也省内存。borrow的状态在每一位计算后即时更新不是累加也不是提前算。减法借位不会跨多位每位最多借 1所以borrow只可能是 0 或 1。去除前导零的循环写在函数内部这样调用方不用每次单独处理。但要注意这里没有处理a b的情况那个在主函数中完成。3.4 整合输入输出带符号、去前导零的完整代码主函数负责判断符号和调用核心减法输出部分单独封装int main() { string s1, s2; cin s1 s2; // 注意这里为了方便假设输入没有前导零如果有需要额外去除 vectorint a strToVec(s1); vectorint b strToVec(s2); bool negative false; vectorint result; if (compareVec(a, b)) { result subVec(a, b); } else { negative true; result subVec(b, a); // 交换顺序保证大的减小的 } if (negative) cout -; for (int i result.size() - 1; i 0; --i) { cout result[i]; } cout endl; return 0; }这里把负号输出放在了最前面然后从高位到低位打印结果数组。很多人容易在这里搞反——数组是逆序存储的打印必须从size()-1倒着来。如果正序打印123 - 45会输出873而不是78因为在数组里低位在前正序打印等于倒着读数字。3.5 压位优化快 10 倍的进阶写法基础版本按 10 进制存储每一位只存 0-9。对于大部分题目和场景来说这个版本已经完全够用。但如果数据规模很大比如 10 万位数字的减法逐位计算的常数就比较大了。这时候可以用压位技巧让数组的每一位存一个更大的基数。常见做法是每 4 位数字压成一个int存储即基数为 10000。这样数组长度直接缩小到原来的 1/4循环次数也相应减少。减法逻辑几乎不用改只需要把基数从 10 改成 10000并且处理借位时改成diff 0时diff BASE。const int BASE 10000; vectorint subVecPacked(const vectorint a, const vectorint b) { vectorint result; int borrow 0; for (size_t i 0; i a.size(); i) { int bVal (i b.size()) ? b[i] : 0; int diff a[i] - borrow - bVal; if (diff 0) { diff BASE; borrow 1; } else { borrow 0; } result.push_back(diff); } while (result.size() 1 result.back() 0) { result.pop_back(); } return result; }压位后的输出需要额外注意除了最高位那块之外其他块输出时必须补前导零。比如BASE 10000结果为1和234两块输出应该是1234不能把 234 直接打印成1234如果块值是 234 而不是 0234就是1234碰巧没问题但如果块值是 34就应该是10034而不是134。这块细节比较多单独写一个辅助函数处理。4. 高精度减法在 Python、Java、JavaScript 里的不同打开方式4.1 Python自带大整数但你可以模拟加法的思路很多读者可能想Python 的int本身就支持任意精度为什么还要学高精度减法这是对的在实际工程里我们确实不需要在 Python 里手写高精度。但在理解算法原理、应对某些不允许使用内置大整数的 OJ 题库或者需要模拟底层计算逻辑的场景中手写一遍仍然有意义。而且掌握原理之后用 Python 去验证其他语言实现是否正确非常方便——拿 Python 的int运算结果当基准测试用例这是我在调试 C 高精度代码时最常用的手段。Python 模拟高精度减法的代码和 C 思路完全一致def str_to_vec(s): return [int(ch) for ch in reversed(s)] def compare_vec(a, b): if len(a) ! len(b): return len(a) len(b) for i in range(len(a) - 1, -1, -1): if a[i] ! b[i]: return a[i] b[i] return True def sub_vec(a, b): result [] borrow 0 for i in range(len(a)): b_val b[i] if i len(b) else 0 diff a[i] - borrow - b_val if diff 0: diff 10 borrow 1 else: borrow 0 result.append(diff) while len(result) 1 and result[-1] 0: result.pop() return result def big_sub(s1, s2): a str_to_vec(s1) b str_to_vec(s2) neg False if compare_vec(a, b): result sub_vec(a, b) else: neg True result sub_vec(b, a) res_str .join(str(x) for x in reversed(result)) return - res_str if neg else res_str用 Python 模拟一遍最大的好处是可以随时拿内置int来对拍验证import random for _ in range(10000): x random.randint(-10**50, 10**50) y random.randint(-10**50, 10**50) # 注意这个模拟只处理非负整数负数自行扩展这也是我强烈建议的做法——学高精度一定要会写对拍器靠随机数据批量验证而不是盯着几个固定用例看半天。4.2 JavaBigInteger 与手写对比Java 里自带java.math.BigInteger功能非常强大。日常开发中直接用BigInteger.subtract()即可不需要自己写。但在算法竞赛中部分判题环境支持 Java 但不允许使用BigInteger多见于一些教学型 OJ这时候就得手写。Java 手写高精度减法的思路和 C 几乎一模一样只是语法稍有不同用ArrayListInteger或int[]存储注意数组扩容和长度管理。public static int[] subArrays(int[] a, int[] b) { // 调用前保证 a b int[] result new int[a.length]; int borrow 0; for (int i 0; i a.length; i) { int bVal i b.length ? b[i] : 0; int diff a[i] - borrow - bVal; if (diff 0) { diff 10; borrow 1; } else { borrow 0; } result[i] diff; } // 处理长度可改为返回有效长度 return result; }Java 里int[]长度固定有效位数需要额外用一个变量记录或者在返回后手动去除前导零。这些细节在实现时要特别留意。4.3 JavaScriptNumber 精度陷阱与 BigIntJavaScript 的Number类型是双精度浮点超过2^53 - 19007199254740991就会出现精度丢失。所以在前端处理大数运算时要么用BigInt要么手写字符串模拟。BigInt是 ES2020 引入的可以直接处理任意大的整数const a 123456789012345678901234567890n; const b 98765432109876543210987654321n; const result a - b; console.log(result.toString());BigInt的减法很简单但在某些极端场景下比如需要兼容不支持BigInt的旧环境手写字符串模拟仍然是一种兜底方案。JavaScript 手写高精度减法的循环思路和其他语言一致只是注意parseInt和String.fromCharCode的边界。其实我在做前端项目时发现很多情况下大数计算并不是性能瓶颈而是容易在边界输入上出问题。比如用户输入一个超出Number.MAX_SAFE_INTEGER的数字如果没有预先做字符串类型的判断直接做Number(a) - Number(b)结果就是错的。所以前端处理大整数第一原则是永远不要在Number上做大数运算。5. 常见问题与调试实录这些坑我替你先踩了5.1 前导零问题1000 - 999 0001 怎么修这是高精度减法里出现频率最高的 bug。原因很简单逐位计算结果数组里高位确实有 0但打印时没有去掉。修复方法就是我在 3.3 节写的while (result.size() 1 result.back() 0) { result.pop_back(); }这里有一个容易忽略的前提result.back()是最高位因为数组是逆序存储的最后 push 进去的元素就是最高位。如果你把数组正序存储这个逻辑就要反着写。每一个高精度实现都必须先搞清楚自己的数组方向再去写去除前导零的逻辑。5.2 借位传递错误999 - 100 变成 809很多人第一次写借位时会这样写diff a[i] - b[i] - borrow; if (a[i] b[i]) { diff 10; borrow 1; }这个写法在borrow 0时是对的但一旦上一位借了位当前位的判断就不对了。必须把borrow也纳入判断diff a[i] - b[i] - borrow; if (diff 0) { diff 10; borrow 1; }判断条件应该基于diff是否为负而不是a[i] b[i]。因为即使a[i] b[i]如果上一位留下了borrow 1这一位依然可能减出负数比如a[i] 5b[i] 4但上一位借位 1diff 5 - 4 - 1 0没问题但如果a[i] 4b[i] 4borrow 1diff -1必须借位。只看a[i] b[i]就会漏掉这种情况。5.3 负数边界100 - 999 -899 与 100 - 100 0负数输出的逻辑看起来简单但边界用例依然容易出错。100 - 100 0的结果不是-0这很重要。因为在比较函数里相等返回true所以会走a b的分支不会进入负数逻辑自然不会输出负号。所以只要你正确实现了compareVec对相等情况的处理就不会出现-0的问题。如果你发现输出变成-0大概率是compareVec的等号判断写反了。100 - 999 -899的正确输出是-899不是-0899也不是-8990。按照我们的流程先比较发现a b交换后计算999 - 100 899去掉前导零然后加负号输出。只要去除前导零在加负号之前完成就不会出问题。5.4 性能考量什么时候需要压位高精度减法的性能瓶颈主要在循环次数和内存访问。对于长度 100 位以内的数字直接用 10 进制逐位计算完全没有问题。但如果长度到 10⁵ 甚至 10⁶ 级别逐位循环的常数就很可观了。这时候推荐压位存储每 4 位压成一个int循环次数减少到原来的 1/4。再配合快读快写性能提升非常明显。我在处理一个 10 万位大数相减的测试用例时基础版跑了大约 5 毫秒压位后降到 1 毫秒左右效果立竿见影。另外还有一个小技巧如果只做减法而且两个数长度差距很大可以先判断长度差超过一定阈值时直接跳过逐位比较减少不必要的计算。不过这种优化在减法里收益不大真正需要的是在比较函数上优化——比较函数如果被频繁调用比如在除法实现里它的性能同样会影响整体表现。5.5 对拍测试高精度代码的正确性保障高精度代码几乎不可能一次写对尤其是减法这种边界条件极多的算法。我的建议是写完不能只靠几个手写用例一定要写对拍程序。对拍思路很简单用 Python 或 Java 的内置大整数作为基准实现。随机生成大量测试数据覆盖不同长度、不同边界条件。将手写实现的结果和基准实现的结果做比对。遇到不一致缩小数据范围定位是哪个环节出了问题。以 C 和 Python 对拍为例C 程序读入两个字符串输出结果Python 脚本生成随机大数分别调用 C 程序和内置int运算比对输出。import random import subprocess for i in range(10000): a random.randint(0, 10**50) b random.randint(0, 10**50) sa, sb str(a), str(b) # 调用 C 程序 p subprocess.run([./big_sub], inputf{sa}\n{sb}\n, capture_outputTrue, textTrue) cpp_result p.stdout.strip() # Python 基准 py_result str(a - b) if cpp_result ! py_result: print(fError: {sa} - {sb}) print(fC: {cpp_result}) print(fPython: {py_result}) break else: print(All tests passed!)对拍是验证高精度代码最有效的手段没有之一。手写几个用例永远只能证明“这几个用例没问题”对拍能在几分钟内帮你跑完几万个随机用例覆盖面完全不是一个量级。6. 从减法出发高精度运算体系的构建6.1 加法、乘法、除法的衔接关系学会减法之后高精度运算的其余部分就顺理成章了。加法、乘法、除法都是围绕“数组模拟竖式”这同一个核心思想展开的。加法和减法共用一个比较判断思路减法里a b的处理就能用到加法的逻辑。乘法的实现会用到加法和位移的概念本质上是多次加法的整合。除法的实现最复杂会用到减法试商时反复减也会用到比较函数。所以很多人把高精度学习顺序定为“加减乘除”这个顺序是合理的。减法作为承上启下的关键环节学扎实了后面就轻松不少。6.2 如何用高精度减法实现浮点数处理高精度不只在整数领域有应用在处理定点小数时同样需要减法。思路是把小数部分单独存放在另一个数组里运算时按位对齐借位可以跨整数部分和小数部分的边界。举个例子3.14 - 1.99按整数运算相当于314 - 199 115然后根据小数位数还原为1.15。这个过程本质上就是用整数减法模拟小数减法。在实际的高精度小数库中对齐小数位、处理借位、输出小数点的逻辑都是在加减法基础上扩展出来的。6.3 高精度减法在算法竞赛中的典型应用在算法竞赛中高精度减法很少单独出现更多是作为其他算法的一个子步骤。典型场景有大整数阶乘、斐波那契数列计算先乘后减。大整数取模运算的辅助步骤。分数运算中分数约分需要求最大公约数辗转相除法里可能会涉及减法。大整数进制转换。我在刷题时发现很多题目看着是“数论题”实际上核心是高精度运算。如果高精度减法实现得不够稳整个题就跑不对尤其是那种结果差一位就判错的题目前导零或符号错误都会直接导致 WA。6.4 扩展思路从减法到模逆元、高精度分数的应用如果你已经能够熟练实现高精度减法下一步可以考虑更多扩展。比如结合高精度减法实现高精度最大公约数辗转相除法进而实现高精度分数运算。这类封装好的工具类在需要精确计算例如金融场景的利率计算时非常有用。我对高精度减法最深的体会是它虽然简单却是所有高精度运算的基础。但凡你想处理超出内置类型范围的数值计算减法就是你绕不过去的坎。把这个坎迈过去后面的路就顺了。