当前位置：首页 > news >正文

用C++的string类手搓一个大整数加法器（附完整可运行代码）

news 2026/6/17 17:02:50

用C++的string类手搓一个大整数加法器（附完整可运行代码）

在C++编程中，处理超大整数一直是个有趣且实用的挑战。标准库中的整数类型如int或long long都有其数值范围限制，当我们需要处理像银行账户余额、加密算法中的大数或者科学计算中的精确数值时，这些原生类型就显得力不从心了。本文将带你从零开始，利用C++的string类实现一个完整的大整数加法器，不仅能够处理任意长度的数字相加，还能兼容不同类型的输入。

1. 为什么需要大整数加法器？

现代计算机硬件对整数运算有明确的位数限制。以64位系统为例：

类型	位数	最大值
int	32	2,147,483,647
long long	64	9,223,372,036,854,775,807

当数字超过这些限制时，就会发生溢出错误。而使用字符串表示数字可以突破这个限制，因为：

字符串长度理论上只受内存限制
每个字符代表数字的一位
运算可以通过逐位处理实现

提示：大整数运算在密码学、金融系统和科学计算等领域有广泛应用，是计算机科学的基础课题之一。

2. 设计大整数类结构

我们将创建一个BigInteger类，核心设计如下：

class BigInteger { private: std::string value; // 存储数字的字符串表示 bool isNegative; // 标记是否为负数 public: // 构造函数 BigInteger(); BigInteger(int num); BigInteger(const std::string& str); // 运算符重载 BigInteger operator+(const BigInteger& other) const; // 友元输出运算符 friend std::ostream& operator<<(std::ostream& os, const BigInteger& num); };

关键设计考虑：

字符串存储：使用std::string存储数字，每位数字对应一个字符
前导零处理：统一在内部存储时不带前导零，简化运算逻辑
负数支持：虽然本文主要实现加法，但预留了负数支持接口
类型兼容：支持从整数和字符串构造大整数对象

3. 实现核心加法算法

加法的核心是模拟手工竖式计算，需要考虑以下几点：

位数对齐
进位处理
不同长度数字的处理

BigInteger BigInteger::operator+(const BigInteger& other) const { std::string result; int i = value.length() - 1; int j = other.value.length() - 1; int carry = 0; while (i >= 0 || j >= 0 || carry > 0) { int digit1 = (i >= 0) ? (value[i--] - '0') : 0; int digit2 = (j >= 0) ? (other.value[j--] - '0') : 0; int sum = digit1 + digit2 + carry; carry = sum / 10; result.push_back((sum % 10) + '0'); } std::reverse(result.begin(), result.end()); return BigInteger(result); }

算法步骤解析：

从字符串末尾（个位）开始处理
每次取对应位数字相加（不足位补零）
计算当前位结果和进位值
将结果字符存入字符串
最后反转字符串得到正确顺序

4. 完整实现与测试

以下是完整的可运行代码，包含构造函数和输出重载：

#include <iostream> #include <string> #include <algorithm> class BigInteger { private: std::string value; public: BigInteger() : value("0") {} BigInteger(int num) { if (num == 0) { value = "0"; return; } bool negative = num < 0; num = std::abs(num); while (num > 0) { value.push_back((num % 10) + '0'); num /= 10; } if (negative) { value.push_back('-'); } std::reverse(value.begin(), value.end()); if (value.empty()) value = "0"; } BigInteger(const std::string& str) { // 简单验证输入字符串 if (str.empty()) { value = "0"; return; } size_t start = 0; if (str[0] == '-') start = 1; // 跳过前导零 while (start < str.length() && str[start] == '0') { start++; } if (start == str.length()) { value = "0"; } else { value = str.substr(start); if (str[0] == '-') { value = "-" + value; } } } BigInteger operator+(const BigInteger& other) const { if (value[0] == '-' || other.value[0] == '-') { // 简化示例，暂不支持负数加法 throw std::runtime_error("Negative addition not implemented"); } std::string result; int i = value.length() - 1; int j = other.value.length() - 1; int carry = 0; while (i >= 0 || j >= 0 || carry > 0) { int digit1 = (i >= 0) ? (value[i--] - '0') : 0; int digit2 = (j >= 0) ? (other.value[j--] - '0') : 0; int sum = digit1 + digit2 + carry; carry = sum / 10; result.push_back((sum % 10) + '0'); } std::reverse(result.begin(), result.end()); return BigInteger(result); } friend std::ostream& operator<<(std::ostream& os, const BigInteger& num) { os << num.value; return os; } }; int main() { // 测试用例 BigInteger a("12345678901234567890"); BigInteger b("98765432109876543210"); BigInteger c = a + b; std::cout << a << " + " << b << " = " << c << std::endl; BigInteger d(999999999); BigInteger e(1); BigInteger f = d + e; std::cout << d << " + " << e << " = " << f << std::endl; return 0; }

5. 进阶优化方向

虽然我们的实现已经能够处理基本的大整数加法，但还有多个可以优化的方向：

性能优化：
- 预分配结果字符串空间
- 使用更高效的反转算法
- 实现移动语义减少拷贝

功能扩展：

// 减法实现示例 BigInteger operator-(const BigInteger& other) const; // 乘法实现思路 BigInteger operator*(const BigInteger& other) const { // 实现Karatsuba算法等高效乘法 }