C++大整数类实现：从原理到工程实践，突破内置整数限制

1. 项目概述：为什么我们需要自己实现BigInteger？

在C++的标准库里，int、long long这些内置整数类型大家用起来得心应手，直到你某天需要计算一个100位的阶乘，或者处理RSA加密算法里那些天文数字般的密钥。这时，编译器会毫不留情地告诉你：溢出了。这就是内置整数类型的边界，它们的位数是固定的，由硬件和编译器决定，无法处理任意大的整数。BigInteger（大整数）类就是为了突破这个限制而生的，它允许我们像操作普通整数一样，进行加、减、乘、除等运算，但数字的位数只受限于计算机的内存。

你可能在LeetCode上刷到过“字符串相加”、“两数相乘（大数版）”这类题目，它们本质上就是BigInteger的简化版面试题。自己动手实现一个完整的BigInteger类，远不止是为了解决一道算法题。这个过程会让你深入理解：

• 数据的底层表示：计算机如何存储和操作远超寄存器容量的数据？
• 基本算法的工程化：如何将小学竖式计算的原理，转化为高效、健壮的代码？
• 内存管理：在C++中，如何安全、高效地管理动态数组，避免内存泄漏和越界？
• 运算符重载：如何让自定义类型拥有和内置类型一样的语法糖，写出a + b * c这样直观的表达式？

接下来，我将带你从零开始，构建一个支持基础四则运算、具备良好接口的BigInteger类。我们会采用最直观、也最易于理解的实现方式——基于十进制字符串或数组的表示，并逐步优化。无论你是想深化C++理解，应对面试，还是为某个需要大数运算的项目打基础，这篇内容都能提供一条清晰的路径。

2. 核心设计：如何表示一个任意大的整数？

实现BigInteger的第一步，也是最重要的一步，是确定它在内存中的表示形式。这直接决定了后续所有算法的效率和实现的复杂度。

2.1 存储方案选型：为什么选择十进制数组？

常见的存储方案主要有三种：

1. 二进制位存储：像内置类型一样，用vector<bool>或位运算来存储每一个二进制位。这种方式空间效率最高，但与人类可读的十进制转换非常耗时，算法实现（尤其是除法）也较为复杂，不适合入门。
2. 大进制块存储：例如，以10^9（1000000000）为基，每个int存储0到999999999之间的数。这是工业级库（如GMP）常用的方法，它在空间效率、计算效率以及与十进制字符串的转换效率之间取得了绝佳的平衡。但实现复杂度较高。
3. 十进制数组存储：用vector<int>或string，每个元素存储一个十进制数字（0-9）。这是最直观、最容易理解和实现的方式，与我们的书写习惯完全一致，方便调试和输入输出。

对于我们的教学和大多数应用场景，十进制数组存储是最佳起点。我们选择vector<int>来存储每一位数字，并且约定：

• 数字的低位存储在数组的低索引位置。例如，数字“12345”在vector<int>中存储为{5, 4, 3, 2, 1}。
• 这种“小端序”存储方式极大地简化了竖式计算的实现，因为运算通常从个位开始。
• 单独用一个bool类型成员变量isNegative来表示正负号，以支持负数。

注意：这里有一个关键细节，我们存储的是int型的数字0-9，而不是char型的字符‘0’-‘9’。这避免了在计算过程中频繁进行字符与数字的转换，提高了效率，也让代码更清晰。

2.2 类的基本骨架与构造函数设计

基于以上设计，我们可以勾勒出BigInteger类的基本框架。

#include <vector> #include <string> #include <iostream> #include <algorithm> // 用于reverse等操作 #include <cctype> // 用于isdigit class BigInteger { private: std::vector<int> digits; // 存储十进制数字，低位在前 bool isNegative; // 符号位，true表示负数 // 辅助函数：去除数字高位无用的前导零，例如将[0,0,1,2]变为[1,2] void trimZeros() { while (digits.size() > 1 && digits.back() == 0) { digits.pop_back(); } // 如果数字本身就是0，确保表示为正的[0]，而不是空的[] if (digits.empty() || (digits.size() == 1 && digits[0] == 0)) { digits = {0}; isNegative = false; } } public: // 默认构造函数，构造为0 BigInteger() : digits({0}), isNegative(false) {} // 从long long构造 BigInteger(long long num) { if (num < 0) { isNegative = true; num = -num; } else { isNegative = false; } if (num == 0) { digits = {0}; return; } while (num > 0) { digits.push_back(num % 10); num /= 10; } } // 从字符串构造（最常用） BigInteger(const std::string& str) { isNegative = false; int startIdx = 0; // 处理可能的符号位 if (!str.empty() && (str[0] == '-' || str[0] == '+')) { isNegative = (str[0] == '-'); startIdx = 1; } // 从字符串末尾（个位）开始向前解析数字 for (int i = str.size() - 1; i >= startIdx; --i) { if (!std::isdigit(str[i])) { throw std::invalid_argument("Invalid character in number string"); } digits.push_back(str[i] - '0'); // 字符转数字 } trimZeros(); // 构造后去除可能的前导零，如“-000” } // 拷贝构造函数、析构函数、赋值运算符等使用编译器默认生成即可 // 因为vector<int>和bool都能正确拷贝/移动 };

构造函数解析：

• 默认构造：初始化为0。这是一个好习惯，避免了未初始化的对象。
• long long构造：通过不断模10、除10来分解数字，直接得到低位在前的数组。注意对负号和0的处理。
• 字符串构造：这是最核心的构造函数。它需要处理正负号，并验证字符串中是否全是数字。从字符串末尾向前遍历的写法，天然实现了“低位在前”的存储约定。trimZeros()的调用确保了像"000123"或"-0"这样的输入能被规范化为123和0。

实操心得：在字符串构造函数中一定要进行有效性检查（isdigit），并抛出异常。我曾经因为读取了包含换行符或空格的字符串，导致 digits 里混入奇怪的值，调试了很久。健壮的输入处理能省去后面无数麻烦。

3. 基础功能实现：比较、输出与绝对值

在实现复杂的算术运算之前，我们需要搭建一些基础设施，它们会让后续的运算逻辑更清晰。

3.1 比较运算符的实现

比较两个BigInteger的大小，是减法、除法等运算的基础。我们首先实现一个忽略符号的绝对值大小比较的辅助函数，然后基于它实现完整的比较运算符。

class BigInteger { // ... 其他成员 ... private: // 比较绝对值的大小。返回：1 表示 this绝对值 > other绝对值，0 表示等于，-1 表示小于 int compareMagnitude(const BigInteger& 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; // 绝对值完全相等 } public: // 完整的比较运算符 bool operator==(const BigInteger& other) const { return isNegative == other.isNegative && digits == other.digits; } bool operator!=(const BigInteger& other) const { return !(*this == other); } bool operator<(const BigInteger& other) const { if (isNegative != other.isNegative) { return isNegative; // 一正一负，负数肯定小 } // 同号情况 int cmp = compareMagnitude(other); if (isNegative) { // 两者都为负，绝对值大的反而小 return cmp == 1; } else { // 两者都为正，绝对值大的大 return cmp == -1; } } bool operator>(const BigInteger& other) const { return other < *this; } bool operator<=(const BigInteger& other) const { return !(*this > other); } bool operator>=(const BigInteger& other) const { return !(*this < other); } };

比较逻辑的核心在于compareMagnitude函数和符号处理。对于operator<：

1. 符号不同：负数永远小于正数。
2. 符号相同（均为负）：绝对值大的数更小（例如 -100 < -10）。
3. 符号相同（均为正）：绝对值大的数更大。

3.2 流输出运算符重载

为了让BigInteger能像内置类型一样用cout << a打印，我们需要重载operator<<。

std::ostream& operator<<(std::ostream& os, const BigInteger& num) { if (num.isNegative) { os << '-'; } // 因为存储是低位在前，输出需要从高位（vector末尾）开始 for (auto it = num.digits.rbegin(); it != num.digits.rend(); ++it) { os << *it; } // 处理数字为0的情况，上面的循环至少会输出一个数字 return os; }

这个实现简单直接。注意使用反向迭代器rbegin()和rend()来从高位向低位输出。

3.3 获取绝对值的辅助函数

在实现加减法时，我们经常需要操作数的绝对值。实现一个返回绝对值副本的函数很方便。

class BigInteger { // ... 其他成员 ... public: BigInteger abs() const { BigInteger result = *this; result.isNegative = false; return result; } };

4. 算术运算核心：加法与减法的实现

加法和减法是所有运算的基石。我们将实现operator+和operator-。为了处理符号问题，我们会将具体的加减运算委托给两个无符号的、针对绝对值的加法/减法函数。

4.1 无符号加法（绝对值相加）

这个函数假设两个操作数都是非负的（通过绝对值传入），只处理数字位的相加和进位。

class BigInteger { // ... 其他成员 ... private: // 核心：两个正数相加，返回结果（结果为正） static BigInteger addMagnitude(const BigInteger& a, const BigInteger& b) { BigInteger result; result.digits.clear(); // 清空默认的0 const auto& da = a.digits; const auto& db = b.digits; size_t len = std::max(da.size(), db.size()); int carry = 0; for (size_t i = 0; i < len || carry > 0; ++i) { int sum = carry; if (i < da.size()) sum += da[i]; if (i < db.size()) sum += db[i]; result.digits.push_back(sum % 10); carry = sum / 10; } // 结果已经是最低位在前，无需trim（因为进位可能产生最高位，但不会是0） return result; } };

这个函数是经典的竖式加法模拟。循环条件i < len || carry > 0是关键，它确保了最高位的进位能被正确处理。

4.2 无符号减法（绝对值相减，要求a >= b）

这个函数假设a的绝对值大于等于b的绝对值，返回a - b的结果（非负）。

class BigInteger { // ... 其他成员 ... private: // 核心：两个正数相减 (a >= b)，返回结果（结果为正或0） static BigInteger subtractMagnitude(const BigInteger& a, const BigInteger& b) { BigInteger result; result.digits.clear(); const auto& da = a.digits; const auto& db = b.digits; int borrow = 0; for (size_t i = 0; i < da.size(); ++i) { int sub = da[i] - borrow; borrow = 0; if (i < db.size()) { sub -= db[i]; } if (sub < 0) { sub += 10; borrow = 1; } result.digits.push_back(sub); } // 去除结果中的前导零，例如 123-120 = 003 -> 3 result.trimZeros(); return result; } };

这里模拟的是借位减法。borrow变量记录从下一位借走的“1”。当本位不够减时，sub += 10并设置borrow=1。

4.3 完整的加法和减法运算符

有了上面的无符号运算，我们就可以根据操作数的符号，来组合出完整的加减法。

class BigInteger { // ... 其他成员 ... public: // 一元负号运算符 BigInteger operator-() const { BigInteger result = *this; if (result != BigInteger(0)) { // 避免 -0 的出现 result.isNegative = !result.isNegative; } return result; } // 加法运算符 BigInteger operator+(const BigInteger& other) const { // 情况1：符号相同，绝对值相加，符号不变 if (isNegative == other.isNegative) { BigInteger result = addMagnitude(*this, other); result.isNegative = isNegative; // 继承相同的符号 return result; } // 情况2：符号不同，转化为绝对值相减 // this正，other负 => this - |other| // this负，other正 => other - |this| int cmp = compareMagnitude(other); if (cmp >= 0) { // |this| >= |other| BigInteger result = subtractMagnitude(*this, other); result.isNegative = isNegative; // 结果的符号与绝对值大的数相同 return result; } else { // |this| < |other| BigInteger result = subtractMagnitude(other, *this); result.isNegative = other.isNegative; // 结果的符号与绝对值大的数相同 return result; } } // 减法运算符：a - b = a + (-b) BigInteger operator-(const BigInteger& other) const { return *this + (-other); } // 复合赋值运算符，通常用于提高效率 BigInteger& operator+=(const BigInteger& other) { *this = *this + other; return *this; } BigInteger& operator-=(const BigInteger& other) { *this = *this - other; return *this; } };

加法运算符的逻辑分解：

1. 同号相加：绝对值相加，符号不变。简单直接。
2. 异号相加：这本质上是一个减法。结果的符号由绝对值大的那个数决定。我们通过compareMagnitude比较绝对值大小，然后调用subtractMagnitude（确保用大的减小的），最后赋予结果正确的符号。

减法运算符巧妙地利用了一元负号和加法来实现，这大大简化了代码。operator-()返回当前对象的相反数。

注意事项：在实现operator-()时，要特别处理0的情况。数学上-0等于0，我们应避免产生一个isNegative=true但值为0的对象。trimZeros()函数已经处理了这种情况，但在一元负号中显式判断更安全。

5. 进阶运算：乘法与除法的实现

乘法和除法的实现比加减法复杂，但核心思想依然是模拟竖式计算。

5.1 乘法实现：模拟竖式乘法

乘法的基本思路是，将乘数b的每一位与被乘数a相乘，得到一个临时的中间结果，然后将所有这些中间结果按位相加（需要左移，即补零）。

class BigInteger { // ... 其他成员 ... public: BigInteger operator*(const BigInteger& other) const { BigInteger result; const auto& da = this->digits; const auto& db = other.digits; // 结果的最大位数是两者位数之和 result.digits.resize(da.size() + db.size(), 0); // 双重循环模拟竖式 for (size_t i = 0; i < da.size(); ++i) { int carry = 0; for (size_t j = 0; j < db.size(); ++j) { // 当前位的乘积，加上之前的进位，再加上该位原有的值（来自低位的进位） int sum = result.digits[i + j] + da[i] * db[j] + carry; result.digits[i + j] = sum % 10; carry = sum / 10; } // 处理最高位的进位 if (carry > 0) { result.digits[i + db.size()] += carry; } } result.trimZeros(); // 去除可能的前导零，例如 123 * 0 // 符号规则：同号为正，异号为负 result.isNegative = (this->isNegative != other.isNegative); // 如果结果是0，确保符号为正 if (result.digits.size() == 1 && result.digits[0] == 0) { result.isNegative = false; } return result; } BigInteger& operator*=(const BigInteger& other) { *this = *this * other; return *this; } };

这个算法的时间复杂度是O(n*m)，其中n和m是两个操作数的位数。它并不是最优的（有Karatsuba等更快的算法），但对于学习和大多数应用足够了。注意我们预先分配了足够大的result.digits空间，避免了在循环中频繁push_back。

5.2 除法与取模实现：模拟竖式除法

除法是最复杂的运算。我们实现一个返回商和余数的函数，然后基于它实现operator/（整除）和operator%（取模）。

class BigInteger { // ... 其他成员 ... private: // 辅助函数：返回 *this 除以 other 的商和余数。假设 other 不为0。 std::pair<BigInteger, BigInteger> divideAndRemainder(const BigInteger& other) const { if (other == BigInteger(0)) { throw std::runtime_error("Division by zero"); } BigInteger dividend = this->abs(); // 被除数取绝对值 BigInteger divisor = other.abs(); // 除数取绝对值 if (dividend < divisor) { // 被除数绝对值小于除数绝对值，商为0，余数为被除数（带原符号） BigInteger remainder = dividend; remainder.isNegative = this->isNegative; // 余数符号同被除数 return {BigInteger(0), remainder}; } BigInteger quotient; BigInteger current; // 当前被除的一段 // 从被除数的高位开始逐位处理 for (int i = dividend.digits.size() - 1; i >= 0; --i) { current.digits.insert(current.digits.begin(), dividend.digits[i]); // 插入到最高位 current.trimZeros(); // 试商：当前段能包含几个除数？ int count = 0; while (current >= divisor) { current = subtractMagnitude(current, divisor); count++; } // 将试商的结果作为商的一位（插入到商的低位，因为我们在从高向低处理） quotient.digits.insert(quotient.digits.begin(), count); } quotient.trimZeros(); // 处理符号：商 = (被除数符号) XOR (除数符号) quotient.isNegative = (this->isNegative != other.isNegative); if (quotient.digits.size() == 1 && quotient.digits[0] == 0) { quotient.isNegative = false; } // 余数符号同被除数 current.isNegative = this->isNegative; current.trimZeros(); return {quotient, current}; } public: // 除法运算符（整除） BigInteger operator/(const BigInteger& other) const { return divideAndRemainder(other).first; } // 取模运算符 BigInteger operator%(const BigInteger& other) const { return divideAndRemainder(other).second; } BigInteger& operator/=(const BigInteger& other) { *this = *this / other; return *this; } BigInteger& operator%=(const BigInteger& other) { *this = *this % other; return *this; } };

除法算法解析： 这是经典的长除法模拟，和我们手算的过程一模一样：

1. 从被除数最高位开始，取一位（或一段）作为current。
2. 看current能减去多少次divisor，这个次数就是商在这一位上的数字。
3. 将current减去divisor * count后剩下的作为新的current。
4. 被除数的下一位落下来，接在current后面，重复步骤2-3。

关键细节：

• current.digits.insert(current.digits.begin(), ...)模拟了“落位”操作。
• 试商过程while (current >= divisor)对于十进制个位数来说很快，但如果除数很大，这里可以优化为二分查找（0-9范围内查找）。
• 商的符号规则是“同号得正，异号得负”。余数的符号在数学上有不同定义，C++11标准规定a % b的符号与a相同。我们遵循了这个约定。
• 一定要在返回前调用trimZeros()，确保结果的规范性。

踩坑记录：除法中最容易出错的就是current的维护和商的插入位置。我最初错误地将商位push_back到末尾，导致商是反的。记住，我们是从被除数高位向低位处理，但digits数组是低位在前。所以每次得到的商位要插入到quotient.digits的开头（insert(begin(), ...)），这样才能保证商的高位在数组末尾。

6. 性能优化与进阶思考

我们目前实现的是一个教学级的、功能完整的BigInteger。它正确但效率不高。如果你打算在项目中使用，或者想进一步挑战自己，可以考虑以下优化方向：

6.1 存储优化：从十进制到万进制

十进制存储直观但效率低。一个int能存约20亿，而我们只用了0-9，浪费了99.9999995%的空间。改用万进制或亿进制可以极大提升性能。

• 万进制：以10000为基，每个int存储0-9999。这样，一个int就相当于4个十进制位。运算次数减少为原来的1/4。
• 实现改动：输入输出时需要做进制转换（十进制字符串<->万进制数组），加减乘除的进位/借位规则从“逢十进一”变为“逢万进一”。核心算法逻辑不变，但效率提升显著。

6.2 算法优化：更快的乘法和除法

• Karatsuba乘法：将两个大数x和y拆分成x = a*B^m + b,y = c*B^m + d，然后通过三次递归乘法ac,bd,(a+b)(c+d)来计算xy，时间复杂度从O(n²)降到约O(n^1.585)。当数字位数很大时（比如超过几百位），优势明显。
• 牛顿迭代法求除法：通过乘法来逼近除法结果，对于特别大的数，比长除法快得多。这通常需要实现一个高精度的倒数近似算法。

6.3 内存与拷贝优化

• 移动语义：为BigInteger实现移动构造函数和移动赋值运算符。在返回临时对象或进行a = b + c这类操作时，可以避免不必要的深拷贝。
• SSO（Small String Optimization）思想：对于非常小的数字（比如小于10^9），可以直接用一个long long成员变量存储，避免动态分配vector的开销。当数字变大时再切换到vector存储。

6.4 扩展功能

• 位运算：实现&,|,^,<<,>>。这需要将大数转换为二进制表示来操作，或者基于现有的十进制/万进制实现模拟。
• 幂运算：实现快速幂算法pow(BigInteger exp)。
• 开平方：实现牛顿迭代法求平方根。
• 输入运算符>>：完善流输入，处理带符号和空格的长字符串。
• 与内置类型的互操作：提供更多构造函数和类型转换（谨慎使用，可能丢失精度）。

7. 测试与常见问题排查

实现完成后，必须进行全面的测试。以下是一些测试用例和常见问题。

7.1 基础功能测试

void testBasic() { BigInteger a("12345678901234567890"); BigInteger b("98765432109876543210"); BigInteger c(-12345); BigInteger d("0"); // 测试输出 std::cout << "a = " << a << std::endl; // 12345678901234567890 std::cout << "b = " << b << std::endl; // 98765432109876543210 std::cout << "c = " << c << std::endl; // -12345 // 测试比较 std::cout << (a < b) << std::endl; // 1 (true) std::cout << (a == a) << std::endl; // 1 std::cout << (d == BigInteger(0)) << std::endl; // 1 // 测试加法 std::cout << "a + b = " << (a + b) << std::endl; // 111111111011111111100 std::cout << "a + c = " << (a + c) << std::endl; // 12345678901234555545 std::cout << "c + c = " << (c + c) << std::endl; // -24690 // 测试减法 std::cout << "a - b = " << (a - b) << std::endl; // -86419753208641975320 std::cout << "b - a = " << (b - a) << std::endl; // 86419753208641975320 std::cout << "c - a = " << (c - a) << std::endl; // -12345678901234580235 // 测试乘法 std::cout << "a * d = " << (a * d) << std::endl; // 0 std::cout << "a * c = " << (a * c) << std::endl; // -1524157875323883455018780510 BigInteger small("12"); std::cout << "small * small = " << (small * small) << std::endl; // 144 // 测试除法 BigInteger e("100000000000000000000"); BigInteger f("33333333333333333333"); std::cout << "e / f = " << (e / f) << std::endl; // 3 std::cout << "e % f = " << (e % f) << std::endl; // 1 (实际上是 100000000000000000000 % 33333333333333333333) std::cout << "c / 5 = " << (c / BigInteger(5)) << std::endl; // -2469 std::cout << "c % 5 = " << (c % BigInteger(5)) << std::endl; // 0 (因为 -12345 / 5 = -2469 余 0) }

7.2 常见问题与排查表

在实现和测试过程中，你可能会遇到以下问题：

7.3 一个实用的调试技巧

在开发过程中，为BigInteger类添加一个debugPrint()私有方法非常有用，它可以打印出内部的digits数组和符号。

class BigInteger { // ... private: void debugPrint(const std::string& name) const { std::cerr << name << ": isNeg=" << isNegative << ", digits=["; for (int d : digits) std::cerr << d << " "; std::cerr << "] ("; for (auto it = digits.rbegin(); it != digits.rend(); ++it) std::cerr << *it; std::cerr << ")" << std::endl; } };

在运算的关键步骤调用它，可以清晰地看到数据是如何流动和变化的。

自己实现一个BigInteger类就像完成一次小型的数据结构与算法综合练习。它强迫你思考整数的本质、计算机的运算方式以及如何用代码优雅地模拟这一过程。从最直观的十进制数组开始，确保每一行代码你都能理解其背后的数学原理，这是理解更复杂优化方案的基础。当你看到它能正确计算100!（100的阶乘）这样一个158位的巨大数字时，那种成就感是无可替代的。这个项目可以作为你C++学习路上一个坚实的里程碑，其背后涉及的思维训练，远比调用一个现成的库有价值得多。