SolitudeAlma

简单介绍一下高精度加法（高精度加高精度或低精度都可以用）

什么是高精度加法呢？🤣🤣🤣

简单点说就是当我们计算的时候，如果数据过大，那么我们使用的数据类型可能存不下，比如 int 的范围是 $-2^{31} $ ~ $2^{31}-1$ （中间有个0），那么你存的数的位数不能超过9位数，但是很多时候数据都会很大，有些人会说，那我用 long 也行啊，我只能说有时候你用 unsigned long long 都不够，可见数据位数之长。

详情可以看看这个高精度算法😘😘😘

这里我们只解决高精度整数加法，一般也不考浮点数吧，emmm😜😜😜

那这种数据我们应该怎么处理呢？很简单。既然存不下，那我们就用字符串（字符数组也行，C++特有的数据类型string，其实也等价于字符数组，只不过更方便使用）读入，然后将其每一位存入数组中即可，只要我们的数组够大，就能完成我们的计算（不TLE的前提，既然题目明确要用这种方法就不会让你超时）。

但是对于加法我们都知道的一点，也是最重要的一点。那就是十进制数是满十进一，因为我们是用数组去存数的每一位，所以在计算的时候我们应该倒序存数的每一位，即数组的第一位存的不是最高位而是最低位，这样在我们进位的时候会更加方便（最高位可能也要进位，而这时数组第0位已经有数了，再放就越界了，得把数组中的数往后移，这样就会特别麻烦）。

那么我们先看看模板是怎样的👇👇👇

不知道vector的小伙伴可以看看这个vector介绍

向量（Vector）是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。


vector<int> add(vector<int> &A , vector<int> &B)
{
    
    if(A.size() < B.size()) return add(B , A);//如果被加数长度小于加数那么就调整顺序，如果不加这一句就需要变动一下for循环，i多判断一次是否小于B的大小（即算完最长的数的位数才停），然后 t += A[i] 用 if(i < A.size())包裹
    vector<int> C;// 定义一个答案
    int t = 0; // 存储进位
    for(int i = 0; i < A.size(); ++ i)
    {
        t += A[i];
        if(i < B.size()) t += B[i]; //如果B还没加完就继续
        C.push_back(t % 10); // mod 10 的结果就是对应位的结果 push_back 是往数组后面插入一个数
        t /= 10; //整除10表示进位是多少
    }
    
    if(t) C.push_back(c); // t为0，表示最高位无进位，大于0表示有进位。也可以写入for循环，自行思考

    return C;
}

这个模板并不难理解，输出答案的时候记得倒序输出就是了。

我们直接上模板题👇👇👇

AcWing 791. 高精度加法

题目描述

给定两个正整数，计算它们的和。

输入格式

共两行，每行包含一个整数。

输出格式

共一行，包含所求的和。

数据范围

$1≤整数长度≤100000$

输入样例：

12
23

输出样例：

C++ 代码

#include <iostream>
#include <vector>

using namespace std;

vector<int> A , B;
string a , b;

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

int main()
{
    cin >> a  >> b;
    
    // a[i] - '0' 是通过ACII码的差值计算该字符转为数字时的大小
    for(int i = a.size() - 1; i >= 0; -- i) A.push_back(a[i] - '0');
    for(int j = b.size() - 1; j >= 0; -- j) B.push_back(b[j] - '0');
    
    // auto是C++11的新特性，编译器会自动识别变量的类型，相当方便，如果不可以用，那就用标识符定义吧
    auto C = add(A , B);
    
    for(int k = C.size() - 1; k >= 0; -- k) cout << C[k];
    
    return 0;
}

引用

有大佬用数组写了一遍，可以参考，记得去前导零，因为开数组的时候都是比数据范围大，（emmm，其实也可以不用，不过写成函数的话可以搞个计数器，记录位数，然后输出2333，灵活运用吧），orz

Java的小伙伴也可以学一下，貌似有些题目不能用Big Integer，毕竟算法这个东西学到一点是一点，不能因为语言特性而不去学

还有一点就是用数组貌似比STL快了一倍，不过这时差可以忽略不计，但是比如链表的操作这些用数组作为静态链表去模拟的话速度会快很多，而且写法也简单，特别是数据很大的时候，用数组往往是很好的选择，当然这也是后话了

对于压位感兴趣的小伙伴也可以试试，引用的题解中有，但是一般应该用不上

lyclyc_NSP AcWing 791. 高精度加法C++数组实现

小呆呆 AcWing 791. 高精度加法

二月 AcWing 791. 高精度加法（使用string，30行） c++

就是个渣渣 AcWing 791. 高精度加法

高精度加法的介绍以及模板的分享