高精度算法复习笔记

帅树

2026-09-13 21:10:56

发布于：广东

10阅读

0回复

0点赞

大数加法

知识点小结

1. 为什么要用大数加法？
C++ 里的 int 最大只能存约 21 亿（10 位数），long long 最大也只能存约 9×10¹⁸（19 位数）。
如果两个数字有 100 位、500 位甚至更多，普通变量根本装不下！
这时候就要用字符串来存储大数，然后一位一位地模拟竖式加法。

2. 核心思路：模拟手算竖式加法
从个位开始，逐位相加，满十进一。
唯一的区别是：我们把每一位数字存在字符串里，而不是脑子里。

3. 关键知识点

知识点	作用	用法
`string` 字符串	存储超大数字	用 `cin >> s` 读入，每个字符代表一位数字
`reverse()` 反转	让个位对齐到下标 0	`reverse(s.begin(), s.end())`，方便从低位开始遍历
字符转数字	把字符 `'5'` 变成数字 `5`	用 `s[i] - '0'`，因为字符 `'0'` 的 ASCII 码是 48，`'5'` 是 53，53-48=5
数字转字符	把数字 `5` 变回字符 `'5'`	用 `数字 + '0'`，反过来操作即可
`% 10` 和 `/ 10`	处理进位	`sum % 10` 取个位作为当前位结果，`sum / 10` 取进位值

步骤分析
第一步：用字符串读入两个大数
因为数字太大，int 和 long long 都存不下，所以用 string 来接收。

第二步：反转两个字符串
竖式加法是从个位开始算的，但字符串第 0 位是最高位。
反转后，第 0 位变成个位，第 1 位变成十位……这样用同一个循环变量 i 就能同时遍历两个数。

第三步：逐位相加，处理进位
从下标 0 开始，把两个字符串对应位置的数字取出来相加。
如果某个字符串已经遍历完了（比较短），就补 0。
每次相加还要加上上一轮的进位值。
sum % 10 得到当前位的结果，sum / 10 得到新的进位。

第四步：处理最高位的进位
循环结束后，如果进位值还不为 0（比如 999+1=1000），要把这个进位也加到结果里。

第五步：反转结果并输出
因为结果是从个位开始拼的，所以最后要反转回来，才能得到正确的数字顺序。

完整代码展示

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

int main() {
    string a, b;
    cin >> a >> b;

    // 反转字符串，让个位对齐下标0，方便从低位开始算
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    string result;
    int carry = 0;  // 进位，用普通int变量，清晰明了
    int i = 0;

    // 只要还有数字没处理完，或者还有进位，就继续
    while (i < a.size() || i < b.size() || carry) {
        int sum = carry;  // 先把上一轮的进位加上
        if (i < a.size()) sum += a[i] - '0';  // 字符转数字
        if (i < b.size()) sum += b[i] - '0';
        carry = sum / 10;           // 算出新的进位
        result += (char)(sum % 10 + '0');  // 数字转字符，拼到结果里
        i++;
    }

    // 结果现在是倒着的（低位在前），反转回来就是正确答案
    reverse(result.begin(), result.end());
    cout << result << endl;
    return 0;
}

逐行代码说明

#include <bits/stdc++.h>    // 引入工具箱，包含各种有用的功能
using namespace std;        // 使用标准命名空间

int main() {
    string a, b;            // 创建两个字符串，用来存储两个大数
    cin >> a >> b;          // 输入两个大数（以字符串形式读入）

    // 反转字符串：让个位对齐到下标0，方便从低位开始计算
    reverse(a.begin(), a.end());   // 反转字符串a
    reverse(b.begin(), b.end());   // 反转字符串b

    string result;          // 创建结果字符串，用来存储答案
    int carry = 0;          // 进位值，初始为0（还没有进位）
    int i = 0;              // 循环变量，从第0位（个位）开始

    // 只要还有数字没处理完，或者还有进位，就继续循环
    while (i < a.size() || i < b.size() || carry) {
        int sum = carry;    // 先把上一轮的进位加到sum里

        // 如果a还有数字没处理完，就取出第i位并转成数字
        if (i < a.size()) sum += a[i] - '0';

        // 如果b还有数字没处理完，就取出第i位并转成数字
        if (i < b.size()) sum += b[i] - '0';

        carry = sum / 10;   // 算出新的进位（比如15/10=1）
        
        // sum % 10 取个位作为当前位结果，+ '0' 转成字符，拼到结果后面
        result += (char)(sum % 10 + '0');
        
        i++;                // 移动到下一位
    }

    // 结果现在是倒着的（低位在前），反转回来就是正确答案
    reverse(result.begin(), result.end());

    // 输出最终结果
    cout << result << endl;

    return 0;               // 程序结束
}