高精度加法

一句话算法

高精度加法就是把小学竖式加法搬到代码里：从最低位开始逐位相加，带着进位往前走。

问题模型

给定两个很大的非负整数。它们可能超过 long long 的范围，不能直接用整数类型保存，需要用字符串或数组按位存储。

本文只讨论非负整数加法，不处理负数和小数。

核心直觉

十进制加法每一位只依赖三个量：

• 当前位 a[i]。
• 当前位 b[i]。
• 从低一位传来的进位 carry。

所以只要反向处理字符串，就可以像手算一样完成加法。

算法步骤

1. 把两个字符串反转，让最低位在前面。
2. 从低位到高位枚举每一位。
3. 计算 sum = x + y + carry。
4. 当前位写入 sum % 10。
5. 新进位为 sum / 10。
6. 最后如果还有进位，把它补到答案末尾。
7. 反转答案并输出。

算法证明

关键不变量： 处理完第 i 位后，答案的低 i+1 位已经等于真实和的低 i+1 位，carry 保存剩余高位需要加上的进位。

1. 第 0 位直接由两个个位和初始进位 0 得到，成立。
2. 假设低位已经正确，第 i 位只会受到当前两个数字和上一位进位影响。
3. sum % 10 正好是当前位，sum / 10 正好是传给下一位的进位。
4. 逐位推进后，每一位都正确，最后补上剩余进位即可。

复杂度分析

设两个数字长度最大为 $n$。

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n)$。

代码实现

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

        #include <bits/stdc++.h>
using namespace std;

string add_positive_integer(string a, string b) {
    if (a.size() < b.size()) swap(a, b);
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    int carry = 0;
    string ans;
    for (size_t i = 0; i < a.size(); ++i) {
        int x = a[i] - '0';
        int y = (i < b.size() ? b[i] - '0' : 0);
        int sum = x + y + carry;
        ans.push_back(char('0' + sum % 10));
        carry = sum / 10;
    }
    if (carry) ans.push_back(char('0' + carry));

    while (ans.size() > 1 && ans.back() == '0') ans.pop_back();
    reverse(ans.begin(), ans.end());
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string a, b;
    cin >> a >> b;
    cout << add_positive_integer(a, b) << '\n';
    return 0;
}
    

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

        # 非负十进制大整数加法：输入、输出都是不带正负号的数字字符串（负数不在支持范围内）。
# C++ 用 string 逐位模拟是因为 long long 会溢出；Python 的 int 本身任意精度，
# 保留字符串实现便于对照逐位过程，也便于移植到没有大整数的语言。


def add_positive_integer(a: str, b: str) -> str:
    """返回两个非负十进制数字串的和；结果去掉前导零，但至少保留一位（全零时为 "0"）。"""
    if len(a) < len(b):
        a, b = b, a
    a = a[::-1]
    b = b[::-1]

    carry = 0
    ans: list[str] = []
    for i in range(len(a)):
        x = int(a[i])
        y = int(b[i]) if i < len(b) else 0
        s = x + y + carry
        ans.append(str(s % 10))
        carry = s // 10
    if carry:
        ans.append(str(carry))

    # C++ 里进位最多 1、前导零最多来自输入本身；Python 逻辑一致。
    while len(ans) > 1 and ans[-1] == '0':
        ans.pop()
    return ''.join(reversed(ans))
    

测试用例

输入：

999999999999999999
1

输出：

1000000000000000000

应用分类详解

高精度加法的本质是“数值太大，改用按位存储和模拟运算”。

一、大整数运算入门

典型模式： 输入数字长度远超 64 位整数。 识别信号： 题面给出“数字长度不超过 10^5”而不是“数值不超过 10^18”。 核心建模： 用字符串保存每一位，按竖式规则模拟。

二、组合计数结果很大

典型模式： 递推结果增长很快，不能取模，要求输出完整答案。 识别信号： 题目要求“精确输出方案数”。 核心建模： DP 状态存高精度整数，转移时做高精度加法。

经典例题

1. luogu-P1601 高精度加法模板题，适合直接练习本文代码。

2. luogu-P2142 高精度减法，和加法一样都要从低位处理借位/进位。

3. luogu-P1005 高精度与动态规划结合，重点是状态值不能取模。

参考

• https://www.geeksforgeeks.org/bigint-big-integers-in-c-with-example/