1. 从“溢出”的烦恼到“无限”的可能为什么我们需要Bigint在写代码的日常里整数运算就像呼吸一样自然。int a 10; int b 20; int c a b;简单直接结果30稳稳地躺在变量c里。但如果你尝试计算2147483647 1呢对于一个32位有符号整数int32_t来说2147483647是它能表示的最大正数。再加1结果并不会如你所愿地变成2147483648而是会“溢出”变成一个负数-2147483648。这个现象就是整数溢出。在金融计算、密码学、科学模拟、大数运算比如计算斐波那契数列的第1000项等场景下标准数据类型如int,long long那有限的位数通常是32位或64位完全不够用溢出会导致灾难性的、难以察觉的错误。这时候Bigint高精度整数就登场了。它不是一个内置类型而是一个我们自己用代码“封装”或“模拟”出来的数据结构。它的核心思想很简单既然一个int装不下那就用多个int来装。我们可以用一个数组比如std::vectorint来存储一个大数的每一位然后自己实现加法、减法、乘法、除法、取模这些基本运算的规则。这听起来像是回到了小学我们重新学习“竖式计算”只不过这次是用代码来模拟笔算的过程。所以封装一个Bigint模板本质上是在为你的程序赋予处理任意大小整数的超能力。它让你摆脱了硬件位宽的限制在逻辑层面实现了“无限”精度的整数运算当然实际受限于内存大小。接下来我将带你从零开始一步步构建一个功能完整、逻辑清晰的Bigint类并深入解释每一步背后的“为什么”以及那些教科书上不会写的“坑”。2. 地基Bigint的数据结构与构造函数设计一个健壮的Bigint类始于一个深思熟虑的内部表示。这里有几个关键决策点每一个都影响着后续所有操作的效率和复杂度。2.1 存储基数的选择为什么是10000而不是10最直观的想法是用一个vectorint每个元素存储十进制的一位0-9。这很符合人类的阅读习惯。但这样做效率很低。考虑两个1000位的数相加你需要进行大约1000次单个数位的加法以及相应的进位处理。每次运算操作的数据单元太小导致循环次数极多。更高效的做法是采用一个较大的基数Base。例如我们选择基数BASE 10000。这意味着我们的vectorint中的每一个元素存储的不是一个十进制位而是一个0到9999之间的数即一个“万进制”位。为什么是10000计算效率基数扩大存储大数所需的数组长度会显著缩短。一个n位的十进制数用基数为BASE的数组存储长度大约是n / log10(BASE)。BASE10000时log10(10000)4数组长度约为原来的1/4。进行四则运算时循环次数也相应减少提升了速度。进位处理10000这个数很好因为它小于int通常32位的最大值约21亿。两个“万进制”位相乘最大约10^8或相加最大约2*10^4的结果仍然可以安全地存储在一个int中而不会溢出这简化了中间运算的进位处理。输出方便10000是10的整数次幂10^4在将内部表示转换为十进制字符串输出时每个“万进制”位刚好对应固定的4个十进制位不足前补零转换算法非常规整高效。当然你也可以选择BASE100000000010^9这样每个元素存储0-999999999数组更短但要注意两个这样的数相乘可能会超过32位int的范围此时需要用64位整数long long来存储中间结果。这是一个典型的“时间-空间-实现复杂度”的权衡。我们以BASE10000为例进行讲解它平衡了效率和实现的简洁性。因此我们的私有数据成员可以这样设计class Bigint { private: std::vectorint digits; // 存储万进制位digits[0]是最低位个位 bool is_negative; // 符号位true表示负数 static const int BASE 10000; static const int BASE_DIGITS 4; // 每个万进制位对应的十进制位数 // ... 其他成员函数 };这里有一个非常重要的约定digits数组采用小端序存储即digits[0]存储的是最低位相当于个位。这符合我们手工计算的习惯从低位开始处理进位最为方便。2.2 构造与赋值处理字符串与去零Bigint需要能从多种类型构造最常用的是从std::string构造。这个过程本质上是将十进制字符串解析为我们内部的万进制数组。Bigint(const std::string s) { is_negative false; int pos 0; // 处理符号 if (s[pos] -) { is_negative true; pos; } else if (s[pos] ) { pos; } // 从字符串末尾开始每BASE_DIGITS位4位切分一段转换为整数存入digits for (int i s.length() - 1; i pos; i - BASE_DIGITS) { int digit 0; // 计算当前段的起始和结束位置 int start std::max(pos, i - BASE_DIGITS 1); for (int j start; j i; j) { digit digit * 10 (s[j] - 0); } digits.push_back(digit); } // 去除前导零在最高位 trim(); }trim()函数是一个辅助函数用于移除digits中最高位的无效零除非整个数为0。这是保证数据规范性的关键一步能避免在比较和输出时产生问题。void trim() { while (digits.size() 1 digits.back() 0) { digits.pop_back(); } if (digits.size() 1 digits[0] 0) { is_negative false; // 规范0没有负号 } }注意在实现trim()时一定要保留一个0表示数字0本身。同时要将0的符号强制设为正这是一个广泛遵循的约定可以避免很多边界判断的麻烦。此外我们还需要实现从内置整数类型如int,long long的构造以及拷贝构造、赋值运算符等。从整数构造相对简单就是不断对BASE取模和除。3. 核心运算实现一加法与减法加法和减法是所有运算的基础。它们的共同点是都需要处理按位运算和进位/借位。3.1 无符号加法模拟竖式计算我们首先实现一个不考虑符号的、针对绝对值相加的辅助函数add_vectors。它接受两个表示绝对值的vectorint返回它们相加的结果。std::vectorint add_vectors(const std::vectorint a, const std::vectorint b) { std::vectorint res; int carry 0; // 进位 size_t i 0; // 遍历两个数组的每一位 for (; i a.size() || i b.size() || carry; i) { int sum carry; if (i a.size()) sum a[i]; if (i b.size()) sum b[i]; res.push_back(sum % BASE); // 当前位结果 carry sum / BASE; // 新的进位 } return res; }这个过程完全模拟了手工竖式加法从最低位开始对应位相加加上低位的进位得到当前位的和与新的进位。3.2 带符号的加法运算符重载有了无符号加法再结合符号判断就能实现完整的operator。Bigint operator(const Bigint other) const { Bigint result; // 同号相加 if (is_negative other.is_negative) { result.digits add_vectors(this-digits, other.digits); result.is_negative this-is_negative; // 结果符号与加数相同 } else { // 异号相加转化为绝对值相减 // 比较两个数的绝对值大小 bool this_abs_larger this-abs_greater_or_equal(other); result.digits this_abs_larger ? subtract_vectors(this-digits, other.digits) : subtract_vectors(other.digits, this-digits); // 结果的符号取绝对值大的那个数的符号 result.is_negative this_abs_larger ? this-is_negative : other.is_negative; } result.trim(); return result; }这里的关键是异号相加转化为减法。我们需要一个比较绝对值大小的函数abs_greater_or_equal和一个无符号减法函数subtract_vectors。3.3 无符号减法与借位处理无符号减法假设a b。实现时同样模拟竖式减法处理借位。std::vectorint subtract_vectors(const std::vectorint a, const std::vectorint b) { std::vectorint res; int borrow 0; // 借位 for (size_t i 0; i a.size(); i) { int diff a[i] - borrow; if (i b.size()) { diff - b[i]; } if (diff 0) { diff BASE; // 不够减向高位借1当BASE borrow 1; } else { borrow 0; } res.push_back(diff); } // 减法结果最高位可能产生前导零需要trim但这里先保留由调用者trim return res; }踩坑点在减法中借位borrow的处理必须非常小心。borrow的值0或1是在计算完当前位diff之后根据diff是否小于0来确定的用于下一次循环。这个顺序不能错。同时向高位借位相当于在当前位加上了BASE。3.4 减法的实现减法operator-可以基于加法来实现a - b a (-b)。因此我们可以先实现一个取负运算符operator-()一元运算符然后复用加法逻辑。Bigint operator-() const { Bigint negated *this; if (!(digits.size() 1 digits[0] 0)) { // 0的负号还是0 negated.is_negative !is_negative; } return negated; } Bigint operator-(const Bigint other) const { return (*this) (-other); // 巧妙转化为加法 }这种方法非常简洁但依赖于加法的正确性。你也可以像加法一样根据符号情况分同号相减和异号相减来直接实现逻辑是对称的。4. 核心运算实现二乘法乘法比加减法复杂常见的有两种方法朴素竖式乘法和Karatsuba快速乘法。我们先从最直观的朴素乘法开始它易于理解和实现时间复杂度为O(n²)其中n是位数。4.1 朴素竖式乘法原理回忆一下我们如何计算123 * 4561 2 3 x 4 5 6 ------------ 7 3 8 (123 * 6) 6 1 5 (123 * 5, 左移一位) 4 9 2 (123 * 4, 左移两位) ------------ 5 6 0 8 8在万进制下这个过程是类似的。a的第i位与b的第j位相乘结果会加到最终结果的第ij位上并可能产生进位。4.2 代码实现与中间结果溢出Bigint operator*(const Bigint other) const { Bigint result; // 结果的最大位数不超过两者位数之和 result.digits.resize(this-digits.size() other.digits.size(), 0); for (size_t i 0; i this-digits.size(); i) { long long carry 0; // 使用long long防止中间溢出 for (size_t j 0; j other.digits.size() || carry; j) { // 计算当前位的结果 long long cur result.digits[i j] carry; if (j other.digits.size()) { cur (long long)this-digits[i] * other.digits[j]; // 关键强制转换 } result.digits[i j] cur % BASE; carry cur / BASE; } } result.is_negative (this-is_negative ! other.is_negative); // 异号为负 result.trim(); return result; }这里有一个极其关键的细节this-digits[i] * other.digits[j]的结果最大可能是(BASE-1)*(BASE-1)。当BASE10000时这个值是9999*999999980001小于10^8还在32位int的范围内。但是我们还需要加上result.digits[ij]和carry。在极端情况下cur可能会超过2^31-1导致32位有符号整数溢出。因此我们必须使用long long通常是64位来存储中间累加结果cur和进位carry。这是实现乘法时最容易忽略的坑。实操心得在编写涉及大数中间计算的代码时养成习惯对任何可能超过单步计算范围的中间变量使用更宽的数据类型如long long来存储。这能避免许多隐蔽的溢出错误。4.3 关于Karatsuba算法当处理非常大的数字比如成千上万位时O(n²)的朴素乘法会成为性能瓶颈。Karatsuba算法是一种分治算法能将乘法时间复杂度降至约O(n^1.585)。其核心思想是将两个大数x和y分别拆分成高位和低位x a*B^m b,y c*B^m d。那么x*y ac*B^(2m) ((ab)(cd) - ac - bd)*B^m bd。这样只需要进行3次规模减半的乘法ac,bd,(ab)(cd)而不是4次。递归应用此方法即可。实现Karatsuba需要处理更复杂的拆分、合并和符号问题代码比朴素乘法复杂得多。对于大多数应用场景位数在几千以内优化后的朴素乘法已经足够快。只有当性能成为关键瓶颈时才值得引入Karatsuba。5. 核心运算实现三除法与取模除法和取模是最复杂的运算因为它们涉及到试商。我们通常实现一个“除法兼取模”的操作一次性得到商和余数。5.1 高精度除以低精度int这是一个相对简单的情况可以作为理解除法过程的起点。我们模拟手工除法从最高位开始当前被除数current 上一步余数 * BASE 当前位然后计算current / divisor得到商的一位更新余数current % divisor给下一位用。// 高精度除以低精度返回商remainder参数返回余数 Bigint divide_by_small_int(int divisor, int remainder) const { Bigint quotient; remainder 0; quotient.digits.resize(digits.size()); // 从最高位开始处理 for (int i digits.size() - 1; i 0; --i) { long long current (long long)remainder * BASE digits[i]; quotient.digits[i] current / divisor; remainder current % divisor; } quotient.trim(); quotient.is_negative (this-is_negative ! (divisor 0)); if (quotient.digits.size() 1 quotient.digits[0] 0) { quotient.is_negative false; } return quotient; }5.2 高精度除以高精度试商法当除数和被除数都是高精度数时情况变得复杂。最经典的算法是Knuth的“高精度除法算法 D”也常被称为“试商法”。其核心步骤是规范化将除数和被除数同时乘以一个缩放因子d使得除数的最高位bn-1BASE/2。这可以使得后续的试商更准确通常只需要尝试1-2次就能确定正确的商位。d可以取BASE / (bn-1 1)。逐位计算商从被除数的高位开始取与被除数最高几位构成的临时被除数temp估算temp / (bn-1)作为试商qhat。修正试商因为估算可能偏大最多偏大2需要用除数的前两位来更精确地检验和修正qhat。乘减用修正后的商q乘以整个除数然后从被除数的对应位置减去。这一步是另一个高精度乘法和减法。处理余数如果减法导致借位结果为负说明商q还是大了1需要将商减1同时把除数加回到被除数对应位置相当于归还借位。记录商位将正确的商q记录在结果的对应位上。循环重复步骤2-6处理下一位。由于该算法实现较为冗长这里给出一个概念性的框架和关键点std::pairBigint, Bigint divide(const Bigint dividend, const Bigint divisor) { // 处理特殊情况除数为0被除数绝对值小于除数等 if (divisor 0) throw std::runtime_error(Division by zero); if (dividend.abs() divisor.abs()) { return {Bigint(0), dividend}; // 商为0余数为被除数 } // 1. 规范化 int d BASE / (divisor.digits.back() 1); Bigint norm_dividend dividend * d; Bigint norm_divisor divisor * d; // ... 后续实现Knuth算法D // 2. 初始化商和余数 // 3. 主循环逐位试商、乘减、修正 // 4. 反规范化余数真正的余数 计算得到的余数 / d // 5. 设置商和余数的符号 // 6. 返回商和余数对 }重要提示自己完整实现Knuth算法D是一个很好的练习但代码量较大且容易在边界条件如试商修正、借位处理上出错。在实际项目中可以考虑使用成熟的库如GMP或者仔细参考可靠的实现。对于学习目的理解其原理和步骤比盲目敲出代码更重要。5.3 运算符重载/ 和 %基于上面的divide函数我们可以轻松重载除法(/)和取模(%)运算符Bigint operator/(const Bigint other) const { auto [quotient, remainder] divide(*this, other); return quotient; } Bigint operator%(const Bigint other) const { auto [quotient, remainder] divide(*this, other); return remainder; }注意对于负数C标准中整数除法的规则是“向零取整”。我们的Bigint实现也应遵循这一规则以确保行为一致。这意味着在确定商和余数的符号时需要额外的逻辑商的符号由被除数和除数的符号决定异号为负余数的符号始终与被除数相同。这是%运算符在C/C/Java等语言中的定义。6. 辅助功能、优化与边界处理一个完整的Bigint类还需要很多周边功能它们虽不涉及核心算法但对易用性和健壮性至关重要。6.1 比较运算符实现,,,,,!。比较的逻辑是先比较符号。正数 0 负数。如果同为正先比较位数位数多的大位数相同则从最高位开始逐位比较。如果同为负则比较其绝对值绝对值大的反而小。6.2 输入输出流重载重载和运算符方便使用cin/cout进行输入输出。输出时需要将内部的万进制数组转换为十进制字符串。由于我们存储是小端序需要从最高位开始输出并且每个万进制位要输出固定的4位数字前导补零但最高位除外。std::ostream operator(std::ostream os, const Bigint num) { if (num.is_negative) os -; os num.digits.back(); // 最高位无需补零 for (int i num.digits.size() - 2; i 0; --i) { os std::setw(BASE_DIGITS) std::setfill(0) num.digits[i]; } return os; }输入流重载则需要读取字符串然后调用我们之前实现的字符串构造函数。6.3 性能优化浅谈预留空间Reserve在vector操作如push_back前如果能预知大致大小使用reserve()预先分配内存可以减少多次重新分配和拷贝的开销。移动语义为Bigint实现移动构造函数和移动赋值运算符在临时对象传递时避免深拷贝。操作符的复合赋值形式实现,-,*,/,%。这些运算符可以直接在自身修改避免创建临时对象效率更高。例如a b比a a b更高效。除法优化如前所述对于除以小整数的情况使用专门的快速路径。6.4 边界条件与异常处理除零错误在除法和取模运算中必须检查除数是否为零并抛出异常或进行错误处理。前导零确保在所有可能产生前导零的运算如减法、乘法、除法后调用trim()。零的符号强制规定0的符号为正可以简化很多判断逻辑。内存耗尽处理极大数字时vector可能因内存不足而分配失败。在生产环境中需要考虑此类异常。封装一个Bigint类是一次对基础算法和细节处理能力的全面锻炼。它要求你不仅理解四则运算的原理还要在代码中妥善处理符号、进位、借位、试商、边界条件等无数细节。自己动手实现一遍你会对整数运算、数据结构、C语言特性有更深的理解。虽然在实际开发中我们更多会使用像GMPGNU Multiple Precision Arithmetic Library这样久经考验的库但“造轮子”的过程本身就是通往资深开发者道路上最宝贵的经验。当你下次再遇到整数溢出警告时你脑海中浮现的将不再仅仅是long long而是一整套应对“无限”的解决方案。