c++算法—— 难道算个a+b还要算法？幽默讲解高精度算法（加法）从小白到精通

小汉堡编程

1100人浏览 · 2025-08-08 21:25:51

小汉堡编程 · 2025-08-08 21:25:51 发布

hi我是小汉堡，今天我们讲解高精度加法和高精度减法，啊，我似乎觉得今天要讲的内容很多，很简单，为啥？请看高精度算法的介绍，也就是下面。

文章目录

高精度算法的作用——小白都能看懂的讲解

啥是高精度算法？在我们了解这个算法之前，我先给大家出道题！

题目描述：
给你两个正整数 $a$ 和 $b$ ，求 $a + b$ 的结果
数据范围：
$a\le 10^{18}$
$b\le 10^{18}$

读完这道题的你直接打开计算机，写起了代码，不到一分钟写出了下面这段代码

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

int main(){
	int a,b;
	cin>>a>>b;
	cout<<a+b;
	return 0;
}

而且你满怀自信的说：“一遍满分，你也太瞧不起我了吧！我学编程第一天就会了！”，并点下了提交，结果出现了下面的结果
在这里插入图片描述
半江瑟瑟（AC，绿）半江红（WA，红），一半对了，一半没对。你下载了错误的测试数据，发现数据中的数很大，于是你写出来下面代码

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

int main(){
	long long a,b;
	cin>>a>>b;
	cout<<a+b;
	return 0；

但是还是半江瑟瑟半江红，你这时一脸懵：“嗯？是不是测评机坏了？”。
事实证明测聘机没坏，而是你写错了。
仔细读读题目的数据范围吧！

$a\le 10^{18}$
$b\le 10^{18}$

$10^{18}=10000000000000000000$
这是一个 $20$ 位数，而 $in t$ 类型只能存下10位数，而long long类型能存二十位，但是两个数相加，说不定就超过了二十位。存不下这个数字，自然就无法计算
如果你计算这样的数，以你写的代码会出现这样的结果
在这里插入图片描述
输入了两个大正整数，但是却输出了一个负数，这说明变量溢出了
这时候，你就没有方法AC这道问题了。
于是，有人发明了一个……（你抢着回答：“新的类型，能存下好大的数”，我：“想的美！”）有人发明了一个算法，高精度算法，专门用来计算超大数字，连long long 都无法存下的的数的计算（当然小一点的数，比如1+1它也能算）。

高精度加法的原理——其实只是加法竖式而已

我们刚刚了解了高精度算法的作用，但是高精度加法如何实现呢（我们今天先讲高精度加法，减法、乘法、除法以后讲）？说起这个，就先说一说小学一年级就学的加法竖式吧！（额~或许在幼儿园就学了），我们再复习一下，讲一讲加法竖式如何程序化。
话说发明高精度算法的人，就是想起了自己学过的加法竖式，就用加法竖式发明了高精度加法（减法，乘法，除法也是竖式），说的明白一点，高精度加法其实就是让计算机算加法竖式，而小一点的数直接用运算符算加法就是加法横式。

我们的竖式是这样的：

列出两个要计算数字，一样的数位对齐，比如：两个数的个位和个位对齐，百位和百位对齐， $321$ 和 $54$ 两个数，4对应1，5对应2，3啥也不对应，如图
从个位开始一位一位相加，如果和为两位数，就把十位上的数字记为进位，在下一次相加时加上这个数字，注意是把这个数字的单位当“个”，而不是“十”
最后得到结果

我说的多了，竖式大家都会

但是为啥我们需要算竖式呢？难道算竖式就不会溢出变量吗？答案是不会的，我们仔细分析一下，竖式是一位一位的算的，而一位一位的算每一位的数，最多加到 $18$ ，不可能超过int类型。但是细心的同学会问：“即使算的时候没有超过int或者long long类型，但是把 $a$ 和 $b$ 输入进来了话”用字符串，字符串可以很长哦！

而让计算机写竖式，也就是写竖式计算的代码，就需要注意一些重要的点

竖式是从个位算起的，而我们输入的两个数则是正着输入的，第一位是最高位，所以应该倒着读数组，或者应该把数组倒过来。
我们从个位开始计算，每一位计算时都有可能产生进位，所以每一次我们都要记住这个位上的进位，哪怕是 $0$ 。
但是，竖式还有一个细节，就是算到最后一位数是，也就是算到最高的那一位很有可能算出两位数，也就是应往下一位进位，但是后面没有位数了，所以应该在高位加一个进位的数。
（说的了没用，看代码吧）

代码——逻辑展现的地方

#include<bits/stdc++.h>
using namespace std;
vector<int> a,b;

vector<int> jf(long long n,long long m){
    vector<int> c;
    int t=0;
    for(int i=0;i<max(n,m);i++){
        if(i<n&&i<m){
            c.push_back((a[i]+b[i]+t)%10);
            t=(a[i]+b[i]+t)/10;
        }else if(i<n&&i>=m){
            c.push_back((a[i]+t)%10);
            t=(a[i]+t)/10;
        }else if(i>=n&&i<m){
            c.push_back((b[i]+t)%10);
            t=(b[i]+t)/10;
        }
    }
    if(t==1) c.push_back(1);
    return c;
}

int main(){
    string x,y;
    cin>>x>>y;
    for(int i=x.length()-1;i>=0;i--)
        a.push_back(x[i]-'0');
    for(int i=y.length()-1;i>=0;i--)
        b.push_back(y[i]-'0');
    vector<int> c=jf(a.size(),b.size());
    for(int i=c.size()-1;i>=0;i--){
        cout<<c[i];
    }
    return 0;
}

代码详解

先看主函数（这是一个好习惯哦！）
第25~26行：定义了两个字符串，用来存入输入的两个数，因为两个数可能很大，所以用字符串装他们，不过存入的是字符的形式。为啥存成字符串就不会溢出呢？因为字符串一个数字只需一字节，理论上是无限存储，除非太大连电脑硬盘都装不下。
第27~30行：我们前边说过，要把数倒着存储，或者倒着读取数，我这里选择了倒着存储，顺便我改了存储类型，改成了数组，也就是说把两个字符串的每一位都存在了数组里的每一位，而我们的字符串应该倒着读，数组正着存，这里我用了vector数组。
第31行：我把高精度的计算内容写在了函数里，函数返回的是vector数组类型是算过后的答案，不能用整数类型哦，算完的数肯定超大，整型装不下。我用数组 $c$ 接受函数返回的结果。再看函数的调用：函数叫 $j f$ ，括号里传入函数传入了两个数组的长度，也就是说是两个数的位数。那么，为啥不用传输 $a, b$ 两个数组呢？因为他们是全局变量不需要传输。
接下来我们看函数
第8行：一个循环，循环 $a$ 数组和 $b$ 数组，从 $0$ 开始，循环到他们的长度 $- 1$ ，但是，看代码，为啥是他们的长度的最大值呢？因为会有一种情况，我们两个数的位数不同，一个位数长，一个位数短，我们一位一位算数，算到一个较短的位数时，还没有算完，不可能停吧！所以应该案位数长的那个来。 $i$ 每次自增 $1$ 。
第9~18行：算数分为3种情况：目前执行到的位数都有数；
在这里插入图片描述
第一个有第二个没有；

第二个有第一个没有

每一种情况都是把数和进位相加，存进数组，记上进位。
第20行：这一行就是我说的