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::vectorint是我们的不二之选。它动态管理内存我们无需手动处理数组的扩容问题可以专注于算法逻辑。std::string也是一个选择但进行数值运算时需要频繁进行字符与数字的转换不如vectorint直接。进制选择核心优化点这是影响性能和代码复杂度的关键决策。十进制每位存0-9最直观输入输出极其简单但效率最低。做乘法时两个n位数相乘需要O(n²)次单位乘法并且进位处理频繁。高进制如万进制每位存0-9999这是实践中更常用的方案。我们用int类型的每一个元素来存储0到9999之间的一个数。这样做的好处是大幅减少运算次数数字的“长度”容器大小缩短为原来的约1/4乘法复杂度从O(n²)降至O((n/4)²)理论上有16倍的提升。充分利用硬件int类型的加减乘除是CPU直接支持的单指令操作速度极快。减少进位频率由于每位容量大单次运算后产生进位的概率降低。当然高进制带来了输入输出转换的额外开销但综合来看在需要频繁运算的场景下其收益远大于代价。本系列将采用万进制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::vectorint 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_castunsigned 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、空字符串、仅符号如“-”等边界情况。这里的“在线转换”算法避免了使用中间的大数组内存效率更高但理解起来需要一点耐心。另一种更直观的方法是先用vectorint按顺序存储每一位十进制数然后再用一个循环将其合并成万进制代码更简单但需要额外的空间。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_castint(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_castint(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。 // 因为保证了*thisrhs所以最终borrow必定为0。 trim(); }减法就是加法的逆过程处理借位是关键。diff 0时说明不够减需要向高位借1即borrow1并在当前位加上基数BASE10000。核心技巧为什么要在加法和减法前保证*this rhs对于加法顺序不影响结果但我们的addAbs实现允许*this和rhs任意长度。对于减法这个保证至关重要。它确保了diff在减去rhs的位后即使为负也可以通过借位和BASE调整回来并且最终borrow会为0。如果我们不保证大小关系实现会复杂很多需要处理结果为负的情况而这可以通过交换操作数和设置符号位来规避。因此在实现完整的operator-时我们会先比较绝对值然后决定调用subAbs的顺序以及结果的符号。6. 带符号的加法与减法运算符现在我们可以利用上面的无符号运算来实现完整的、带符号的operator和operator-。加法的逻辑可以根据两个操作数的符号分为四种情况正 正绝对值相加结果为正。负 负绝对值相加结果为负。正 负转化为绝对值相减结果的符号由绝对值大的数决定。负 正同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第一部分的全部内容从设计思路、数据存储、构造、输出、比较到最基础的加减法。这个版本已经能够处理任意大小的整数加减运算。在下一部分我们将挑战更复杂的乘法和除法并着手进行性能优化。
