高精度算法-加法（附完整源码）

前言：基础的加法，类似a+b都很熟悉，但是整型之间的加法是存在范围限制的，比如int类型的范围是【-2³¹，+2³¹-1】，即使是long long类型也有着【-2⁶³，+2⁶³-1】的范围，一旦超过这个范围，计算机无法准确给出答案。计算这类问题就是高精度算法的意义

0.整型转字符（准备工作）

数组中可以储存许多数字，并且没有限制，比如1亿只需要向数组中储存9位数字，所以我们高精度算法的核心就是将超出长整型范围的数字分成个，十，百......分别作为元素储存在数组当中。

#include <iostream>
using namespace std;
string s1,s2;//储存高精度加法两个数字的字符串数组
int a[101],b[101],c[101];//这里马上讲到

1.个位对齐-反转,字符转整型

这里是一个小难点，我举个小例子
假如是s1="123" ,s2="34"

先不论字符串能不能直接加（一会儿会转化为整型的），我们看到这个计算方式错的很低级，但是我们就是用字符串对应位相加，然后拼在一起。所以出现这个问题，也就是同一位（即个位和个位，十位和十位）没有对齐，为了方便解决这个问题，我们将字符串中数字反转，呈现下图的样子

其实这基本上就是这种题目的完整思路了，不过后面要完善一下细节，我们接下来写一下反转的代码

void strtoint(string src,int des[]){//这里用到上面的a[101],b[101],c[101],作为参数传进来。
    for (int i = 0; i < src.size(); ++i) {
        des[src.size()-i]=src[i]-'0';//这一步是转换为整型。我们这里des数组初始就不从0开始了，从1开始，为了后面方便计算。
    }
}

2.计算c数组长度

这个比较好理解，两数相加得到的数字位数要不然等于位数大的，要不然进一位成位数大的加一位，自己举几个例子看看就行，123+34=157,990+11=1001，不外乎这两个情况，直接上代码

cin>>s1>>s2;
strtoint(s1,a);
strtoint(s2,b);
int la=s1.size(),lb=s2.size();
int lc=max(la,lb)+1;

3.对位相加得出c数组

for (int i = 1; i <=lc ; ++i) {
        c[i]=a[i]+b[i]+c[i];
        c[i+1]=c[i]/10;
        c[i]=c[i]%10;
    }

代码已上，详细解释下

4.去除前导0

我们是倒序输出c数组元素的，直接输出会出现一些问题，比如

因为之前的操作，c数组长度可能多一位，倒着会输出未赋值的元素即0，因此要消除这个前导0，同时因为第二种情况的出现，我们需要多次消除这个0，直到非零元素或只剩一个0元素。

while (c[lc]==0&&lc>1) lc--;

这就是完整思路了，写这么一篇好累啊，最后附上完整代码

#include <iostream>
using namespace std;
string s1,s2;
int a[101],b[101],c[101];
void strtoint(string src,int des[]){
    for (int i = 0; i < src.size(); ++i) {
        des[src.size()-i]=src[i]-'0';
    }
}
int main(){
    cin>>s1>>s2;
    strtoint(s1,a);
    strtoint(s2,b);
    int la=s1.size(),lb=s2.size();
    int lc=max(la,lb)+1;
    for (int i = 1; i <=lc ; ++i) {
        c[i]=a[i]+b[i]+c[i];
        c[i+1]=c[i]/10;
        c[i]=c[i]%10;
    }
    while (c[lc]==0&&lc>1) lc--;
    for (int i = lc; i >=1 ; --i) {
        cout<<c[i];
    }
    return 0;
}