C++高精度除法实现：从原理到工程实践详解

2026/7/22 10:25:57

1. 项目概述：为什么我们需要高精度除法？

在C++的标准库中，我们处理整数除法通常使用int、long long等内置类型。然而，这些类型有其固定的位数限制。比如，一个64位的long long最大也只能表示大约19位的十进制整数。当你需要计算一个100位甚至1000位的整数除以另一个大整数时，比如计算圆周率到小数点后一万位，或者处理金融、密码学中的超大数值运算，标准数据类型就完全无能为力了。这时，“高精度计算”就成了我们必须自己动手实现的领域。

高精度计算的核心思想并不复杂：既然一个变量存不下，我们就用数组或字符串来模拟这个超长的数字。数组的每一个元素（比如一个int）只存储数字的一位或几位（为了效率，通常存储多位），然后我们手动实现小学时学过的竖式加减乘除算法。加减乘相对直观，而除法，尤其是高精度除以高精度的除法，是其中逻辑最复杂、边界情况最多、也最能体现算法设计功底的部分。

网上能找到的很多高精度除法示例，要么只实现了高精度除以低精度（即除数是普通整数），要么代码冗长晦涩，缺乏清晰的步骤解释和异常处理。今天，我将从一个一线开发者的角度，手把手带你实现一个完整、健壮且高效的高精度除以高精度算法。我们会从最基础的存储设计开始，逐步推导算法原理，最终给出可直接编译运行的、附带详尽注释的C++源码。无论你是正在备战算法竞赛的学生，还是需要处理特殊计算任务的开发者，这篇文章都能让你彻底搞懂高精度除法的“里子”。

2. 核心思路与数据结构设计

在动手写代码之前，我们必须先解决两个根本问题：如何表示一个大数？以及，高精度除法的核心算法是什么？

2.1 大数的表示：从字符串到整数数组

最直观的表示法是用字符串std::string，用户输入和最终输出都很方便。但在运算过程中，频繁的字符数字转换（‘0’到0）和逐位操作效率较低。更通用的做法是使用整数数组（如std::vector<int>），并采用“压位”技巧来提升效率。

所谓“压位”，就是数组的每个元素不只存储一位十进制数，而是存储多位。例如，我们可以让每个int存储0到9999之间的一个数，即一个“万进制”位。这样，一个100位的十进制数，只需要一个长度为25的数组（100 / 4）即可表示，运算次数大幅减少。为了输出方便，我们通常选择压的位数是10的幂，如BASE = 10000（万进制），每个元素对应4位十进制数。

我们定义以下结构体和常量：

const int BASE = 10000; // 压位基数，每个单元存储0-9999 const int BASE_DIGITS = 4; // 每个单元对应的十进制位数 struct BigInt { std::vector<int> digits; // 数字位，下标0对应最低位（个位） int sign; // 符号，1为正，-1为负 // 构造函数等... };

这里采用“小端序”存储，即digits[0]是个位（在万进制下，是低4位），digits[1]是万位，以此类推。这符合我们手工计算从低位开始的习惯。符号单独用sign存储。

2.2 高精度除法算法选型：模拟竖式与试商法

高精度除以高精度（BigInt / BigInt）的算法，本质是模拟我们小学学的竖式除法，但需要适配我们的数组存储结构。假设我们计算 A / B，目标是得到商 Q 和余数 R，使得 A = B * Q + R，且 0 <= R < B。

最直接的“减法模拟”法——不断地从被除数中减去除数，直到不够减为止——在两者相差巨大时（如 10^100 / 2），复杂度会退化到 O(Q)，完全不可接受。

因此，工业级和竞赛级的实现普遍采用“试商法”。其核心步骤是：

规范化：先处理符号，转化为两个正数相除。
比较与特判：如果被除数 A 小于除数 B，商直接为0，余数就是 A。
位数对齐：通过将除数和被除数同时乘以一个适当的 10 的幂（相当于在末尾补零），使得除数的最高位至少达到BASE/2。这一步是关键，它能极大提高后续试商的准确性和稳定性。
逐位确定商：从被除数当前最高位开始，结合次高位，估算出一个“试商值”。
调整与修正：由于是估算，试商值可能偏大或偏小，需要通过乘法和减法进行检验和修正。
收集商位：将修正后的正确商位存入商的数组中。
循环与移位：处理完一位后，移除已处理的部分，继续处理下一位。

其中，第3步的“规范化”（或称为“标准化”）和第4步的“试商”是算法的灵魂，也是容易出错的地方。我们将用一个具体的数字例子贯穿下面的讲解，确保每一步都清晰可见。

注意：有些教程会介绍基于long long的更大基数的试商（如BASE=10^9），其原理完全相同，但试商时的中间计算结果可能溢出，需要格外小心。我们选择万进制（BASE=10000）是为了在32位int环境下确保乘法（试商值乘以除数）不会溢出，简化代码，优先保证正确性和可理解性。

3. 核心函数实现细节拆解

接下来，我们深入到代码层面，拆解几个最关键的辅助函数和核心除法函数。我会先给出函数原型和功能描述，然后剖析实现细节和注意事项。

3.1 基础工具函数：比较、移位与减法

高精度除法严重依赖几个基础操作：比较两个正的大数大小、左移（乘以基数BASE）和带借位的减法。

3.1.1 绝对值比较函数compareAbs这个函数比较两个BigInt的绝对值大小，忽略符号。它从最高位开始向下比较，这是大数运算的常规套路。

// 比较两个正BigInt的绝对值大小。返回1表示a>b，0表示a==b，-1表示a<b。 int compareAbs(const BigInt& a, const BigInt& b) const { if (a.digits.size() != b.digits.size()) { return a.digits.size() > b.digits.size() ? 1 : -1; } for (int i = a.digits.size() - 1; i >= 0; --i) { if (a.digits[i] != b.digits[i]) { return a.digits[i] > b.digits[i] ? 1 : -1; } } return 0; }

实操心得：循环一定要从最高位向最低位进行。digits数组可能包含前导零（尽管我们会维护去除它们），但比较函数必须能正确处理。在除法过程中，我们经常需要比较被除数当前部分和除数的大小。

3.1.2 原地减法函数subAbs这个函数假设a >= b，并从a中减去b的绝对值，结果存储在a中。它模拟了手工减法的借位过程。

// 假设 a >= b，计算 a = a - b (绝对值相减) void subAbs(BigInt& a, const BigInt& b) { int carry = 0; for (size_t i = 0; i < b.digits.size() || carry; ++i) { int sub = carry; if (i < b.digits.size()) { sub += b.digits[i]; } if (a.digits[i] < sub) { a.digits[i] += BASE - sub; carry = 1; } else { a.digits[i] -= sub; carry = 0; } } // 减法完成后，移除可能产生的前导零 while (a.digits.size() > 1 && a.digits.back() == 0) { a.digits.pop_back(); } }

踩坑记录：这里的借位逻辑是初学者容易糊涂的地方。a.digits[i] < sub时，说明本位不够减，需要从上一位借一个BASE过来，所以本位变成a.digits[i] + BASE - sub，同时设置carry=1表示下一位要多减1。循环结束后，务必清理前导零，保持数据的“干净”，否则会影响后续的比较和输出。

3.2 核心除法函数`divide`的实现

这是整个高精度库中最长的函数。我们将它分解成几个逻辑块，并用一个例子来同步说明。

假设我们要计算A = 123456789除以B = 4567。在我们的万进制表示下：A表示为[6789, 2345, 1]（即 110^8 + 234510^4 + 6789）B表示为[4567]。

步骤1：特判与符号处理

if (b.isZero()) throw std::runtime_error("Division by zero!"); if (compareAbs(a, b) < 0) { // |a| < |b|， 商为0，余数为a return std::make_pair(BigInt(0), a); } int res_sign = a.sign * b.sign; BigInt dividend = a.abs(); // 被除数取正 BigInt divisor = b.abs(); // 除数取正

首先处理除零错误。如果被除数绝对值小于除数，商就是0，余数就是被除数本身（注意保留原符号）。然后确定商的符号（同号得正，异号得负），并将两数都转为正数进行后续计算。

步骤2：规范化除数这是提升试商准确率的关键一步。我们希望除数的最高位divisor.digits.back()至少大于等于BASE/2（即5000）。

int norm = BASE / (divisor.digits.back() + 1); dividend.mulSmall(norm); // 被除数也乘以相同的因子，保证等式不变 divisor.mulSmall(norm);

mulSmall是一个实现大数乘以普通整数的函数。这里norm是一个缩放因子。为什么是BASE / (最高位 + 1)？这样可以确保缩放后的除数最高位落在[BASE/2, BASE)区间内。试商时，我们用被除数的前两位除以除数最高位，这个缩放能使得估算的商误差非常小，通常就在正负1以内，极大减少了后续调整的次数。

在我们的例子中，除数最高位是4567，BASE=10000，norm = 10000 / (4567+1) ≈ 2。A和B都乘以2，变成A' = 246913578,B' = 9134。现在B'的最高位是9134，已经大于5000。

步骤3：初始化与主循环

int n = divisor.digits.size(); int m = dividend.digits.size() - n; BigInt quotient; // 商 quotient.digits.resize(std::max(m + 1, 1), 0); // 商最多有 m+1 位 // 将除数左移m位，使其与被除数的当前高位对齐 BigInt shiftedDivisor = divisor; shiftedDivisor.shiftLeft(m);

m是预计商的位数（被除数位数减去除数位数，可能为0或负，上面特判已处理）。我们创建一个足够大的商数组。然后，我们复制一份除数，并将其左移m位（相当于乘以BASE^m），使其最高位与被除数的当前最高位区域对齐。

主循环从商的最低位（对应被除数的最高位区域）开始，逐步向低位计算：

for (int i = m; i >= 0; --i) { // 1. 估算试商值 q_hat // 2. 检验并修正 q_hat // 3. 记录商位 // 4. 从被除数中减去 q_hat * divisor // 5. 将除数右移一位（除以BASE），准备下一次迭代 }

步骤4：试商与修正——算法最精妙的部分在循环体内，我们首先要估算当前位的商q_hat。

// 取被除数的“当前”高两位进行估算。 // 注意：因为可能发生借位，被除数位数是动态变化的，我们用 j = n + i 来索引当前高位区域。 int j = n + i; long long top = (j < dividend.digits.size() ? dividend.digits[j] : 0); top = top * BASE + (j-1 < dividend.digits.size() ? dividend.digits[j-1] : 0); int q_hat = top / divisor.digits.back();

这里top组合了被除数的第j位和第j-1位，形成一个“两位数”（在万进制下，这是一个范围在0到约BASE^2的数），用它除以除数的最高位，得到一个试商值q_hat。

由于我们之前做了规范化，这个q_hat非常接近真实的商，但可能偏大（最多大1或2）。接下来是关键的修正步骤：

// 将试商值限制在 [0, BASE-1] 范围内 q_hat = std::min(q_hat, BASE - 1); // 检验：计算 q_hat * divisor，并与被除数当前高位部分比较 BigInt test = divisor; test.mulSmall(q_hat); test.shiftLeft(i); // 对齐到正确的位置 while (compareAbs(dividend, test) < 0) { // 如果 test 太大了，说明 q_hat 偏大，减1重试 q_hat--; test.subSmall(divisor, i); // 从test中减去除数（对齐后） }

mulSmall和subSmall需要能处理对齐偏移。这个while循环就是修正过程，确保我们减去的test不会超过当前的被除数。由于q_hat初始估计很准，这个循环很少执行超过2次。

步骤5：记录商与更新被除数修正后的q_hat就是当前位的最终商。

quotient.digits[i] = q_hat; // 存储商位 // 从被除数中减去 q_hat * (除数左移i位) BigInt toSubtract = divisor; toSubtract.mulSmall(q_hat); toSubtract.shiftLeft(i); subAbs(dividend, toSubtract);

执行减法后，dividend就变成了新的、更小的被除数（即余数的一部分），用于下一位商的计算。

步骤6：后处理循环结束后，dividend中剩下的就是最终的余数，但别忘了我们最初乘以了缩放因子norm。所以真正的余数需要除以norm。

// 去除前导零 quotient.trim(); dividend.divSmall(norm); // 余数需要除以之前乘的norm quotient.sign = res_sign; dividend.sign = a.sign; // 余数的符号同被除数（在数学定义中通常如此） return std::make_pair(quotient, dividend);

trim函数移除商中的前导零。divSmall实现大数除以普通整数，这里用于将余数缩放回原来的尺度。

4. 完整源码与关键函数注解

下面给出一个完整、可运行的高精度整数类BigInt的核心部分，重点关注除法及其相关函数。代码包含了必要的构造函数、输入输出和辅助函数。

#include <iostream> #include <vector> #include <string> #include <algorithm> #include <stdexcept> #include <utility> // for std::pair class BigInt { private: std::vector<int> digits; // 小端序，每个元素存储0-9999 int sign; // 1 正， -1 负 static const int BASE = 10000; static const int BASE_DIGITS = 4; // 工具函数：移除前导零 void trim() { while (!digits.empty() && digits.back() == 0) { digits.pop_back(); } if (digits.empty()) { sign = 1; digits.push_back(0); } } // 比较绝对值大小 int compareAbs(const BigInt& other) const { if (digits.size() != other.digits.size()) { return digits.size() > other.digits.size() ? 1 : -1; } for (int i = digits.size() - 1; i >= 0; --i) { if (digits[i] != other.digits[i]) { return digits[i] > other.digits[i] ? 1 : -1; } } return 0; } // 绝对值加法（假设均为正） void addAbs(const BigInt& other) { int carry = 0; size_t maxSize = std::max(digits.size(), other.digits.size()); digits.resize(maxSize, 0); for (size_t i = 0; i < maxSize || carry; ++i) { if (i == digits.size()) digits.push_back(0); digits[i] += carry + (i < other.digits.size() ? other.digits[i] : 0); carry = digits[i] >= BASE; if (carry) digits[i] -= BASE; } trim(); } // 绝对值减法（假设 this >= other） void subAbs(const BigInt& other) { int carry = 0; for (size_t i = 0; i < other.digits.size() || carry; ++i) { int sub = carry + (i < other.digits.size() ? other.digits[i] : 0); if (digits[i] < sub) { digits[i] += BASE - sub; carry = 1; } else { digits[i] -= sub; carry = 0; } } trim(); } // 乘以一个小整数 void mulSmall(int val) { if (val == 0) { *this = BigInt(0); return; } if (val < 0) { sign *= -1; val = -val; } int carry = 0; for (size_t i = 0; i < digits.size() || carry; ++i) { if (i == digits.size()) digits.push_back(0); long long cur = carry + digits[i] * 1LL * val; digits[i] = cur % BASE; carry = cur / BASE; } trim(); } // 除以一个小整数，返回余数 int divSmall(int divisor) { if (divisor == 0) throw std::runtime_error("Division by zero!"); int remainder = 0; for (int i = digits.size() - 1; i >= 0; --i) { long long cur = digits[i] + remainder * 1LL * BASE; digits[i] = cur / divisor; remainder = cur % divisor; } trim(); return remainder; } // 左移k位（相当于乘以 BASE^k） void shiftLeft(int k) { if (isZero()) return; digits.insert(digits.begin(), k, 0); } public: // 构造函数 BigInt() : sign(1), digits(1, 0) {} BigInt(long long v) { if (v < 0) { sign = -1; v = -v; } else { sign = 1; } if (v == 0) digits.push_back(0); while (v > 0) { digits.push_back(v % BASE); v /= BASE; } } BigInt(const std::string& s) { fromString(s); } // 从字符串解析 void fromString(const std::string& s) { sign = 1; digits.clear(); int pos = 0; if (s[pos] == '-') { sign = -1; ++pos; } else if (s[pos] == '+') { ++pos; } for (int i = s.size() - 1; i >= pos; i -= BASE_DIGITS) { int digit = 0; for (int j = std::max(pos, i - BASE_DIGITS + 1); j <= i; ++j) { digit = digit * 10 + (s[j] - '0'); } digits.push_back(digit); } trim(); } // 转换为字符串 std::string toString() const { if (isZero()) return "0"; std::string res; if (sign == -1) res.push_back('-'); res += std::to_string(digits.back()); for (int i = digits.size() - 2; i >= 0; --i) { std::string block = std::to_string(digits[i]); // 补足前导零，保证每个块都是4位（最高位除外） res.append(BASE_DIGITS - block.size(), '0'); res += block; } return res; } // 判断是否为零 bool isZero() const { return digits.size() == 1 && digits[0] == 0; } // 取绝对值 BigInt abs() const { BigInt res = *this; res.sign = 1; return res; } // 高精度除法，返回商和余数 std::pair<BigInt, BigInt> divide(const BigInt& other) const { if (other.isZero()) { throw std::runtime_error("BigInt: division by zero"); } BigInt a = *this; BigInt b = other; // 处理符号和比较 int res_sign = a.sign * b.sign; a.sign = b.sign = 1; // 转为正数处理 if (a.compareAbs(b) < 0) { // |a| < |b|, 商为0，余数为a BigInt quotient(0); BigInt remainder = a; remainder.sign = this->sign; // 余数符号同被除数 return {quotient, remainder}; } // 规范化：使除数的最高位 >= BASE/2 int norm = BASE / (b.digits.back() + 1); a.mulSmall(norm); b.mulSmall(norm); int n = b.digits.size(); int m = a.digits.size() - n; BigInt quotient; quotient.digits.resize(std::max(m + 1, 1), 0); quotient.sign = res_sign; // 主循环：逐位确定商 for (int i = m; i >= 0; --i) { // 估算试商值 q_hat // 取被除数的高“两位” (在BASE进制下) int j = n + i; long long top = (j < a.digits.size() ? a.digits[j] : 0) * 1LL * BASE; top += (j-1 < a.digits.size() ? a.digits[j-1] : 0); int q_hat = top / b.digits.back(); q_hat = std::min(q_hat, BASE - 1); // 确保不超过基数 // 检验并修正 q_hat BigInt test = b; test.mulSmall(q_hat); test.shiftLeft(i); // 对齐到当前位置 while (a.compareAbs(test) < 0) { // 估算值偏大，减1 q_hat--; // 从test中减去除数b（对齐后） BigInt subtractor = b; subtractor.shiftLeft(i); test.subAbs(subtractor); } // 存储商位 quotient.digits[i] = q_hat; // 从被除数a中减去 q_hat * b * (BASE^i) BigInt toSubtract = b; toSubtract.mulSmall(q_hat); toSubtract.shiftLeft(i); a.subAbs(toSubtract); } // 后处理 quotient.trim(); // 余数需要除以之前乘的norm a.divSmall(norm); a.sign = this->sign; // 余数符号同原被除数 return {quotient, a}; } // 重载除法运算符，只返回商 BigInt operator/(const BigInt& other) const { return divide(other).first; } // 重载取模运算符，只返回余数 BigInt operator%(const BigInt& other) const { return divide(other).second; } // 为了方便测试，重载输出运算符 friend std::ostream& operator<<(std::ostream& os, const BigInt& num) { os << num.toString(); return os; } friend std::istream& operator>>(std::istream& is, BigInt& num) { std::string s; is >> s; num.fromString(s); return is; } }; // 示例主函数 int main() { try { BigInt a, b; std::cout << "请输入被除数 a: "; std::cin >> a; std::cout << "请输入除数 b: "; std::cin >> b; auto result = a.divide(b); BigInt quotient = result.first; BigInt remainder = result.second; std::cout << "商: " << quotient << std::endl; std::cout << "余数: " << remainder << std::endl; // 验证： a == b * quotient + remainder BigInt验证 = b * quotient + remainder; std::cout << "验证 a == b*q + r: " << (a.toString() == 验证.toString() ? "正确" : "错误") << std::endl; } catch (const std::exception& e) { std::cerr << "错误: " << e.what() << std::endl; } return 0; }

（注：为了代码简洁，上述代码省略了乘法运算符*和加法运算符+的重载实现，它们需要调用mulSmall和addAbs等方法，实现相对直接，重点是展示除法逻辑。）

5. 常见问题与调试技巧实录

即使理解了算法，实现过程中也极易出错。下面是我在实现和教学过程中总结的几个典型“坑”及其解决方案。

问题1：试商值q_hat溢出或不准

现象：程序运行结果完全错误，或者在某些特定数字（如除数最高位很小）时崩溃。
根因：
1. 估算q_hat时，top的计算可能溢出。top是long long类型，必须确保(digits[j] * BASE + digits[j-1])在long long范围内。我们的BASE=10000，digits[i]最大为9999，9999*10000+9999=99,999,999，远小于long long最大值，安全。
2. 没有进行规范化（norm）或规范化因子计算错误，导致除数最高位过小，使得q_hat的初始估算误差很大，修正循环次数过多甚至无法修正。
解决：
- 务必实现并调用规范化步骤。计算norm = BASE / (除数最高位 + 1)。
- 在估算q_hat后，立即用q_hat = std::min(q_hat, BASE-1)进行截断，这是必须的安全措施。
- 在修正循环中，确保test的减法是正确对齐的。我见过很多错误是因为在修正时，直接test.mulSmall(q_hat)后没有重新对齐，或者对齐的位数i弄错了。

问题2：减法后产生前导零，导致比较出错

现象：在循环中，某一步之后商突然变得巨大，或者程序进入死循环。
根因：从被除数a中减去toSubtract后，a的最高几位可能变成0。如果此时没有及时清理这些前导零，那么a.digits.size()就会比预期的大，导致下一轮循环中计算j = n + i时索引越界，或者取a.digits[j]时访问到无意义的0，从而严重干扰top的计算和大小比较。
解决：在subAbs函数和任何可能改变数字位数的操作（如divSmall）的最后，必须调用trim()函数移除尾部的0。在除法主循环中，每次更新a（被除数）后，可以显式检查并清理其高位的零，但更稳妥的是保证subAbs等基础操作自身是“干净”的。

问题3：余数的符号和值不对

现象：商看起来正确，但余数为负或绝对值大于等于除数。
根因：
1. 符号处理错误。数学上，余数的符号通常与被除数相同。我们在函数开头保存了this->sign，最后应将其赋给余数a.sign。
2. 忘记了反向缩放。我们一开始将a和b都乘以了norm，最终余数a也需要除以norm来还原。divSmall函数在实现时要注意处理整除和余数。
解决：
- 明确约定：divide函数返回的余数r满足0 <= |r| < |b|，且符号与被除数a相同。
- 在返回前，确保执行了a.divSmall(norm)。
- 编写单元测试，特别测试边界情况：a正负、b正负、a绝对值小于b、a是b的整数倍等。

问题4：性能瓶颈

现象：计算超大的数（如10000位除以5000位）时速度很慢。
根因：
1. 试商修正循环可能退化为多次减法。虽然规范化后很少发生，但极端情况下仍可能。
2. 基础操作（如mulSmall,subAbs）使用朴素的O(n)算法，当位数极大时成为瓶颈。
3. 没有使用更高效的乘法算法（如Karatsuba或FFT）。
优化方向：
- 确保规范化：这是提升试商准确率、减少修正次数的性价比最高的方法。
- 使用更大的基数：如果使用64位整数，可以将BASE设置为10^9（压9位），这样数组更短，每次循环处理的数据量更少。但要注意中间计算（如top）要用128位整数（__int128或unsigned long long结合处理）。
- 升级乘法算法：当位数超过几百时，朴素O(n^2)的乘法会成为瓶颈。可以考虑实现Karatsuba算法（O(n^1.585)）。对于竞技编程或超大规模计算，可能需要FFT（O(n log n)）。但这会极大增加代码复杂度，需要根据实际需求权衡。

调试技巧：

单元测试法：编写一系列测试用例，从小数字开始，逐步增大。使用Python内置的大整数（int）作为参照，因为Python整数精度无限，是完美的对拍工具。
打印中间状态：在除法循环中，打印出每一步的i（商位索引）、q_hat（试商值）、被除数a的当前值。这是定位问题最直接的方法。
边界值测试：重点测试除数为1、被除数为0、被除数和除数相等、商为0、余数为0等情况。
内存与效率分析：使用valgrind等工具检查内存泄漏。对于性能测试，可以计算两个几百位的大数相除，与成熟的库（如GMP）对比结果和耗时。

实现一个健壮的高精度除法，是对你C++编程能力、算法理解力和调试耐心的综合考验。它没有黑魔法，就是对竖式除法的严格模拟，并谨慎处理每一个边界条件。当你最终看到它正确计算出123456789012345678901234567890 / 987654321时，那种成就感是无可替代的。这份代码和其中的细节思考，希望能成为你解决更大、更复杂问题的一块坚实基石。