高精度加法复习笔记

1.0 问题
1.1 思路
1.2 代码
1.3 时间复杂度分析
1.4 写在最后

1.0 问题

在我们熟悉的数据类型中，能够储存的最大的数也只是longlong的范围。

虽然有些编译器也提供__int128类型，但是最多也只能表示40位左右的数，大小依然有限，而且适用范围也很受限。

那么，又没有办法来模拟非常长的整数呢？

1.1 思路

既然变量不能储存大数，我们可以尝试使用数组来储存一个数。

用数组的每一位来储存那个数字上的一位，也就是说，用一个长度为n的数组记录一个n位数字。

那么，问题又来了，我们如何进行加法运算呢

首先，回顾一下小学学习的竖式计算：

  1 9 1
+ 9 8 1
--------
1 1 7 2

可以看到，用竖式计算时，为了保证进位正确，是从低位向高位运算的

我们可以模拟这个运算方法：

方便读入，使用string直接读入大数
将string类型的数转换为数字，并为了进位方便，倒叙存储在数组内
将两个数加起来
把两数的和对10取整，即进位。
- 例如
  - 两数的和为9，对10取整为0，即进位为0;
  - 两数的和为19，对10取整为1，即进1位、
处理完进位后，把两数的和对10取余，留下个位。
- 例如
  - 和为9，对10取余，留下个位为9
  - 和为19，对10取余，留下个位为9
最后将数组倒叙输出即可。

1.2 代码

根据上面的描述，可以得到如下代码：

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;
const int MAXn = 2333;
int num1[MAXn], num2[MAXn], sum[MAXn];
int len1, len2;

int main(){

    //读入
    string str1, str2;
    cin >> str1 >> str2;
    //转换
    len1 = str1.length();
    len2 = str2.length();
    //从 len - 1 开始到0遍历数组，减去1是因为数组下标从0开始，方便操作
    for(int i = len1 - 1; i >= 0; i--){
        //倒叙存储         把字符转换为数字
        num1[len1 - i] = str1[i] - '0';
    }
    for(int i = len2 - 1; i >= 0; i--){
        num2[len2 - i] = str2[i] - '0';
    }

    //进行加运算
    int len = max(len1, len2);
    for(int i = 0; i <= len; i++){
        //此处使用“+=” 是因为可能有进位
        sum[i] += num1[i] + num2[i];
        //处理进位  直接把进的为赋值给sum[i - 1]
        sum[i + 1] = sum[i] / 10;
        //保留个位
        sum[i] %= 10;
    }

    //输出
    //进位有可能导致位数增加1
    if(sum[len + 1]){
        len++;
    }
    //倒叙输出
    for(int i = len; i >0; i--){
        cout << sum[i];
    }

    return 0;
}