1. 项目概述为什么我们需要自己造轮子在C的标准库里int、long long这些内置整数类型大家用得都很顺手直到你遇到一个需要计算100的阶乘或者处理两个100位质数相乘的场景。这时编译器会毫不留情地告诉你溢出了。这就是“大整数”Big Integer问题最直接的体现——当数值范围远超CPU原生数据类型通常是64位最大值约9.22e18时我们必须自己设计一种数据结构来存储和运算。自己动手实现一个大整数类远不止是为了完成一次作业或应付面试。它是一个绝佳的练手项目能让你深入理解计算机如何表示和运算远超其字长的数字这是从“使用语言”到“理解语言背后逻辑”的关键一步。数据结构与算法的紧密结合如何高效地存储比如用字符串还是数组、如何设计加减乘除的算法小学竖式运算的计算机版本。面向对象设计的精髓如何封装内部复杂的表示对外提供清晰、易用且安全的接口比如重载运算符让大数用起来和普通int一样自然。性能与资源的权衡加法可以很简单但乘法呢除法呢如何优化避免成为性能瓶颈网上确实有很多现成的库如GMP但“知其然更要知其所以然”。亲手实现一遍你对内存管理、算法复杂度、接口设计的理解会深刻得多。接下来我们就从零开始设计并实现一个功能完整、接口友好、性能尚可的C大整数类。2. 核心设计思路与数据结构选型设计一个大整数类第一步也是最重要的一步就是决定如何在内存中表示这个“大”数。这直接决定了后续所有算法的效率和实现的复杂度。2.1 内部表示方案对比常见的内部表示方案主要有两种十进制字符串表示做法直接用std::string存储数字的字符串形式例如“12345678901234567890”。优点输入输出极其方便人类可读性强实现简单的加减法模拟竖式也比较直观。致命缺点运算效率极低。每一次运算都需要进行字符与数字的转换进位借位操作繁琐乘除法的复杂度会非常高O(n²)量级。内存利用率也不高一个字节只存储一个十进制位0-9。高精度进制如10^9进制数组表示做法使用std::vectorint或std::vectorlong long每个元素存储大整数的一部分。例如在10^9进制下数字“12345678901234567890”可以表示为[34567890, 12345678]因为12345678901234567890 12345678 * 10^9 34567890。优点这是业界标准做法如GMP库的核心思想。效率极高因为利用机器字长每个“位”可以存储一个很大的数如0到10^9-1一次运算能处理多位十进制数。运算直接加减乘除都可以在数组元素间直接进行利用CPU的ALU进行高速计算只需处理好进位和借位。内存紧凑存储密度高。缺点输入输出需要做进制转换实现稍复杂。设计决策为了追求性能和通用性我们毫不犹豫地选择高精度进制数组表示法。我们将采用10^9作为基底Base因为10^9 1,000,000,000小于2^31约21亿可以安全地用一个32位有符号int存储且两个这样的数相乘不会溢出64位long long的范围方便我们实现乘法。与十进制转换方便因为基底是10的幂。std::vectorint作为容器动态管理内存。2.2 类的整体框架设计确定了内部表示我们就可以勾勒出类的骨架。一个健壮的大整数类需要处理正负号、提供丰富的构造函数、重载常用运算符。// BigInt.h #ifndef BIGINT_H #define BIGINT_H #include vector #include string class BigInt { private: // 核心数据成员 std::vectorint digits; // 存储数字digits[0]是最低位个位 bool isNegative; // 符号位true表示负数 // 静态常量定义我们的进制系统 static const int BASE 1000000000; // 10^9 static const int BASE_DIGITS 9; // 每个元素对应的十进制位数 // 内部工具函数声明 void trim(); // 去除高位的无效0 void fromString(const std::string s); // 从字符串构造 public: // 构造函数 BigInt(); // 默认构造为0 BigInt(long long num); // 从long long构造 BigInt(const std::string s); // 从字符串构造 BigInt(const BigInt other); // 拷贝构造 // 赋值运算符 BigInt operator(const BigInt other); // 算术运算符重载成员函数形式 BigInt operator(const BigInt rhs) const; BigInt operator-(const BigInt rhs) const; BigInt operator*(const BigInt rhs) const; BigInt operator/(const BigInt rhs) const; BigInt operator%(const BigInt rhs) const; // 复合赋值运算符 BigInt operator(const BigInt rhs); BigInt operator-(const BigInt rhs); BigInt operator*(const BigInt rhs); BigInt operator/(const BigInt rhs); BigInt operator%(const BigInt rhs); // 比较运算符重载友元函数更常见 friend bool operator(const BigInt lhs, const BigInt rhs); friend bool operator!(const BigInt lhs, const BigInt rhs); friend bool operator(const BigInt lhs, const BigInt rhs); friend bool operator(const BigInt lhs, const BigInt rhs); friend bool operator(const BigInt lhs, const BigInt rhs); friend bool operator(const BigInt lhs, const BigInt rhs); // 一元运算符 BigInt operator-() const; // 取负 BigInt operator() const { return *this; } // 取正直接返回自身 // 输入输出 friend std::ostream operator(std::ostream os, const BigInt num); friend std::istream operator(std::istream is, BigInt num); // 转换为字符串 std::string toString() const; }; #endif // BIGINT_H这个框架定义了一个清晰的数据边界digits向量和isNegative标志是绝对私有的所有外部交互都通过公有接口进行。这符合面向对象封装的原则。3. 核心功能实现细节与算法剖析有了框架我们来逐一实现最核心的部分构造、加减、比较、乘除。这些算法的效率直接决定了整个类的性能。3.1 构造函数与字符串解析从long long构造相对简单不断除以BASE取余即可。难点在于从字符串构造因为字符串可能很长还可能包含正负号。// BigInt.cpp (部分) void BigInt::fromString(const std::string s) { digits.clear(); // 清空现有数据 isNegative false; int startPos 0; // 处理符号 if (!s.empty() (s[0] - || s[0] )) { isNegative (s[0] -); startPos 1; } // 核心分段读取字符串转换为BASE进制 // 我们从字符串的末尾十进制个位开始每BASE_DIGITS位9位切一段 for (int i s.length(); i startPos; i - BASE_DIGITS) { int segmentEnd i; int segmentStart std::max(startPos, i - BASE_DIGITS); std::string segment s.substr(segmentStart, segmentEnd - segmentStart); // 将这段字符串转换为整数存入digits int digit std::stoi(segment); // stoi会自动处理前导0 digits.push_back(digit); } trim(); // 构造完成后去除可能的前导0 } BigInt::BigInt(const std::string s) { // 简单的有效性检查 if (s.empty() || (s[0] - s.size() 1) || (s[0] s.size() 1)) { // 处理空串或单独的符号默认为0 digits.push_back(0); isNegative false; return; } // 检查字符串是否全是数字和符号 for (size_t i (s[0] - || s[0] ) ? 1 : 0; i s.size(); i) { if (!std::isdigit(s[i])) { throw std::invalid_argument(Invalid character in BigInt string: s); } } fromString(s); }实操心得字符串解析是错误输入的“重灾区”。一定要做好边界检查和异常处理。例如字符串“-”、“”、空串、包含非数字字符等情况。std::stoi在遇到“00123”时会正确处理为123这很方便。另外注意substr的参数确保不会越界。3.2 加法与减法实现加法和减法是基础但需要仔细处理符号和进位/借位。我们实现一个不考虑符号的绝对值加法add和绝对值减法sub然后在operator和operator-中根据操作数的符号组合来调用它们。// 不考虑符号的绝对值相加假设a, b都非负且a的位数 b的位数 static std::vectorint addAbs(const std::vectorint a, const std::vectorint b) { std::vectorint result; int carry 0; for (size_t i 0; i a.size() || carry; i) { int sum carry; if (i a.size()) sum a[i]; if (i b.size()) sum b[i]; carry sum BigInt::BASE; if (carry) sum - BigInt::BASE; result.push_back(sum); } return result; } // 不考虑符号的绝对值相减假设a, b都非负且a b static std::vectorint subAbs(const std::vectorint a, const std::vectorint b) { std::vectorint result; int borrow 0; for (size_t i 0; i a.size(); i) { int diff a[i] - borrow; if (i b.size()) diff - b[i]; borrow diff 0; if (borrow) diff BigInt::BASE; result.push_back(diff); } // 去除结果中的前导0 while (result.size() 1 result.back() 0) { result.pop_back(); } return result; }有了这两个辅助函数operator的逻辑就清晰了如果同号绝对值相加符号不变。如果异号比较绝对值大小用大的减小的结果的符号取绝对值大的那个数的符号。处理结果为0的情况符号应为正。BigInt BigInt::operator(const BigInt rhs) const { if (isNegative rhs.isNegative) { // 同号相加 BigInt result; result.digits addAbs(this-digits, rhs.digits); result.isNegative this-isNegative; // 符号与加数相同 return result; } else { // 异号相加转化为减法 if (absGreater(rhs)) { // absGreater是一个比较绝对值大小的私有函数 // |this| |rhs| BigInt result; result.digits subAbs(this-digits, rhs.digits); result.isNegative this-isNegative; result.trim(); return result; } else { // |this| |rhs| BigInt result; result.digits subAbs(rhs.digits, this-digits); result.isNegative rhs.isNegative; result.trim(); return result; } } }减法operator-可以通过a - b a (-b)来实现这样只需复用加法逻辑代码更简洁。注意事项在实现subAbs时必须确保第一个参数被减数的绝对值大于等于第二个参数减数。否则会出现负数结果而我们的digits向量设计是不存储负数的。这就是为什么在operator中需要先比较绝对值大小。3.3 乘法实现从朴素到优化乘法是性能关键。最朴素的方法是模拟小学竖式复杂度是O(n²)。对于大数运算我们有更高效的算法比如Karatsuba算法能将复杂度降至约O(n^1.585)。这里我们先实现朴素算法保证正确性再讨论优化思路。朴素乘法实现BigInt BigInt::operator*(const BigInt rhs) const { BigInt result; result.digits.resize(this-digits.size() rhs.digits.size(), 0); // 结果最大位数 for (size_t i 0; i this-digits.size(); i) { long long carry 0; for (size_t j 0; j rhs.digits.size() || carry; j) { long long product result.digits[i j] carry; if (j rhs.digits.size()) { product (long long)this-digits[i] * rhs.digits[j]; } result.digits[i j] product % BASE; carry product / BASE; } } result.isNegative (this-isNegative ! rhs.isNegative); // 异号得负 result.trim(); return result; }这个双重循环就是标准的竖式乘法。注意我们用long long来存储中间乘积因为两个int小于10^9相乘最大约为10^18在long long通常最大9.22e18的范围内可以避免溢出。Karatsuba算法简介当数字非常大时比如上千位朴素乘法就太慢了。Karatsuba算法的核心思想是“分治”。它将两个大数X和Y各自分成两半X A * B^m BY C * B^m D 其中m大约是位数的一半B是进制对我们来说是BASE^m。 那么 X*Y AC * B^(2m) ((AB)(CD) - AC - BD) * B^m BD 这样一次大的乘法被分解成了三次较小的乘法AC, BD, (AB)(CD)和几次加减法。递归应用可以显著提升速度。实现Karatsuba需要精心处理递归基当数字较小时退化成朴素乘法和内存分配是一个很好的进阶挑战。性能权衡在作业或面试场景实现朴素乘法通常就够了但一定要能说出其复杂度是O(n²)并且知道有KaratsubaO(n^1.585)和更快的FFT-based乘法O(n log n)存在。在实际项目中如果对性能要求极高应该直接集成GMP这样的专业库。3.4 除法与取模实现除法是最复杂的运算我们采用高精度除以高精度的算法同样模拟竖式除法。这里介绍一个相对高效的“试商法”。基本思路是将被除数和除数都规范化通过乘以一个缩放因子使得除数的最高位足够大然后逐位计算商。简化版的高精度除法可以基于多次“高精度减高精度”来实现。由于实现较长这里给出一个简化版的思路框架适用于除数不是特别大的情况例如实现一个高精度除以long long的版本更为常见和实用// 一个更实用的版本BigInt 除以一个小的 int用于进制转换输出等 BigInt BigInt::operator/(long long rhs) const { if (rhs 0) throw std::runtime_error(Division by zero); BigInt result; result.digits.resize(digits.size()); long long remainder 0; for (int i (int)digits.size() - 1; i 0; --i) { // 从高位开始 long long current remainder * BASE digits[i]; result.digits[i] current / rhs; remainder current % rhs; } result.isNegative (isNegative ! (rhs 0)); result.trim(); return result; } // 对应的取模运算可以同时得到余数对于完整的BigInt / BigInt算法非常复杂。一个常见的策略是如果除数的位数很少比如1或2个digit可以将其转换为long long然后调用上面的函数否则实现完整的试商除法。许多教学性的大整数类会省略完整的除法或者只提供除以小整数的接口。避坑指南除法运算要特别注意除零异常。在实现完整的BigInt / BigInt时试商的过程很容易因为估算不准而导致多次回溯效率低下。一个技巧是用除数的最高两位或三位来更准确地估算商。同时处理符号也要小心遵循“同号得正异号得负”的规则但余数的符号定义在数学和编程语言中可能不同C11后规定商向0取整余数符号与被除数相同需要保持一致。4. 运算符重载、辅助功能与测试核心算法实现后我们需要完善接口让这个类用起来和内置类型一样顺手。4.1 比较运算符的实现比较运算符, , , , , !是其他运算如减法、除法的基础。实现的关键在于先比较符号再比较绝对值大小。bool operator(const BigInt lhs, const BigInt rhs) { // 1. 符号不同 if (lhs.isNegative !rhs.isNegative) return true; if (!lhs.isNegative rhs.isNegative) return false; // 2. 符号相同比较绝对值 if (lhs.isNegative) { // 两者都为负绝对值大的反而小 return absGreater(lhs, rhs); // 需要一个比较绝对值的辅助函数 } else { // 两者都为正 return absLess(lhs, rhs); } } bool operator(const BigInt lhs, const BigInt rhs) { return (lhs.isNegative rhs.isNegative) (lhs.digits rhs.digits); }其他比较运算符都可以基于和来定义例如a b等价于b aa b等价于!(b a)。4.2 输入输出流重载为了让BigInt能直接用cin和cout操作我们需要重载和运算符。std::ostream operator(std::ostream os, const BigInt num) { if (num.isNegative) os -; // 最高位直接输出不需要前导0 os (num.digits.empty() ? 0 : num.digits.back()); // 后续位需要补足BASE_DIGITS位前导0 for (int i (int)num.digits.size() - 2; i 0; --i) { os std::setw(BigInt::BASE_DIGITS) std::setfill(0) num.digits[i]; } return os; } std::istream operator(std::istream is, BigInt num) { std::string s; is s; // 直接从流中读取一个字符串 num BigInt(s); // 利用字符串构造函数 return is; }注意输出时除了最高位后面的每一位都需要用setw和setfill补足9位BASE_DIGITS否则像[123, 456]会错误地输出为“123456”而它实际表示的是“456000000123”。4.3 完整的测试案例实现完成后必须进行全面的测试。测试应覆盖边界情况、特殊值和常规运算。// test_bigint.cpp #include BigInt.h #include cassert #include iostream int main() { // 1. 构造与基本输出测试 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 // 2. 加法测试 BigInt sum1 a b; std::cout a b sum1 std::endl; // -86419753208641975320 assert(sum1 BigInt(-86419753208641975320)); BigInt sum2 a a; std::cout a a sum2 std::endl; // 24691357802469135780 // 3. 减法测试 BigInt diff1 a - b; std::cout a - b diff1 std::endl; // 111111111111111111100 BigInt diff2 c - d; std::cout c - d diff2 std::endl; // 24690 // 4. 乘法测试 BigInt prod1 a * c; std::cout a * c prod1 std::endl; // 152415787532388345001050 // 大数乘法 BigInt e(123456789); BigInt f(987654321); BigInt prod2 e * f; std::cout e * f prod2 std::endl; // 121932631112635269 assert(prod2 BigInt(121932631112635269)); // 5. 除法与取模测试使用除以小整数的版本 BigInt div1 a / 100; std::cout a / 100 div1 std::endl; // 123456789012345678 // 6. 比较运算符测试 assert(a c); assert(b d); assert(a ! b); assert(-a BigInt(-12345678901234567890)); // 7. 复合赋值测试 BigInt g(1000); g BigInt(500); std::cout g 500 g std::endl; // 1500 g * BigInt(3); std::cout g * 3 g std::endl; // 4500 // 8. 超大数测试如30! BigInt factorial(1); for (int i 1; i 30; i) { factorial * BigInt(i); } std::cout 30! factorial std::endl; // 正确结果265252859812191058636308480000000 std::cout All tests passed! std::endl; return 0; }5. 进阶优化、常见问题与扩展方向一个基础版本的大整数类已经完成但要从“能用”到“好用”、“高效”还有很长的路要走。5.1 性能优化策略乘法算法升级如前所述将朴素乘法替换为Karatsuba算法。可以设定一个阈值例如当数字位数超过100位时递归使用Karatsuba低于阈值则用朴素法。这能显著提升大数乘法的速度。内存管理std::vector在每次push_back可能导致重新分配和拷贝。对于已知大小的运算如乘法结果最大位数可以提前reserve空间。或者可以考虑使用自定义的内存池来管理digit数组。除法优化实现完整的BigInt / BigInt除法并优化试商过程。使用牛顿迭代法求倒数再进行乘法是另一种更高效但更复杂的思路。移动语义为BigInt类实现移动构造函数和移动赋值运算符避免在函数返回等场景下的不必要的深拷贝。BigInt(BigInt other) noexcept : digits(std::move(other.digits)), isNegative(other.isNegative) { other.isNegative false; other.digits {0}; }5.2 常见问题与调试技巧问题一输出结果错误尤其是末尾多出很多0。排查检查trim()函数是否正确实现并在每次可能产生前导0的运算后调用如构造、加减乘除后。trim()函数应该从向量的末尾开始移除所有值为0的元素直到遇到非零元素或只剩一个元素保证0的表示是[0]。void BigInt::trim() { while (digits.size() 1 digits.back() 0) { digits.pop_back(); } if (digits.size() 1 digits[0] 0) { isNegative false; // 规范0是非负数 } }问题二乘法或加法结果溢出得到负数或奇怪的大数。排查核心检查点是进位处理。在加法和乘法的循环中确保进位变量carry在每一步都被正确计算和传递。特别是在乘法中中间结果product必须用足够大的类型如long long来存储防止在(long long)a * b之前就溢出。问题三除法和取模的结果不符合预期。排查首先明确你遵循的余数定义C11标准(a/b)*b a%b a且a%b的符号与a相同。测试时用一些小数字包括正负验证a / b和a % b是否满足这个等式。问题四从字符串构造超长数字时崩溃或出错。排查检查fromString函数中字符串下标的计算特别是substr的起始位置和长度。使用std::stoi时确保截取的子串是有效的数字字符串。对于极长的字符串要确保循环边界i startPos的判断正确。5.3 功能扩展方向位运算实现左移()、右移()、按位与()、或(|)、异或(^)等。注意这里的移位是算术移位针对二进制需要先将大整数视为二进制补码形式实现起来比较复杂但很有挑战性。数论函数实现快速幂取模pow_mod、最大公约数gcd使用欧几里得算法或更高效的二进制算法、最小公倍数lcm。随机数生成生成一个指定位数的大随机素数这是RSA等加密算法的基础。不同进制转换除了十进制支持从二进制、十六进制字符串构造和输出。浮点数兼容实现与double的相互转换虽然可能会有精度损失。实现一个完整的大整数类是一个系统工程它涉及到底层数据结构、基本算法、面向对象设计、运算符重载、异常安全等多个方面。即使只实现加减乘除也能极大地锻炼你的C综合编程能力。建议你先实现一个基础版本并通过所有测试然后再选择一两个方向进行深度优化和扩展。在这个过程中你收获的将远不止一个大数计算工具。
C++大整数类实现：从高精度算法到运算符重载的完整指南
1. 项目概述为什么我们需要自己造轮子在C的标准库里int、long long这些内置整数类型大家用得都很顺手直到你遇到一个需要计算100的阶乘或者处理两个100位质数相乘的场景。这时编译器会毫不留情地告诉你溢出了。这就是“大整数”Big Integer问题最直接的体现——当数值范围远超CPU原生数据类型通常是64位最大值约9.22e18时我们必须自己设计一种数据结构来存储和运算。自己动手实现一个大整数类远不止是为了完成一次作业或应付面试。它是一个绝佳的练手项目能让你深入理解计算机如何表示和运算远超其字长的数字这是从“使用语言”到“理解语言背后逻辑”的关键一步。数据结构与算法的紧密结合如何高效地存储比如用字符串还是数组、如何设计加减乘除的算法小学竖式运算的计算机版本。面向对象设计的精髓如何封装内部复杂的表示对外提供清晰、易用且安全的接口比如重载运算符让大数用起来和普通int一样自然。性能与资源的权衡加法可以很简单但乘法呢除法呢如何优化避免成为性能瓶颈网上确实有很多现成的库如GMP但“知其然更要知其所以然”。亲手实现一遍你对内存管理、算法复杂度、接口设计的理解会深刻得多。接下来我们就从零开始设计并实现一个功能完整、接口友好、性能尚可的C大整数类。2. 核心设计思路与数据结构选型设计一个大整数类第一步也是最重要的一步就是决定如何在内存中表示这个“大”数。这直接决定了后续所有算法的效率和实现的复杂度。2.1 内部表示方案对比常见的内部表示方案主要有两种十进制字符串表示做法直接用std::string存储数字的字符串形式例如“12345678901234567890”。优点输入输出极其方便人类可读性强实现简单的加减法模拟竖式也比较直观。致命缺点运算效率极低。每一次运算都需要进行字符与数字的转换进位借位操作繁琐乘除法的复杂度会非常高O(n²)量级。内存利用率也不高一个字节只存储一个十进制位0-9。高精度进制如10^9进制数组表示做法使用std::vectorint或std::vectorlong long每个元素存储大整数的一部分。例如在10^9进制下数字“12345678901234567890”可以表示为[34567890, 12345678]因为12345678901234567890 12345678 * 10^9 34567890。优点这是业界标准做法如GMP库的核心思想。效率极高因为利用机器字长每个“位”可以存储一个很大的数如0到10^9-1一次运算能处理多位十进制数。运算直接加减乘除都可以在数组元素间直接进行利用CPU的ALU进行高速计算只需处理好进位和借位。内存紧凑存储密度高。缺点输入输出需要做进制转换实现稍复杂。设计决策为了追求性能和通用性我们毫不犹豫地选择高精度进制数组表示法。我们将采用10^9作为基底Base因为10^9 1,000,000,000小于2^31约21亿可以安全地用一个32位有符号int存储且两个这样的数相乘不会溢出64位long long的范围方便我们实现乘法。与十进制转换方便因为基底是10的幂。std::vectorint作为容器动态管理内存。2.2 类的整体框架设计确定了内部表示我们就可以勾勒出类的骨架。一个健壮的大整数类需要处理正负号、提供丰富的构造函数、重载常用运算符。// BigInt.h #ifndef BIGINT_H #define BIGINT_H #include vector #include string class BigInt { private: // 核心数据成员 std::vectorint digits; // 存储数字digits[0]是最低位个位 bool isNegative; // 符号位true表示负数 // 静态常量定义我们的进制系统 static const int BASE 1000000000; // 10^9 static const int BASE_DIGITS 9; // 每个元素对应的十进制位数 // 内部工具函数声明 void trim(); // 去除高位的无效0 void fromString(const std::string s); // 从字符串构造 public: // 构造函数 BigInt(); // 默认构造为0 BigInt(long long num); // 从long long构造 BigInt(const std::string s); // 从字符串构造 BigInt(const BigInt other); // 拷贝构造 // 赋值运算符 BigInt operator(const BigInt other); // 算术运算符重载成员函数形式 BigInt operator(const BigInt rhs) const; BigInt operator-(const BigInt rhs) const; BigInt operator*(const BigInt rhs) const; BigInt operator/(const BigInt rhs) const; BigInt operator%(const BigInt rhs) const; // 复合赋值运算符 BigInt operator(const BigInt rhs); BigInt operator-(const BigInt rhs); BigInt operator*(const BigInt rhs); BigInt operator/(const BigInt rhs); BigInt operator%(const BigInt rhs); // 比较运算符重载友元函数更常见 friend bool operator(const BigInt lhs, const BigInt rhs); friend bool operator!(const BigInt lhs, const BigInt rhs); friend bool operator(const BigInt lhs, const BigInt rhs); friend bool operator(const BigInt lhs, const BigInt rhs); friend bool operator(const BigInt lhs, const BigInt rhs); friend bool operator(const BigInt lhs, const BigInt rhs); // 一元运算符 BigInt operator-() const; // 取负 BigInt operator() const { return *this; } // 取正直接返回自身 // 输入输出 friend std::ostream operator(std::ostream os, const BigInt num); friend std::istream operator(std::istream is, BigInt num); // 转换为字符串 std::string toString() const; }; #endif // BIGINT_H这个框架定义了一个清晰的数据边界digits向量和isNegative标志是绝对私有的所有外部交互都通过公有接口进行。这符合面向对象封装的原则。3. 核心功能实现细节与算法剖析有了框架我们来逐一实现最核心的部分构造、加减、比较、乘除。这些算法的效率直接决定了整个类的性能。3.1 构造函数与字符串解析从long long构造相对简单不断除以BASE取余即可。难点在于从字符串构造因为字符串可能很长还可能包含正负号。// BigInt.cpp (部分) void BigInt::fromString(const std::string s) { digits.clear(); // 清空现有数据 isNegative false; int startPos 0; // 处理符号 if (!s.empty() (s[0] - || s[0] )) { isNegative (s[0] -); startPos 1; } // 核心分段读取字符串转换为BASE进制 // 我们从字符串的末尾十进制个位开始每BASE_DIGITS位9位切一段 for (int i s.length(); i startPos; i - BASE_DIGITS) { int segmentEnd i; int segmentStart std::max(startPos, i - BASE_DIGITS); std::string segment s.substr(segmentStart, segmentEnd - segmentStart); // 将这段字符串转换为整数存入digits int digit std::stoi(segment); // stoi会自动处理前导0 digits.push_back(digit); } trim(); // 构造完成后去除可能的前导0 } BigInt::BigInt(const std::string s) { // 简单的有效性检查 if (s.empty() || (s[0] - s.size() 1) || (s[0] s.size() 1)) { // 处理空串或单独的符号默认为0 digits.push_back(0); isNegative false; return; } // 检查字符串是否全是数字和符号 for (size_t i (s[0] - || s[0] ) ? 1 : 0; i s.size(); i) { if (!std::isdigit(s[i])) { throw std::invalid_argument(Invalid character in BigInt string: s); } } fromString(s); }实操心得字符串解析是错误输入的“重灾区”。一定要做好边界检查和异常处理。例如字符串“-”、“”、空串、包含非数字字符等情况。std::stoi在遇到“00123”时会正确处理为123这很方便。另外注意substr的参数确保不会越界。3.2 加法与减法实现加法和减法是基础但需要仔细处理符号和进位/借位。我们实现一个不考虑符号的绝对值加法add和绝对值减法sub然后在operator和operator-中根据操作数的符号组合来调用它们。// 不考虑符号的绝对值相加假设a, b都非负且a的位数 b的位数 static std::vectorint addAbs(const std::vectorint a, const std::vectorint b) { std::vectorint result; int carry 0; for (size_t i 0; i a.size() || carry; i) { int sum carry; if (i a.size()) sum a[i]; if (i b.size()) sum b[i]; carry sum BigInt::BASE; if (carry) sum - BigInt::BASE; result.push_back(sum); } return result; } // 不考虑符号的绝对值相减假设a, b都非负且a b static std::vectorint subAbs(const std::vectorint a, const std::vectorint b) { std::vectorint result; int borrow 0; for (size_t i 0; i a.size(); i) { int diff a[i] - borrow; if (i b.size()) diff - b[i]; borrow diff 0; if (borrow) diff BigInt::BASE; result.push_back(diff); } // 去除结果中的前导0 while (result.size() 1 result.back() 0) { result.pop_back(); } return result; }有了这两个辅助函数operator的逻辑就清晰了如果同号绝对值相加符号不变。如果异号比较绝对值大小用大的减小的结果的符号取绝对值大的那个数的符号。处理结果为0的情况符号应为正。BigInt BigInt::operator(const BigInt rhs) const { if (isNegative rhs.isNegative) { // 同号相加 BigInt result; result.digits addAbs(this-digits, rhs.digits); result.isNegative this-isNegative; // 符号与加数相同 return result; } else { // 异号相加转化为减法 if (absGreater(rhs)) { // absGreater是一个比较绝对值大小的私有函数 // |this| |rhs| BigInt result; result.digits subAbs(this-digits, rhs.digits); result.isNegative this-isNegative; result.trim(); return result; } else { // |this| |rhs| BigInt result; result.digits subAbs(rhs.digits, this-digits); result.isNegative rhs.isNegative; result.trim(); return result; } } }减法operator-可以通过a - b a (-b)来实现这样只需复用加法逻辑代码更简洁。注意事项在实现subAbs时必须确保第一个参数被减数的绝对值大于等于第二个参数减数。否则会出现负数结果而我们的digits向量设计是不存储负数的。这就是为什么在operator中需要先比较绝对值大小。3.3 乘法实现从朴素到优化乘法是性能关键。最朴素的方法是模拟小学竖式复杂度是O(n²)。对于大数运算我们有更高效的算法比如Karatsuba算法能将复杂度降至约O(n^1.585)。这里我们先实现朴素算法保证正确性再讨论优化思路。朴素乘法实现BigInt BigInt::operator*(const BigInt rhs) const { BigInt result; result.digits.resize(this-digits.size() rhs.digits.size(), 0); // 结果最大位数 for (size_t i 0; i this-digits.size(); i) { long long carry 0; for (size_t j 0; j rhs.digits.size() || carry; j) { long long product result.digits[i j] carry; if (j rhs.digits.size()) { product (long long)this-digits[i] * rhs.digits[j]; } result.digits[i j] product % BASE; carry product / BASE; } } result.isNegative (this-isNegative ! rhs.isNegative); // 异号得负 result.trim(); return result; }这个双重循环就是标准的竖式乘法。注意我们用long long来存储中间乘积因为两个int小于10^9相乘最大约为10^18在long long通常最大9.22e18的范围内可以避免溢出。Karatsuba算法简介当数字非常大时比如上千位朴素乘法就太慢了。Karatsuba算法的核心思想是“分治”。它将两个大数X和Y各自分成两半X A * B^m BY C * B^m D 其中m大约是位数的一半B是进制对我们来说是BASE^m。 那么 X*Y AC * B^(2m) ((AB)(CD) - AC - BD) * B^m BD 这样一次大的乘法被分解成了三次较小的乘法AC, BD, (AB)(CD)和几次加减法。递归应用可以显著提升速度。实现Karatsuba需要精心处理递归基当数字较小时退化成朴素乘法和内存分配是一个很好的进阶挑战。性能权衡在作业或面试场景实现朴素乘法通常就够了但一定要能说出其复杂度是O(n²)并且知道有KaratsubaO(n^1.585)和更快的FFT-based乘法O(n log n)存在。在实际项目中如果对性能要求极高应该直接集成GMP这样的专业库。3.4 除法与取模实现除法是最复杂的运算我们采用高精度除以高精度的算法同样模拟竖式除法。这里介绍一个相对高效的“试商法”。基本思路是将被除数和除数都规范化通过乘以一个缩放因子使得除数的最高位足够大然后逐位计算商。简化版的高精度除法可以基于多次“高精度减高精度”来实现。由于实现较长这里给出一个简化版的思路框架适用于除数不是特别大的情况例如实现一个高精度除以long long的版本更为常见和实用// 一个更实用的版本BigInt 除以一个小的 int用于进制转换输出等 BigInt BigInt::operator/(long long rhs) const { if (rhs 0) throw std::runtime_error(Division by zero); BigInt result; result.digits.resize(digits.size()); long long remainder 0; for (int i (int)digits.size() - 1; i 0; --i) { // 从高位开始 long long current remainder * BASE digits[i]; result.digits[i] current / rhs; remainder current % rhs; } result.isNegative (isNegative ! (rhs 0)); result.trim(); return result; } // 对应的取模运算可以同时得到余数对于完整的BigInt / BigInt算法非常复杂。一个常见的策略是如果除数的位数很少比如1或2个digit可以将其转换为long long然后调用上面的函数否则实现完整的试商除法。许多教学性的大整数类会省略完整的除法或者只提供除以小整数的接口。避坑指南除法运算要特别注意除零异常。在实现完整的BigInt / BigInt时试商的过程很容易因为估算不准而导致多次回溯效率低下。一个技巧是用除数的最高两位或三位来更准确地估算商。同时处理符号也要小心遵循“同号得正异号得负”的规则但余数的符号定义在数学和编程语言中可能不同C11后规定商向0取整余数符号与被除数相同需要保持一致。4. 运算符重载、辅助功能与测试核心算法实现后我们需要完善接口让这个类用起来和内置类型一样顺手。4.1 比较运算符的实现比较运算符, , , , , !是其他运算如减法、除法的基础。实现的关键在于先比较符号再比较绝对值大小。bool operator(const BigInt lhs, const BigInt rhs) { // 1. 符号不同 if (lhs.isNegative !rhs.isNegative) return true; if (!lhs.isNegative rhs.isNegative) return false; // 2. 符号相同比较绝对值 if (lhs.isNegative) { // 两者都为负绝对值大的反而小 return absGreater(lhs, rhs); // 需要一个比较绝对值的辅助函数 } else { // 两者都为正 return absLess(lhs, rhs); } } bool operator(const BigInt lhs, const BigInt rhs) { return (lhs.isNegative rhs.isNegative) (lhs.digits rhs.digits); }其他比较运算符都可以基于和来定义例如a b等价于b aa b等价于!(b a)。4.2 输入输出流重载为了让BigInt能直接用cin和cout操作我们需要重载和运算符。std::ostream operator(std::ostream os, const BigInt num) { if (num.isNegative) os -; // 最高位直接输出不需要前导0 os (num.digits.empty() ? 0 : num.digits.back()); // 后续位需要补足BASE_DIGITS位前导0 for (int i (int)num.digits.size() - 2; i 0; --i) { os std::setw(BigInt::BASE_DIGITS) std::setfill(0) num.digits[i]; } return os; } std::istream operator(std::istream is, BigInt num) { std::string s; is s; // 直接从流中读取一个字符串 num BigInt(s); // 利用字符串构造函数 return is; }注意输出时除了最高位后面的每一位都需要用setw和setfill补足9位BASE_DIGITS否则像[123, 456]会错误地输出为“123456”而它实际表示的是“456000000123”。4.3 完整的测试案例实现完成后必须进行全面的测试。测试应覆盖边界情况、特殊值和常规运算。// test_bigint.cpp #include BigInt.h #include cassert #include iostream int main() { // 1. 构造与基本输出测试 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 // 2. 加法测试 BigInt sum1 a b; std::cout a b sum1 std::endl; // -86419753208641975320 assert(sum1 BigInt(-86419753208641975320)); BigInt sum2 a a; std::cout a a sum2 std::endl; // 24691357802469135780 // 3. 减法测试 BigInt diff1 a - b; std::cout a - b diff1 std::endl; // 111111111111111111100 BigInt diff2 c - d; std::cout c - d diff2 std::endl; // 24690 // 4. 乘法测试 BigInt prod1 a * c; std::cout a * c prod1 std::endl; // 152415787532388345001050 // 大数乘法 BigInt e(123456789); BigInt f(987654321); BigInt prod2 e * f; std::cout e * f prod2 std::endl; // 121932631112635269 assert(prod2 BigInt(121932631112635269)); // 5. 除法与取模测试使用除以小整数的版本 BigInt div1 a / 100; std::cout a / 100 div1 std::endl; // 123456789012345678 // 6. 比较运算符测试 assert(a c); assert(b d); assert(a ! b); assert(-a BigInt(-12345678901234567890)); // 7. 复合赋值测试 BigInt g(1000); g BigInt(500); std::cout g 500 g std::endl; // 1500 g * BigInt(3); std::cout g * 3 g std::endl; // 4500 // 8. 超大数测试如30! BigInt factorial(1); for (int i 1; i 30; i) { factorial * BigInt(i); } std::cout 30! factorial std::endl; // 正确结果265252859812191058636308480000000 std::cout All tests passed! std::endl; return 0; }5. 进阶优化、常见问题与扩展方向一个基础版本的大整数类已经完成但要从“能用”到“好用”、“高效”还有很长的路要走。5.1 性能优化策略乘法算法升级如前所述将朴素乘法替换为Karatsuba算法。可以设定一个阈值例如当数字位数超过100位时递归使用Karatsuba低于阈值则用朴素法。这能显著提升大数乘法的速度。内存管理std::vector在每次push_back可能导致重新分配和拷贝。对于已知大小的运算如乘法结果最大位数可以提前reserve空间。或者可以考虑使用自定义的内存池来管理digit数组。除法优化实现完整的BigInt / BigInt除法并优化试商过程。使用牛顿迭代法求倒数再进行乘法是另一种更高效但更复杂的思路。移动语义为BigInt类实现移动构造函数和移动赋值运算符避免在函数返回等场景下的不必要的深拷贝。BigInt(BigInt other) noexcept : digits(std::move(other.digits)), isNegative(other.isNegative) { other.isNegative false; other.digits {0}; }5.2 常见问题与调试技巧问题一输出结果错误尤其是末尾多出很多0。排查检查trim()函数是否正确实现并在每次可能产生前导0的运算后调用如构造、加减乘除后。trim()函数应该从向量的末尾开始移除所有值为0的元素直到遇到非零元素或只剩一个元素保证0的表示是[0]。void BigInt::trim() { while (digits.size() 1 digits.back() 0) { digits.pop_back(); } if (digits.size() 1 digits[0] 0) { isNegative false; // 规范0是非负数 } }问题二乘法或加法结果溢出得到负数或奇怪的大数。排查核心检查点是进位处理。在加法和乘法的循环中确保进位变量carry在每一步都被正确计算和传递。特别是在乘法中中间结果product必须用足够大的类型如long long来存储防止在(long long)a * b之前就溢出。问题三除法和取模的结果不符合预期。排查首先明确你遵循的余数定义C11标准(a/b)*b a%b a且a%b的符号与a相同。测试时用一些小数字包括正负验证a / b和a % b是否满足这个等式。问题四从字符串构造超长数字时崩溃或出错。排查检查fromString函数中字符串下标的计算特别是substr的起始位置和长度。使用std::stoi时确保截取的子串是有效的数字字符串。对于极长的字符串要确保循环边界i startPos的判断正确。5.3 功能扩展方向位运算实现左移()、右移()、按位与()、或(|)、异或(^)等。注意这里的移位是算术移位针对二进制需要先将大整数视为二进制补码形式实现起来比较复杂但很有挑战性。数论函数实现快速幂取模pow_mod、最大公约数gcd使用欧几里得算法或更高效的二进制算法、最小公倍数lcm。随机数生成生成一个指定位数的大随机素数这是RSA等加密算法的基础。不同进制转换除了十进制支持从二进制、十六进制字符串构造和输出。浮点数兼容实现与double的相互转换虽然可能会有精度损失。实现一个完整的大整数类是一个系统工程它涉及到底层数据结构、基本算法、面向对象设计、运算符重载、异常安全等多个方面。即使只实现加减乘除也能极大地锻炼你的C综合编程能力。建议你先实现一个基础版本并通过所有测试然后再选择一两个方向进行深度优化和扩展。在这个过程中你收获的将远不止一个大数计算工具。
