1. 项目概述：为什么我们需要自己造一个“大整数”？

在C++的标准库里，int、long long这些内置整数类型大家用得都很顺手，直到你某天刷题或者处理实际业务时，遇到了一个需要计算1000位甚至10000位数字的场景。比如，高精度计算圆周率、RSA加密解密中的大数运算、或者处理金融领域天文数字级别的金额。这时候，标准类型那可怜的几十位存储上限（通常是2^31-1或2^63-1）瞬间就捉襟见肘了。

这就是BigInt（大整数）登场的时刻。它不是一个神秘的黑魔法，其核心思想非常直观：既然一个变量存不下，我们就用多个变量来存。最经典也最易于理解的方式，就是用一个数组来模拟一个超长的数字，数组的每一个元素（比如一个int）只存储这个超大数字的一位或几位（十进制下的一位，或万进制下的一位）。然后，我们手动实现这个“数组数字”的加、减、乘、除等基本运算规则，也就是把我们小学学过的竖式计算法，用代码翻译出来。

所以，这个系列文章的目标，就是带你从零开始，亲手实现一个功能完整、性能尚可的BigInt类。这不仅是一个绝佳的C++综合练习项目，能深刻锻炼你对类设计、运算符重载、内存管理和基础算法的理解，更是理解“高精度计算”这一计算机基础领域的敲门砖。无论你是想挑战更复杂的算法题，还是对底层实现抱有好奇心，这个项目都值得你投入时间。

在第一部分，我们将聚焦于最核心的基石：数据的内部表示与存储，以及最基础的输入输出和比较运算。万丈高楼平地起，这部分的设计将直接决定后续所有运算实现的复杂度和效率。

2. 核心设计：如何表示一个“无限大”的整数？

设计一个BigInt，首先要回答几个关键问题：数字是正还是负？用什么容器存储每一位？每一位代表十进制的一位，还是更高的进制（如10000进制）？数据在容器中如何排列（高位在前还是低位在前）？

2.1 符号、容器与进制选择

符号处理：我们单独用一个布尔值bool isNegative_来标记整数的正负。这样在实现加减法时，逻辑会更清晰。当然，你也可以采用补码的思想，但对于教学和清晰度而言，单独存储符号是更好的起点。

容器选择：std::vector<int>是我们的不二之选。它动态管理内存，我们无需手动处理数组的扩容问题，可以专注于算法逻辑。std::string也是一个选择，但进行数值运算时需要频繁进行字符与数字的转换，不如vector<int>直接。

进制选择（核心优化点）：这是影响性能和代码复杂度的关键决策。

• 十进制（每位存0-9）：最直观，输入输出极其简单，但效率最低。做乘法时，两个n位数相乘需要O(n²)次单位乘法，并且进位处理频繁。
• 高进制（如万进制，每位存0-9999）：这是实践中更常用的方案。我们用int类型的每一个元素来存储0到9999之间的一个数。这样做的好处是：
  1. 大幅减少运算次数：数字的“长度”（容器大小）缩短为原来的约1/4，乘法复杂度从O(n²)降至O((n/4)²)，理论上有16倍的提升。
  2. 充分利用硬件：int类型的加减乘除是CPU直接支持的单指令操作，速度极快。
  3. 减少进位频率：由于每位容量大，单次运算后产生进位的概率降低。

当然，高进制带来了输入输出转换的额外开销，但综合来看，在需要频繁运算的场景下，其收益远大于代价。本系列将采用万进制（10000进制）作为基础。

存储顺序：为了便于运算（特别是从个位开始处理），我们采用低位在前（Little-Endian）的存储方式。即digits_[0]存储的是数字的个位（在万进制下，是最低4位十进制数字），digits_[1]存储的是次低位，以此类推。这样，当我们遍历数组进行运算时，自然就是从低位到高位处理，与竖式计算的习惯一致。

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

基于以上设计，我们可以勾勒出BigInt类的初步轮廓。

#include <vector> #include <string> #include <iostream> #include <algorithm> // 用于reverse等操作 #include <cctype> // 用于isdigit class BigInt { private: std::vector<int> digits_; // 存储万进制下的每一位，低位在前 bool isNegative_; // 符号位，true表示负数 // 辅助函数：去除前导零，保证数字0表示为{0}而非空数组或{0,0,0} void trim() { while (digits_.size() > 1 && digits_.back() == 0) { digits_.pop_back(); } // 处理结果为0的情况，保证其符号为正，表示为{0} if (digits_.size() == 1 && digits_[0] == 0) { isNegative_ = false; } } public: // 默认构造函数，构造值为0的BigInt BigInt() : digits_(1, 0), isNegative_(false) {} // 从long long构造 BigInt(long long num) { isNegative_ = (num < 0); num = std::abs(num); if (num == 0) { digits_.push_back(0); } else { while (num > 0) { digits_.push_back(num % 10000); // 获取低4位十进制（万进制下的一位） num /= 10000; } } } // 从字符串构造（核心且复杂） BigInt(const std::string& str) { // 实现细节见下文 } // 拷贝构造函数、赋值运算符等（遵循Rule of Three/Five，此处省略，建议实现） BigInt(const BigInt& other) = default; BigInt& operator=(const BigInt& other) = default; // 移动构造函数和移动赋值运算符在后续优化时可以考虑添加 };

注意：trim()函数至关重要。在运算过程中，可能会在最高位产生多余的0（例如，9999 + 1，在万进制下计算会得到[0, 1]，我们需要去掉高位的0，变成[1]）。同时，它确保了数字“0”的唯一规范表示，避免后续比较和输出出现歧义。

3. 从字符串构造：处理正负号与进制转换

从字符串构造是BigInt与外界交互的主要入口之一，也是第一个需要细心处理的复杂函数。我们需要处理可能存在的正负号‘+’、‘-’，并忽略前导空格，然后将十进制字符串转换为内部的万进制表示。

BigInt(const std::string& str) { // 1. 处理空字符串 if (str.empty()) { digits_.push_back(0); isNegative_ = false; return; } size_t start = 0; // 2. 处理符号位 if (str[0] == '-') { isNegative_ = true; start = 1; } else if (str[0] == '+') { isNegative_ = false; start = 1; } else { isNegative_ = false; } // 3. 跳过前导零（可选，但能提升效率） while (start < str.size() && str[start] == '0') { start++; } // 如果字符串全是零，则构造为0 if (start == str.size()) { digits_.push_back(0); isNegative_ = false; return; } // 4. 核心转换：十进制字符串 -> 万进制vector // 思路：从字符串最高位（十进制）开始，模拟除以10000的过程。 // 但我们从低位开始存，所以先读取字符串，最后再反转？不，有更高效的方法。 // 我们采用“累加乘基”法，从字符串的高位向低位遍历。 digits_.clear(); // 清空可能的内容 // 先放入一个0，作为初始值 digits_.push_back(0); const int BASE = 10000; for (size_t i = start; i < str.size(); ++i) { char c = str[i]; if (!std::isdigit(static_cast<unsigned char>(c))) { throw std::invalid_argument("Invalid character in BigInt string constructor"); } int digit = c - '0'; // 将当前结果乘以10，然后加上新的数字 // 注意：digits_是万进制，乘以10需要分解为乘以10的循环 // 更通用的方法是：将整个数字乘以10，然后加上digit。 // 我们可以实现一个`multiplyBy(int)`和`add(int)`辅助函数，但这里为了清晰，直接展开。 // 实际上，对于构造器，更简单粗暴的方法是：先全部按十进制存到临时vector，再转换成万进制。 // 这里展示一种“在线”转换的方法，效率较高。 // 当前结果乘以10 int carry = 0; for (size_t j = 0; j < digits_.size(); ++j) { int product = digits_[j] * 10 + carry; digits_[j] = product % BASE; carry = product / BASE; } if (carry > 0) { digits_.push_back(carry); } // 加上新的个位数digit carry = digit; for (size_t j = 0; carry > 0 && j < digits_.size(); ++j) { int sum = digits_[j] + carry; digits_[j] = sum % BASE; carry = sum / BASE; } if (carry > 0) { digits_.push_back(carry); } } // 5. 去除可能存在的最高位前导零（由于乘法进位可能产生） trim(); }

这段代码是构造函数的灵魂。它逐位读取十进制字符串，将整个数字视为一个整体，每次将其乘以10，然后加上新的数字。这个过程模拟了我们在纸上从高位到低位组合数字的过程，但巧妙地利用循环处理了万进制下的进位。

实操心得：字符串构造函数的鲁棒性非常重要。务必检查非法字符（非数字），并妥善处理全是0、空字符串、仅符号（如“-”）等边界情况。这里的“在线转换”算法避免了使用中间的大数组，内存效率更高，但理解起来需要一点耐心。另一种更直观的方法是先用vector<int>按顺序存储每一位十进制数，然后再用一个循环将其合并成万进制，代码更简单，但需要额外的空间。

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

在实现加减乘除之前，我们需要先让BigInt能够被查看和比较。这涉及到输出运算符重载和比较运算符重载。

4.1 输出运算符<<

输出需要将内部的万进制表示转换回十进制字符串。由于存储是低位在前，我们需要从最高位开始输出。最高位可能不足4位，输出时不能补前导零，而中间的每一位都需要固定输出4位（前导零补足），以保证数值正确。

// 声明为友元函数，以便访问私有成员 friend std::ostream& operator<<(std::ostream& os, const BigInt& num); // 在类外实现 std::ostream& operator<<(std::ostream& os, const BigInt& num) { if (num.isNegative_) { os << '-'; } // 先输出最高位（没有前导零） os << num.digits_.back(); // 从次高位开始，每个位都需要输出4位数字，不足补0 for (int i = static_cast<int>(num.digits_.size()) - 2; i >= 0; --i) { // 使用setw和setfill来格式化输出，需要包含<iomanip> // 为了减少依赖，这里用printf风格或手动补零 os.width(4); // 设置输出宽度为4 os.fill('0'); // 不足部分用'0'填充 os << num.digits_[i]; // 注意：os.width()的效果是一次性的，所以需要在循环内设置 // 更简洁的方式是使用snprintf或stringstream } // 使用stringstream的另一种实现（更清晰）： /* std::ostringstream oss; if (num.isNegative_) oss << '-'; oss << num.digits_.back(); for (int i = (int)num.digits_.size() - 2; i >= 0; --i) { oss << std::setw(4) << std::setfill('0') << num.digits_[i]; } return os << oss.str(); */ return os; }

注意事项：输出格式是新手最容易出错的地方。务必记住，除了最高位，其他每一位在转换成十进制时都必须占满4位。例如，万进制数字[123, 45]（低位123，高位45）对应的十进制是45 * 10000 + 123 = 450123。输出时，如果直接输出“45123”就错了，因为高位“45”实际代表“0045”。所以必须格式化输出。

4.2 比较运算符

比较运算（<,<=,>,>=,==,!=）是其他运算（特别是减法）的基础。比较的逻辑需要同时考虑符号和绝对值大小。

我们先实现一个比较绝对值的辅助函数：

private: // 比较两个BigInt的绝对值大小。返回：-1表示 |this| < |rhs|, 0表示相等，1表示大于。 int compareAbs(const BigInt& rhs) const { // 先比较位数 if (digits_.size() != rhs.digits_.size()) { return digits_.size() < rhs.digits_.size() ? -1 : 1; } // 位数相同，从最高位开始逐位比较 for (int i = static_cast<int>(digits_.size()) - 1; i >= 0; --i) { if (digits_[i] != rhs.digits_[i]) { return digits_[i] < rhs.digits_[i] ? -1 : 1; } } return 0; // 绝对值完全相等 }

然后，利用这个辅助函数实现完整的比较运算符：

public: bool operator==(const BigInt& rhs) const { // 符号相同且绝对值相等 return isNegative_ == rhs.isNegative_ && compareAbs(rhs) == 0; } bool operator!=(const BigInt& rhs) const { return !(*this == rhs); } bool operator<(const BigInt& rhs) const { // 情况1：符号不同 if (isNegative_ && !rhs.isNegative_) return true; // 负 < 正 if (!isNegative_ && rhs.isNegative_) return false; // 正 > 负 // 情况2：符号相同（同为负或同为正） if (isNegative_) { // 同为负数，绝对值大的反而小 return compareAbs(rhs) > 0; } else { // 同为正数，绝对值大的就大 return compareAbs(rhs) < 0; } } bool operator>(const BigInt& rhs) const { return rhs < *this; } bool operator<=(const BigInt& rhs) const { return !(rhs < *this); } bool operator>=(const BigInt& rhs) const { return !(*this < rhs); }

踩坑记录：实现比较运算符时，最容易混淆的是负数比较。一定要牢记：两个负数比较，绝对值大的那个数实际更小。例如，-100 < -10。上面的代码通过符号判断和compareAbs函数的组合，清晰地区分了所有情况。先处理符号不同的简单情况，再处理符号相同的复杂情况，逻辑层次分明。

5. 核心运算奠基：无符号加法与减法

有了比较和基础框架，我们可以开始实现最核心的算术运算了。我们首先实现不考虑符号的绝对值加法和减法（即addAbs和subAbs），它们将作为带符号的operator+和operator-的内部基石。

5.1 无符号加法 (addAbs)

假设两个操作数都是非负的，并且*this的绝对值大于等于rhs的绝对值（这可以通过提前比较来保证，简化进位逻辑）。我们实现一个私有成员函数。

private: // 假设 *this 和 rhs 都为正，且 *this >= rhs。将rhs的绝对值加到 *this 的绝对值上。 void addAbs(const BigInt& rhs) { int carry = 0; size_t i = 0; // 遍历两个数字的每一位，直到处理完较长的那个数和所有进位 for (; i < digits_.size() || i < rhs.digits_.size() || carry; ++i) { // 如果当前位超出*this的长度，需要扩容 if (i == digits_.size()) { digits_.push_back(0); } // 获取当前位的和：*this的位 + rhs的位（如果存在）+ 进位 int sum = digits_[i] + carry; if (i < rhs.digits_.size()) { sum += rhs.digits_[i]; } // 计算新的当前位和新的进位 digits_[i] = sum % BASE; carry = sum / BASE; } // 加法完成后，最高位可能没有进位，digits_大小刚好，trim一下确保规范。 // 注意：因为我们是原地修改*this，且可能扩容了，所以需要trim。 }

这个函数的逻辑就是模拟竖式加法：从最低位开始，对应位相加，加上低位的进位，然后计算当前位的结果和新的进位。

5.2 无符号减法 (subAbs)

同样假设两个操作数非负，且*this的绝对值大于等于rhs的绝对值。从*this中减去rhs的绝对值。

private: // 假设 *this 和 rhs 都为正，且 *this >= rhs。从 *this 的绝对值中减去 rhs 的绝对值。 void subAbs(const BigInt& rhs) { int borrow = 0; // 因为保证了 *this >= rhs，所以只需遍历*this的位数即可 for (size_t i = 0; i < digits_.size(); ++i) { // 计算当前位的差：*this的位 - 借位 int diff = digits_[i] - borrow; // 减去rhs对应的位（如果存在） if (i < rhs.digits_.size()) { diff -= rhs.digits_[i]; } // 处理借位 if (diff < 0) { diff += BASE; borrow = 1; } else { borrow = 0; } digits_[i] = diff; } // 减法完成后，最高位可能产生前导零，必须trim。 // 因为保证了*this>=rhs，所以最终borrow必定为0。 trim(); }

减法就是加法的逆过程，处理借位是关键。diff < 0时，说明不够减，需要向高位借1（即borrow=1），并在当前位加上基数BASE（10000）。

核心技巧：为什么要在加法和减法前保证*this >= rhs？对于加法，顺序不影响结果，但我们的addAbs实现允许*this和rhs任意长度。对于减法，这个保证至关重要。它确保了diff在减去rhs的位后，即使为负，也可以通过借位和+BASE调整回来，并且最终borrow会为0。如果我们不保证大小关系，实现会复杂很多，需要处理结果为负的情况，而这可以通过交换操作数和设置符号位来规避。因此，在实现完整的operator-时，我们会先比较绝对值，然后决定调用subAbs的顺序以及结果的符号。

6. 带符号的加法与减法运算符

现在，我们可以利用上面的无符号运算，来实现完整的、带符号的operator+和operator-。

加法的逻辑可以根据两个操作数的符号分为四种情况：

1. 正 + 正：绝对值相加，结果为正。
2. 负 + 负：绝对值相加，结果为负。
3. 正 + 负：转化为绝对值相减，结果的符号由绝对值大的数决定。
4. 负 + 正：同3，转化为绝对值相减。

public: BigInt operator+(const BigInt& rhs) const { BigInt result = *this; // 拷贝当前对象 result += rhs; // 调用复合赋值运算符+=，逻辑更清晰 return result; } BigInt& operator+=(const BigInt& rhs) { // 情况1和2：同号，绝对值相加，符号不变 if (isNegative_ == rhs.isNegative_) { addAbs(rhs); // 注意：这里直接修改了*this // 符号沿用当前的isNegative_ } else { // 情况3和4：异号，转化为绝对值相减 int cmp = compareAbs(rhs); if (cmp == 0) { // 绝对值相等，结果为0 digits_.assign(1, 0); isNegative_ = false; } else if (cmp > 0) { // |this| > |rhs|， 做减法 this - rhs，符号与this相同 subAbs(rhs); // isNegative_ 保持不变（是this的符号） } else { // |this| < |rhs|， 需要计算 rhs - this，结果符号与rhs相同 BigInt temp = rhs; // 拷贝rhs temp.subAbs(*this); // 计算 |rhs| - |this| // 将结果赋值给*this digits_ = std::move(temp.digits_); isNegative_ = temp.isNegative_; // 符号取rhs的符号 } } // 运算后务必trim，确保表示规范 trim(); return *this; }

减法的实现可以巧妙地利用加法：a - b = a + (-b)。因此，我们可以先取减数的相反数，然后做加法。

public: BigInt operator-(const BigInt& rhs) const { BigInt result = *this; result -= rhs; return result; } BigInt& operator-=(const BigInt& rhs) { // a -= b 等价于 a += (-b) // 创建一个rhs的副本，翻转其符号 BigInt negRhs = rhs; negRhs.isNegative_ = !negRhs.isNegative_; // 注意：0的符号翻转后还是正，但trim会处理 // 然后调用 += 运算符 return *this += negRhs; } // 一元负号运算符 BigInt operator-() const { BigInt result = *this; if (result != BigInt(0)) { // 避免将-0表示为负 result.isNegative_ = !result.isNegative_; } return result; }

实现心得：将减法转化为加法来实现，是降低代码复杂度的经典技巧。它保证了减法逻辑的正确性，并复用了已经测试通过的加法代码。注意在operator-()中，要特殊处理0的情况，确保-0的输出仍然是0（符号为正），这符合数学惯例，也由我们的trim()函数保证。

7. 测试与验证：搭建简易测试框架

代码写完了，不测试就是闭着眼睛开车。我们需要一个简单有效的方法来验证BigInt的基本功能。可以编写一些简单的测试用例，或者直接利用main函数进行交互式测试。

// 一个简单的测试函数 void testBigInt() { std::cout << "=== 测试开始 ===" << std::endl; // 测试构造与输出 BigInt a("12345678901234567890"); BigInt b("-98765432109876543210"); BigInt c(12345); BigInt d = -c; std::cout << "a = " << a << std::endl; // 12345678901234567890 std::cout << "b = " << b << std::endl; // -98765432109876543210 std::cout << "c = " << c << std::endl; // 12345 std::cout << "d = " << d << std::endl; // -12345 std::cout << "BigInt(0) = " << BigInt(0) << std::endl; // 0 // 测试比较 std::cout << "\n=== 比较测试 ===" << std::endl; std::cout << "a == a? " << (a == a) << std::endl; // 1 (true) std::cout << "a != b? " << (a != b) << std::endl; // 1 std::cout << "a > b? " << (a > b) << std::endl; // 1 std::cout << "c < a? " << (c < a) << std::endl; // 1 std::cout << "d < c? " << (d < c) << std::endl; // 1 (-12345 < 12345) std::cout << "BigInt(0) == -BigInt(0)? " << (BigInt(0) == -BigInt(0)) << std::endl; // 1 // 测试加法 std::cout << "\n=== 加法测试 ===" << std::endl; BigInt sum1 = a + b; std::cout << a << " + " << b << " = " << sum1 << std::endl; // -86419753208641975320 BigInt sum2 = c + d; std::cout << c << " + " << d << " = " << sum2 << std::endl; // 0 BigInt sum3 = BigInt("9999999999") + BigInt("1"); std::cout << "9999999999 + 1 = " << sum3 << std::endl; // 10000000000 // 测试减法 std::cout << "\n=== 减法测试 ===" << std::endl; BigInt diff1 = a - b; std::cout << a << " - " << b << " = " << diff1 << std::endl; // 111111111111111111100 BigInt diff2 = c - d; std::cout << c << " - " << d << " = " << diff2 << std::endl; // 24690 BigInt diff3 = BigInt("10000000000") - BigInt("1"); std::cout << "10000000000 - 1 = " << diff3 << std::endl; // 9999999999 // 测试复合赋值 std::cout << "\n=== 复合赋值测试 ===" << std::endl; BigInt x("100"); x += BigInt("50"); std::cout << "x += 50 -> " << x << std::endl; // 150 x -= BigInt("75"); std::cout << "x -= 75 -> " << x << std::endl; // 75 std::cout << "\n=== 测试结束 ===" << std::endl; } int main() { try { testBigInt(); } catch (const std::exception& e) { std::cerr << "异常发生: " << e.what() << std::endl; } return 0; }

运行这些测试，观察输出是否与预期一致。这是验证我们代码逻辑正确性的第一步。如果测试通过，恭喜你，一个具备基础能力的BigInt类已经初具雏形。

8. 常见问题与性能思考

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

1. 为什么选择10000作为进制基数，而不是更大的数比如100000000？这是一个权衡。基数越大，存储效率越高，运算次数越少。但基数太大（接近或超过int的最大值INT_MAX，约21亿）时，在做乘法a * b + carry时可能会溢出。10000的平方是1亿，加上可能的进位（小于10000），结果小于1亿+1万，远小于21亿，在int的安全范围内。选择2的幂次（如65536）在计算机中处理更高效（位运算），但输入输出时需要做二进制到十进制的转换，更复杂。10000是一个在安全、效率和实现简便性上较好的折中。

2.trim()函数为什么如此重要？它保证了数据的“规范形式”。没有它，数字0可能被表示为{0, 0}，123可能被表示为{123, 0}。这会导致比较运算出错（例如{123, 0}和{123}在逐位比较时不相等），输出错误（输出多余的前导零），以及后续运算的复杂度增加。在任何可能改变digits_数组内容的操作（尤其是减法、乘法、除法）之后，都必须调用trim()。

3. 如何调试BigInt的内部状态？可以添加一个调试输出函数，例如：

void debugPrint() const { std::cout << (isNegative_ ? "-" : "+") << " ["; for (int i = digits_.size() - 1; i >= 0; --i) { std::cout << digits_[i]; if (i > 0) std::cout << ", "; } std::cout << "] (Base 10000, LSB first)" << std::endl; }

当输出结果不符合预期时，打印出内部存储的万进制数组，可以非常直观地定位问题。

4. 当前实现的性能瓶颈在哪里？目前我们只实现了加法和减法，其时间复杂度是O(n)，n是万进制下的位数，对于大数来说已经很快。接下来的乘法如果使用最朴素的O(n²)算法（模拟竖式），将会是主要的性能瓶颈。在后续部分，我们将探讨更高效的乘法算法，如Karatsuba算法（分治法，复杂度约为O(n^1.585)），这对于处理非常大的数字至关重要。

5. 关于内存和拷贝优化当前的实现大量使用了传值返回（如operator+），这会导致拷贝构造。对于巨大的BigInt，拷贝std::vector的成本不容忽视。在后续优化中，可以考虑实现移动构造函数(BigInt(BigInt&&))和移动赋值运算符，并在可能的情况下使用std::move来转移资源所有权，减少不必要的深拷贝。例如，在operator+的实现中，可以尝试通过参数值传递和移动语义来优化。

至此，我们已经完成了BigInt第一部分的全部内容：从设计思路、数据存储、构造、输出、比较到最基础的加减法。这个版本已经能够处理任意大小的整数加减运算。在下一部分，我们将挑战更复杂的乘法和除法，并着手进行性能优化。