C++高精度算法实现：从原理到工程实践，手把手构建大整数运算库

1. 项目概述：当整型不再够用

在C++的世界里，我们习惯了int、long long这些内置数据类型带来的便利。处理日常计算，它们游刃有余。但当你需要计算一个100位的阶乘，或者处理银行系统中涉及天文数字金额的利息计算时，这些固定位宽的整型就显得力不从心了。long long的最大值大约是9.22e18，一个20位的数字就能让它“溢出”，导致计算结果完全错误。这就是“高精度算法”登场的时刻。

高精度算法，有时也被称为“大整数运算”，其核心思想并不复杂：既然一个变量装不下，那就用多个变量来装。它通过数组、字符串或者容器，手动模拟我们在小学就学会的竖式计算过程，实现理论上无限位数（仅受限于内存）的加、减、乘、除等运算。这不仅仅是学术上的奇技淫巧，在密码学（RSA密钥）、科学计算（高精度圆周率）、金融系统以及信息学竞赛中，它都是不可或缺的基础工具。

本文将以C++为工具，从零开始，手把手带你实现一套完整的高精度算法。我们将从最基础的数据存储讲起，逐步实现加、减、乘、除四大运算，并深入探讨其中的优化技巧和无数我踩过的“坑”。无论你是正在备战信息学奥赛的学生，还是需要在项目中处理大数运算的开发者，这篇文章都将为你提供一份可直接“抄作业”的、经过实战检验的代码与思路。

2. 高精度算法的核心设计与存储模型

2.1 为什么选择“倒序存储”？

几乎所有高精度算法的入门教程都会告诉你：用数组存储，并且要倒序。比如数字12345，我们会存储在数组里num[0]=5, num[1]=4, num[2]=3, num[3]=2, num[4]=1。新手看到这里往往会疑惑：这不是自找麻烦吗？正着存不是更符合直觉？

这里面的门道，在于运算的便利性。竖式计算是从最低位（个位）开始的。如果我们正序存储（num[0]=1, num[1]=2,...），当两个数位数不同时，对位就会变得非常麻烦。例如123 + 45，你需要将45的个位5去和123的百位1对齐吗？显然不对。你需要先找到个位的位置，这增加了无谓的判断。

而采用倒序存储，数组下标天然就代表了位数（下标0是个位，1是十位，以此类推）。进行加法时，我们只需要从i=0开始循环，将a[i]与b[i]相加，处理进位，然后写入结果数组的c[i]。整个过程干净利落，代码逻辑极其清晰。这个设计选择是无数前辈经验总结的最优解，务必理解并接受它。

2.2 数据结构选型：数组、字符串还是vector？

确定了倒序存储，接下来是用什么来存。常见的有三种选择：

1. C风格数组（int num[1000]）：最原始，最直接。需要预先定义一个足够大的固定长度（如1000），可能会造成内存浪费，或者长度不够用。优点是访问速度极快，代码简单。
2. C++字符串（std::string）：将数字以字符形式存储。string本身是动态的，长度灵活。但字符‘5’需要减去‘0’才能得到数字5进行运算，运算完又要加回‘0’才能存回去，稍微有些繁琐。不过，它非常便于直接从输入流读取大数。
3. C++向量（std::vector<int>）：我个人最推荐的方式。它兼具了数组的快速随机访问和动态扩容的能力。我们可以用vector的每个元素存储数字的一位（0-9）。这是现代C++中实现高精度最优雅和高效的方式。

为了兼顾性能、易用性和教学清晰度，本文将主要采用std::vector<int>作为存储结构，并在关键部分对比不同选择的优劣。我们会定义一个BigInt类来封装这个大整数。

class BigInt { public: std::vector<int> digits; // 倒序存储每一位数字 bool isNegative; // 符号位，true为负 // 构造函数 BigInt(const std::string &s = "0") { fromString(s); } // ... 其他成员函数 private: void fromString(const std::string &s) { digits.clear(); isNegative = (s[0] == '-'); // 从字符串末尾（个位）开始，倒序存入vector for (int i = s.length() - 1; i >= (isNegative ? 1 : 0); --i) { digits.push_back(s[i] - '0'); } trim(); // 去除前导零 } void trim() { while (digits.size() > 1 && digits.back() == 0) { digits.pop_back(); } if (digits.size() == 1 && digits[0] == 0) { isNegative = false; // 统一处理-0的情况 } } };

注意：trim()函数至关重要。在运算过程中，尤其是乘法和除法，可能会产生大量的前导零（比如00123）。这些零不仅浪费空间，还会在比较和输出时造成错误。因此，在每次可能产生前导零的运算后，都必须调用trim()进行清理。

3. 四大核心运算的逐行实现与优化

3.1 高精度加法：进位是唯一难点

加法的逻辑最直白，就是模拟竖式加法：对应位相加，加上低位的进位，然后计算当前位的值和新进位。

BigInt BigInt::operator+(const BigInt &rhs) const { if (isNegative != rhs.isNegative) { // 异号转化为减法，这里先省略，后文详述 // 例如 a + (-b) 等同于 a - b BigInt tmp = rhs; tmp.isNegative = !tmp.isNegative; return *this - tmp; } BigInt result; result.isNegative = isNegative; // 同号相加，符号不变 result.digits.clear(); int carry = 0; // 进位 size_t maxLen = std::max(digits.size(), rhs.digits.size()); for (size_t i = 0; i < maxLen || carry; ++i) { int sum = carry; if (i < digits.size()) sum += digits[i]; if (i < rhs.digits.size()) sum += rhs.digits[i]; result.digits.push_back(sum % 10); carry = sum / 10; } // 加法不会产生前导零（除非0+0），但为了规范还是trim一下 return result; }

实操心得：注意循环条件i < maxLen || carry。这是关键！即使两个数的所有位都处理完了（i >= maxLen），如果最后还有进位（carry == 1），循环必须继续，将这个进位作为新的最高位。这是新手最容易遗漏的点，会导致999 + 1的结果错误地变成000（实际应为1000）。

3.2 高精度减法：借位与结果符号的判断

减法比加法复杂，因为涉及借位和结果符号的判断。核心思路是先判断两个数的大小，确保用大数减小数，并最终确定结果的符号。

BigInt BigInt::operator-(const BigInt &rhs) const { if (isNegative != rhs.isNegative) { // 异号转化为加法，例如 a - (-b) = a + b BigInt tmp = rhs; tmp.isNegative = !tmp.isNegative; return *this + tmp; } // 同号相减：比较绝对值大小 const BigInt &a = *this; const BigInt &b = rhs; bool resultNegative = false; // 比较绝对值的函数 absLessThan 需要另外实现 if (a.isNegative) { // 都是负数， (-a) - (-b) = -(a - b) = b - a if (absLessThan(a, b)) { // |a| < |b|, 结果为正 return b.absSub(a); } else { // |a| >= |b|, 结果为负 BigInt result = a.absSub(b); result.isNegative = true; return result; } } else { // 都是正数 if (absLessThan(a, b)) { // a < b, 结果为负 BigInt result = b.absSub(a); result.isNegative = true; return result; } else { // a >= b, 结果为正 return a.absSub(b); } } } // 辅助函数：假设this和rhs都是正数，且this >= rhs BigInt BigInt::absSub(const BigInt &rhs) const { BigInt result; result.digits.clear(); int borrow = 0; // 借位 for (size_t i = 0; i < digits.size(); ++i) { int diff = digits[i] - borrow; if (i < rhs.digits.size()) { diff -= rhs.digits[i]; } if (diff < 0) { diff += 10; borrow = 1; } else { borrow = 0; } result.digits.push_back(diff); } result.trim(); // 至关重要！减法会产生前导零，如100-99=01 return result; }

避坑指南：减法最棘手的部分是符号处理。我的经验是，先将所有情况转化为“两个正数相减”，最后再贴上正确的符号。上面代码中的absSub函数就是做这个“脏活”的，它假设被减数绝对值大于减数。在实现比较函数absLessThan时，要从最高位开始逐位比较，注意先比较位数，位数多的绝对值一定大。

3.3 高精度乘法：从O(n²)到优化

最朴素的乘法是模拟竖式，将乘数的每一位与被乘数相乘，然后错位相加。时间复杂度是O(n²)，其中n是位数。

// 朴素乘法 BigInt BigInt::operator*(const BigInt &rhs) const { BigInt result; result.digits.resize(digits.size() + rhs.digits.size(), 0); // 结果最大位数 for (size_t i = 0; i < digits.size(); ++i) { int carry = 0; for (size_t j = 0; j < rhs.digits.size() || carry; ++j) { // 关键：result.digits[i+j] 是累加的位置 long long cur = result.digits[i + j] + (long long)digits[i] * (j < rhs.digits.size() ? rhs.digits[j] : 0) + carry; result.digits[i + j] = cur % 10; carry = cur / 10; } } result.isNegative = (isNegative != rhs.isNegative); // 同号得正，异号得负 result.trim(); return result; }

性能瓶颈与优化：当数字非常大（比如上万位）时，O(n²)的复杂度是无法接受的。在实际项目或竞赛中，我们通常会采用更高效的算法：

• Karatsuba算法：将大数分成两部分，通过三次递归乘法代替四次，将复杂度降至约O(n^1.585)。
• FFT（快速傅里叶变换）乘法：将大数乘法转化为多项式乘法，利用FFT在O(n log n)时间内完成，这是目前已知最快的大数乘法算法之一。

对于绝大多数应用场景（位数在几千以内），朴素乘法已经足够。但了解这些优化方向，是进阶的必经之路。一个简单的优化是，在内外层循环中，确保外层循环是位数较短的那个数，可以减少一些计算量。

3.4 高精度除法：最复杂的运算

除法是高精度运算中最复杂的一种，因为商是一位一位试出来的。常用的是“模拟竖式除法”。

这里实现一个高精度整数除以低精度整数（int）的版本，相对简单，也很有用（例如求阶乘后除以一个数）。

// 高精度除以低精度（int），返回商，remainder返回余数 BigInt BigInt::divide(int divisor, int &remainder) const { if (divisor == 0) { throw std::runtime_error("Division by zero!"); } BigInt quotient; quotient.digits.resize(digits.size(), 0); // 商最多和被除数位数一样多 long long rem = 0; // 余数，用long long防止中间溢出 // 从最高位开始除（注意我们是倒序存储，所以最高位在最后） for (int i = (int)digits.size() - 1; i >= 0; --i) { rem = rem * 10 + digits[i]; quotient.digits[i] = rem / divisor; // 注意这里商也是倒序存的，但计算顺序是正序 rem %= divisor; } quotient.trim(); remainder = (int)rem; quotient.isNegative = (isNegative != (divisor < 0)); return quotient; }

关于高精度除以高精度：这是一个更复杂的主题，通常采用“试商法”。基本思路是：将除数通过左移操作（乘以10的幂）对齐到和被除数相同的最高位，然后估算商（例如，用被除数的前几位除以除数的最高位加一），再进行减法调整。由于实现复杂且代码冗长，它常常是信息学竞赛的压轴题。一个更工程化的思路是：将高精度数转换为字符串或二进制流，利用数学库（如GMP）或者转换为浮点数进行估算，再精细调整。但这已经超出了基础实现的范畴。

4. 完整实现、测试与性能调优实录

4.1 一个可运行的BigInt类框架

将上述模块组合起来，并补充比较运算符、输入输出，我们就得到了一个可用的BigInt类雏形。

#include <iostream> #include <vector> #include <string> #include <algorithm> #include <stdexcept> class BigInt { private: std::vector<int> digits; bool isNegative; void trim() { /* 如前所述 */ } void fromString(const std::string &s) { /* 如前所述 */ } bool absLessThan(const BigInt &rhs) const; // 比较绝对值 BigInt absSub(const BigInt &rhs) const; // 绝对值减法 public: // 构造函数 BigInt(const std::string &s = "0") { fromString(s); } BigInt(long long num) { /* 从long long构造，略 */ } // 算术运算符 BigInt operator+(const BigInt &rhs) const; BigInt operator-(const BigInt &rhs) const; BigInt operator*(const BigInt &rhs) const; BigInt operator/(int divisor) const; // 仅实现除以int // 比较运算符 bool operator<(const BigInt &rhs) const; bool operator==(const BigInt &rhs) const; // 友元函数，方便输入输出 friend std::ostream& operator<<(std::ostream &os, const BigInt &bi); friend std::istream& operator>>(std::istream &is, BigInt &bi); }; // 比较绝对值 bool BigInt::absLessThan(const BigInt &rhs) const { if (digits.size() != rhs.digits.size()) { return digits.size() < rhs.digits.size(); } for (int i = (int)digits.size() - 1; i >= 0; --i) { if (digits[i] != rhs.digits[i]) { return digits[i] < rhs.digits[i]; } } return false; // 相等 } // 输出运算符 std::ostream& operator<<(std::ostream &os, const BigInt &bi) { if (bi.isNegative) os << '-'; for (int i = (int)bi.digits.size() - 1; i >= 0; --i) { os << bi.digits[i]; } if (bi.digits.empty()) os << '0'; // 处理空值 return os; } // 输入运算符 std::istream& operator>>(std::istream &is, BigInt &bi) { std::string s; is >> s; bi.fromString(s); return is; } // 主函数测试 int main() { BigInt a, b; std::cout << "Enter two big integers: "; std::cin >> a >> b; std::cout << "a + b = " << (a + b) << std::endl; std::cout << "a - b = " << (a - b) << std::endl; std::cout << "a * b = " << (a * b) << std::endl; int divisor = 7; int rem; BigInt quotient = a.divide(divisor, rem); std::cout << "a / " << divisor << " = " << quotient << " ... " << rem << std::endl; return 0; }

4.2 典型问题排查与性能优化技巧

在实际编码和调试中，你会遇到各种各样的问题。下面这个表格总结了我遇到的一些典型“坑”及其解决方案：

重点聊聊“压位优化”：这是将高精度算法性能提升一个数量级的关键技巧。我们不再用一个int存一个十进制位（0-9），而是用一个int存多位十进制数，比如存4位（0-9999）。这样，存储空间立刻减少为原来的1/4，同时，加法、乘法的循环次数也同比减少。

例如，用int数组digits，每个元素存储0-9999。那么数字123456789将被存储为digits[0]=6789,digits[1]=2345,digits[2]=1（依然是倒序，但以万进制为单位）。运算时，进位基数从10变成了10000。输出时需要特别注意，除了最高位，中间的每一位都要用printf(“%04d”, digits[i])这样的方式补零输出。

压位实现的复杂度会显著上升，但带来的性能收益是巨大的。对于竞赛和严肃项目，这是必选项。

4.3 进阶应用：计算N的阶乘

高精度算法一个经典的应用就是计算大数阶乘（N!）。这完美展示了其价值。

BigInt factorial(int n) { BigInt result("1"); for (int i = 2; i <= n; ++i) { // 这里需要实现 BigInt * int 的重载，比高精*高精快 result = result * i; // 假设已重载 BigInt::operator*(int) } return result; } // 重载 BigInt * int BigInt BigInt::operator*(int rhs) const { if (rhs == 0) return BigInt("0"); BigInt result; long long carry = 0; for (size_t i = 0; i < digits.size() || carry; ++i) { if (i < digits.size()) { carry += (long long)digits[i] * rhs; } result.digits.push_back(carry % 10); carry /= 10; } result.trim(); result.isNegative = (isNegative != (rhs < 0)); return result; }

计算1000的阶乘，用上面的代码（未压位）可能已经能感觉到延迟了。计算10000的阶乘，朴素算法就会非常慢。此时，压位优化和更高效的乘法算法就显得尤为重要。你可以尝试用这个函数计算factorial(100)，并观察结果的位数（应该有158位），来验证你实现的正确性。

5. 工程实践建议与扩展方向

当你掌握了基础的高精度四则运算后，可以思考如何将其工程化，以及还有哪些可以探索的方向。

1. 封装与接口设计： 一个完善的BigInt类应该提供完整的运算符重载（+,-,*,/,%,+=,-=等），支持与内置整型的混合运算，实现完整的比较运算符（<,<=,>,>=,==,!=）。此外，像pow（幂运算）、sqrt（开平方，可用牛顿迭代法配合高精度实现）、gcd（最大公约数）等常用函数也值得封装。

2. 性能权衡：

• 对于教学和一般应用：使用vector<int>存储十进制位，实现朴素算法，代码清晰易懂。
• 对于竞赛和中等性能要求：实现压位存储（如万进制），并采用Karatsuba乘法。
• 对于极限性能要求（如密码学）：使用专门的库，如GNU MP (GMP)。这是一个用C编写的高度优化的大数运算库，经过了数十年的打磨，性能远超自己实现的版本。在C++中可以通过gmpxx.h接口来使用。

3. 扩展方向：

• 浮点数高精度：处理小数，需要独立存储整数部分和小数部分，并定义小数点位置。运算规则更复杂，特别是除法。
• 高精度与数论结合：实现模幂运算（用于RSA）、Miller-Rabin素数测试等。
• 与其他算法结合：例如，在高精度运算中融入快速傅里叶变换（FFT）来实现超大规模整数的乘法。

实现一套高精度算法，是对你编程基本功、算法思维和耐心的一次全面锻炼。从最初的“为什么这么存”的疑惑，到后来对进位借位逻辑的娴熟，再到主动思考压位和FFT优化，这个过程本身就是极大的收获。我建议你不要止步于看懂本文的代码，最好能自己从头到尾敲一遍，并在过程中尝试添加新的功能（比如%运算符、+=复合赋值），或者尝试将其改造成压位存储。当你能够用它流畅地计算2^1000或者1000!时，你对整数运算和C++语言的理解，一定会到达一个新的层次。