c++中如何实现大数加法_c++字符串模拟高精度加法算法【实例】

不能直接用int或long long做大数加法,因为其位数上限分别为10位和约19位,超限会溢出;必须用字符串模拟竖式加法,从右往左逐位计算并处理进位,最后反转结果。

c++中如何实现大数加法_c++字符串模拟高精度加法算法【实例】

为什么不能直接用 intlong long 做大数加法

因为 C++ 内置整型有上限:int 通常最多表示 10 位十进制数,long long 最多约 19 位。一旦输入像 "123456789012345678901234567890" 这样的字符串,就必然溢出。所以必须用字符串存数字,逐位模拟小学竖式加法。

字符串从右往左逐位相加的核心逻辑

关键在于对齐末位、处理进位、反向拼接结果。不能从左往右加,否则进位会破坏已计算位。

  • 把两个字符串 ab 视为“低位在右”,用索引从后往前遍历(i = a.size()-1, j = b.size()-1
  • 每次取当前位数字:a[i] - '0',注意字符转数字要减 '0'
  • 维护一个 carry 变量记录进位(初始为 0),当前和为 digit_a + digit_b + carry
  • 当前位结果是 sum % 10,新进位是 sum / 10
  • 把每位结果 push_back 到临时 string res,最后调用 reverse(res.begin(), res.end())

完整可运行的高精度加法函数示例

string addStrings(string a, string b) {
    string res;
    int i = a.size() - 1, j = b.size() - 1;
    int carry = 0;
    while (i >= 0 || j >= 0 || carry) {
        int digit_a = (i >= 0) ? a[i--] - '0' : 0;
        int digit_b = (j >= 0) ? b[j--] - '0' : 0;
        int sum = digit_a + digit_b + carry;
        res.push_back('0' + (sum % 10));
        carry = sum / 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

这个函数能正确处理:不同长度(如 "99" + "1")、全零、空串(需额外判空,但题目通常保证非空)、以及最大进位(如多个 "9" 相加)。

容易被忽略的边界细节

实际写题或工程中,这几个点常导致 WA 或崩溃:

PixVerse

PixVerse

PixVerse是一款强大的AI视频生成工具,可以轻松地将多种输入转化为令人惊叹的视频。

下载

立即学习C++免费学习笔记(深入)”;

  • 没处理 ij 负值时的越界访问——必须用 (i >= 0) ? ... : 0 形式,不能直接写 a[i]
  • 忘记循环条件中的 || carry,导致最高位进位丢失(例如 "5" + "5" 输出 "0" 而不是 "10"
  • 结果字符串未反转,输出是倒序的
  • 输入含前导空格或负号?本算法只适用于非负整数字符串;若要支持负数,得先解析符号、再分情况调用加/减逻辑

真正难的不是写对一次,而是让代码在所有边界输入下稳定输出——比如 "0" + "0""0001" + "2",这些看似简单的情况反而最易暴露逻辑漏洞。

https://www.php.cn/faq/1991880.html

发表回复

Your email address will not be published. Required fields are marked *