高精度算法1：高精度加法

一、高精度算法

在算法题目中难免会出现一些特别大的数字来进行计算，那么如果他们的范围超出了 long long我们该如何进行计算呢？于是就要使用高精度算法了。接下来就介绍一下高精度算法的几个主要部分——加减乘除四则运算。

对于高精度算法，他应对的是位数​<=10^6的情况，这个数据范围其实非常大了，因此就需要使用高精度算法来做。不过要注意的是，在本章当中，高精度乘法和除法对应的都是一个大数乘或除以一个常规 int或 long long范围内的数，两个大数相互乘除的算法应用较少，就不再介绍了。

二、高精度加法

高精度加法和减法应该是高精度算法中最简单的两个内容了，对于两个长度​≤10^6的庞大数字，使用普通的加法肯定是不能做到的，因为已经超过了 int和 long long范围了。所以我们可以回归加法的本质，也就是小学列竖式来计算加法。如下图：

我们注意到，在竖式计算时，我们对齐两个数的最低位进行逐位相加，构成结果的一位。这个就是高精度加法的核心本质。那么如何处理进位呢？在代码中，我们只需要将两个位相加的结果取余​10得到的数放到新数组中，对于剩余的数字，直接除以​10得到十位，下一次直接累加上就可以解决了。有些同学可能会担心​t>20的情况，其实这种情况是不存在的，因为我们每一位都是一个个位数，所以相加一定会小于​20，所以每一位的进位也一定是​0或​1，所以最大也就是​19，仍然不会超过​20。

那么要注意的是，如果最后一位进位了，那么我们就需要多一位，但是如果数组是正向存储的话，就需要移动整个数字来实现在前面插入一个数的操作，非常麻烦。所以为了便于进位和计算，我们需要将数字倒序存储在数组中。具体代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 1e6 + 10;

vector<int> add(vector<int> &A, vector<int> &B){
    vector<int> C;
    int t = 0;
    for(int i = 0; i < A.size() || i < B.size(); i++){
        if(i < A.size()) t += A[i];
        if(i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if(t) C.push_back(1);
    return C;
}

int main(){
    string a, b;
    vector<int> A, B;
    cin >> a >> b;
    for(int i = a.size() - 1; i >= 0; i--){
        A.push_back(a[i] - '0');
    }
    for(int i = b.size() - 1; i >= 0; i--){
        B.push_back(b[i] - '0');
    }
  
    auto C = add(A, B);
  
    for(int i = C.size() - 1; i >= 0; i--){
        cout << C[i];
    }
    return 0;
}