1. 项目概述为什么我们需要自己实现BigInteger在C的标准库里int、long long这些内置整数类型大家用起来得心应手直到你某天需要计算一个100位的阶乘或者处理RSA加密算法里那些天文数字般的密钥。这时编译器会毫不留情地告诉你溢出了。这就是内置整数类型的边界它们的位数是固定的由硬件和编译器决定无法处理任意大的整数。BigInteger大整数类就是为了突破这个限制而生的它允许我们像操作普通整数一样进行加、减、乘、除等运算但数字的位数只受限于计算机的内存。你可能在LeetCode上刷到过“字符串相加”、“两数相乘大数版”这类题目它们本质上就是BigInteger的简化版面试题。自己动手实现一个完整的BigInteger类远不止是为了解决一道算法题。这个过程会让你深入理解数据的底层表示计算机如何存储和操作远超寄存器容量的数据基本算法的工程化如何将小学竖式计算的原理转化为高效、健壮的代码内存管理在C中如何安全、高效地管理动态数组避免内存泄漏和越界运算符重载如何让自定义类型拥有和内置类型一样的语法糖写出a b * c这样直观的表达式接下来我将带你从零开始构建一个支持基础四则运算、具备良好接口的BigInteger类。我们会采用最直观、也最易于理解的实现方式——基于十进制字符串或数组的表示并逐步优化。无论你是想深化C理解应对面试还是为某个需要大数运算的项目打基础这篇内容都能提供一条清晰的路径。2. 核心设计如何表示一个任意大的整数实现BigInteger的第一步也是最重要的一步是确定它在内存中的表示形式。这直接决定了后续所有算法的效率和实现的复杂度。2.1 存储方案选型为什么选择十进制数组常见的存储方案主要有三种二进制位存储像内置类型一样用vectorbool或位运算来存储每一个二进制位。这种方式空间效率最高但与人类可读的十进制转换非常耗时算法实现尤其是除法也较为复杂不适合入门。大进制块存储例如以10^91000000000为基每个int存储0到999999999之间的数。这是工业级库如GMP常用的方法它在空间效率、计算效率以及与十进制字符串的转换效率之间取得了绝佳的平衡。但实现复杂度较高。十进制数组存储用vectorint或string每个元素存储一个十进制数字0-9。这是最直观、最容易理解和实现的方式与我们的书写习惯完全一致方便调试和输入输出。对于我们的教学和大多数应用场景十进制数组存储是最佳起点。我们选择vectorint来存储每一位数字并且约定数字的低位存储在数组的低索引位置。例如数字“12345”在vectorint中存储为{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::vectorint 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” } // 拷贝构造函数、析构函数、赋值运算符等使用编译器默认生成即可 // 因为vectorint和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符号不同负数永远小于正数。符号相同均为负绝对值大的数更小例如 -100 -10。符号相同均为正绝对值大的数更大。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并设置borrow1。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; } };加法运算符的逻辑分解同号相加绝对值相加符号不变。简单直接。异号相加这本质上是一个减法。结果的符号由绝对值大的那个数决定。我们通过compareMagnitude比较绝对值大小然后调用subtractMagnitude确保用大的减小的最后赋予结果正确的符号。减法运算符巧妙地利用了一元负号和加法来实现这大大简化了代码。operator-()返回当前对象的相反数。注意事项在实现operator-()时要特别处理0的情况。数学上-0等于0我们应避免产生一个isNegativetrue但值为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::pairBigInteger, 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; } };除法算法解析 这是经典的长除法模拟和我们手算的过程一模一样从被除数最高位开始取一位或一段作为current。看current能减去多少次divisor这个次数就是商在这一位上的数字。将current减去divisor * count后剩下的作为新的current。被除数的下一位落下来接在current后面重复步骤2-3。关键细节current.digits.insert(current.digits.begin(), ...)模拟了“落位”操作。试商过程while (current divisor)对于十进制个位数来说很快但如果除数很大这里可以优化为二分查找0-9范围内查找。商的符号规则是“同号得正异号得负”。余数的符号在数学上有不同定义C11标准规定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,(ab)(cd)来计算xy时间复杂度从O(n²)降到约O(n^1.585)。当数字位数很大时比如超过几百位优势明显。牛顿迭代法求除法通过乘法来逼近除法结果对于特别大的数比长除法快得多。这通常需要实现一个高精度的倒数近似算法。6.3 内存与拷贝优化移动语义为BigInteger实现移动构造函数和移动赋值运算符。在返回临时对象或进行a b c这类操作时可以避免不必要的深拷贝。SSOSmall 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 常见问题与排查表在实现和测试过程中你可能会遇到以下问题问题现象可能原因排查与解决思路结果完全错误或乱码1.digits数组存储顺序混乱高位在前还是低位在前。2. 在加减乘除循环中数组索引越界。3. 进位/借位处理逻辑错误特别是最高位的进位丢失或借位多借。1.统一约定坚持“低位在前”。在所有输入构造函数、输出operator和运算内部都遵循此约定。2.使用vector.at(i)代替[i]在调试阶段开启边界检查。3.单步调试用一个简单的例子如1234100-1跟踪每一步的digits和carry/borrow值。前导零导致比较或运算出错没有在构造函数和运算后正确调用trimZeros()。例如[0,0,1,2]代表2100而不是12。1. 确保在每个可能产生前导零的地方都调用trimZeros()构造函数、减法、乘法、除法。2. 在compareMagnitude函数中先比较digits.size()是有效的但前提是数字已经过trim。负数运算结果符号错误加减法中异号情况下的符号判断逻辑有误。乘除法中符号规则应用错误。1.重温符号规则加法“同号加异号减符号随绝对值大的”乘法“同号得正异号得负”除法商同乘法余数同被除数。2. 用(-5) 25 (-2)(-5) * 25 * (-2)(-5) / 25 / (-2)等边界案例测试。除以零导致崩溃除法运算前没有检查除数是否为零。在divideAndRemainder函数开头添加除零检查并抛出std::runtime_error异常。大数运算速度极慢1. 使用了十进制存储而非更高进制。2. 乘法是O(n²)的朴素算法。3. 在循环中频繁进行vector的push_back或insert导致重分配。1.升级到万进制是性价比最高的优化。2. 实现Karatsuba乘法。3. 对于乘法预分配结果数组大小digits.size() other.digits.size()。对于除法避免在循环中频繁insert可以先用一个临时数组存储商位最后再反转。内存泄漏虽然使用了vector一般不会泄漏但如果在类中添加了原始指针成员需要实现“三/五法则”。使用valgrind等工具检测。对于当前设计使用默认的拷贝构造、赋值和析构即可Rule of Zero。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学习路上一个坚实的里程碑其背后涉及的思维训练远比调用一个现成的库有价值得多。