一、前言

时隔多日，算法笔记终于又开始恢复更新了。今天 a n d u i n anduin anduin 为大家带来的是 高精度算法 。

高精度算法是解决大数运算的一把利器。虽然这个名字听起来挺高大上的，但是高精度算法的原理其实并不难，就和我们平时算计算题一样。所以学习起来还是十分愉快的。

高精度算法分为四大类，高精度加法，高精度减法，高精度乘法，高精度除法。它们各自有各自的优点。而今天，我们就来学习这四种算法。

二、高精度加法

1、思想及模板

高精度加法说白了就是两个大数之间相加，数字长度不超过 1 0 6 10^{6} 106 。注意这里是长度，而不是数据大小哦！

但是这种数字如果放到变量中肯定是存不下的，所以我们一般用数组来存储，在 C++ 中一般用 vector 容器。

如果存入数组中，就需要考虑存储顺序，究竟应该正着存还是倒着存。

实际上，我们这边 倒着存 是很合适的，因为对于数组来说，给一个数的后面一个数加 1 1 1 很简单，但是在一个数的前面加上 1 1 1 就很麻烦。

就比如这张图：

如果我们 倒着存 那么 a[0] + b[0] = 11 ，是需要进位的。如果倒着存就可以 很快的进行进位 ，直接在下标 1 1 1 处进行自增即可；但是如果正着存，那么进位就需要到 − 1 -1 −1 下标了，这样就不麻烦，我们算法就是为了更快解决问题，所以自然选择最合适的方式：倒着存 。

而高精度加法运算其实就像我们小学列 竖式 一样：

   从最低位开始计算，如果两个数相加超过 10 10 10 ，就需要进位。竖式我就不带着大家列了，相信以小伙伴的脑袋瓜很容易想明白。

我这边就讲一下思想：

假如数组 a a a 和 b b b 分别用来存数据， c c c 用来存储答案。

通过循环同时遍历 a a a 、 b b b 数组，在遍历的同时，使用 t t t 来判断是否进位。将 a[i] + b[i] 的数据累加到 t t t 中。

数据相加有两种结果：

   如果 a[i] + b[i] < 10 ，直接将 t 放入 c c c ，让 t /= 10 ，以便下一次计算。

   如果 a[i] + b[i] = 10 ，将 t % 10 = 0 放入 c c c ，让 t /= 10 。

   如果 a[i] + b[i] > 10 ，将 t % 10 放入 c c c 数组，将 t /= 10 作为 进位 ，下一次 t t t 初始就是 1 1 1 。

就拿这张图理解：

这里就是对最后一位进行运算时，所做的进位操作。

而 t % 10 t \% 10 t%10 最终的结果肯定在 0 ∼ 9 0 \sim 9 0∼9 之间，如果 t < 10 t < 10 t<10 小，那么 % 10 \%10 %10 不会对运算结果产生影响；对于 t > 10 t > 10 t>10的情况，则会将结果控制到 0 ∼ 9 0 \sim 9 0∼9 之间。

这种做法就像是计算机在模拟我们日常的操作，所以高精度加法在力扣上有一题被归为 模拟算法 的范畴：415. 字符串相加 。就比如这道题目，就是经典的高精度加法。

模板 ：

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;
}

简单讲一下模板在干什么：

a a a 和 b b b 是倒着存的，并同步遍历，由于数据大小不确定，所以只要 a a a 和 b b b 有一个符合条件，则就可以被 t t t 累加，符合条件的就加上该位置的元素，否则就不处理，默认为 0 0 0 。

每次将 t % 10 t \% 10 t%10 尾插到结果数组 c c c 中，然后将 t / 10 t / 10 t/10 ，以便下次运算，如果有进位，那么下次 t t t 的初值就为 1 1 1 。

最后循环结束后，再判断一下是否还有进位没进，如果有进位，则将 1 1 1 尾插到 c c c 中。

2、代码实现

链接：791. 高精度加法

描述：

给定两个正整数（不含前导 0 0 0），计算它们的和。

输入格式：

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

输出格式：

共一行，包含所求的和。

数据范围：

1 ≤ 1 ≤ 1≤ 整数长度 ≤ 100000 ≤100000 ≤100000

输入样例：

12
23

输出样例：

35

思路 ：

思路我们基本已经讲完了，在经过模板中的处理后，将数据倒着打印出来即可。

三、高精度减法

1、思路及模板

高精度减法是对大整数的减法，数据长度不超过 1 0 6 10^{6} 106 。

我们讲解的 高精度减法是基于对正整数的算法 ，如果计算的是负数，那么需要微调。

高精度减法使用的存储方式为 倒序存储 。还是和我们的竖式计算十分相似。

假设我们现在还是两个数组： a , b a, b a,b ，当 a [ i ] − b [ i ] < 0 a[i] - b[i] < 0 a[i]−b[i]<0 时，则需要 借位 ；如果 a [ i ] − b [ i ] > = 0 a[i] - b[i] >= 0 a[i]−b[i]>=0 ，则无需处理。

就比如这幅图就是 a [ i ] − b [ i ] < 0 a[i] - b[i] < 0 a[i]−b[i]<0 的一个经典样例：

如果 a [ i ] − b [ i ] < 0 a[i] - b[i] < 0 a[i]−b[i]<0 ，则说明需要借位，就是 + 10 +10 +10 ，为了防止 + 10 +10 +10 后超过 10 10 10 而放不进数组，所以需要 % 10 \% 10 %10 。然后判断 t t t本身是否小于 0 0 0 ，将借位更新一下： t = − 1 t = -1 t=−1 ，方便下一次计算。

如果 a [ i ] − b [ i ] ≥ 0 a[i] - b[i] \ge 0 a[i]−b[i]≥0 ，上面的方式也能完全适应，因为对于 0 ∼ 9 0 \sim 9 0∼9 的正数来说先 + 10 +10 +10 再 % 10 \% 10 %10 是不变的，所以方法完全适配。在这种情况下 t ≥ 0 t \ge 0 t≥0 ，所以无需进位 t = 0 t = 0 t=0 。

但是在进行高精度减法之前，我们需要知道两个数的大小：

   若 a < b a < b a<b ，则 a − b a - b a−b 结果为负数

   若 a ≥ b a \ge b a≥b ，则 a − b a - b a−b 结果为整数或 0 0 0

所以我们需要预处理比较两个数的大小，如果 a < b a < b a<b 的话，相减的结果就为负数，所以就需要交换它们的值，因为它俩相减结果就相当于 − ( b − a ) -(b - a) −(b−a) ，这时只需要先输出负号，然后正常倒序输出即可。

再来看看模板：

// 比较 a 和 b 的大小
bool cmp(vector<int> &A, vector<int> &B)
{
    // 如果 A 的位数小于或等于 B 的位数
    if (A.size() != B.size()) {
        return A.size() > B.size();
    }
    // A 的位数大于 B 的位数
    for (int i = A.size() - 1; i >= 0; i--) {
        if (A[i] != B[i]) {
            return A[i] > B[i];
        }
    }
    // 此时 A == B
    return true;
}
vector<int> Sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i++) {
        t += A[i];
        if (i < B.size()) {
            t -= B[i];
        }
        // 相减结果可能为负数 % 10 可以得到 0~9 的位数
        // 此时是需要借位的
        C.push_back((t + 10) % 10);
        // 如果 t < 0 说明要借位
        if (t < 0) {
            t = -1;
        } else {
            t = 0;
        }
    }
    while (C.size() > 1 && C.back() == 0) {
        C.pop_back();
    }
    return C;
}

这段模板里的大部分我们都讲过了，下面讲一下这块是什么意思：

while (C.size() > 1 && C.back() == 0) {
        C.pop_back();
}

由于我们的数据时是倒着存放的，而两个数相减结果为 0 0 0 ，就会在该位填上 0 0 0 。

比如 666 ∼ 665 666 \sim 665 666∼665 倒着存储并在经过上方的高精度运算后， c c c 中结果为 100 100 100 ，所以这种情况就需要去前导 0 0 0 。

上面的操作就是检查长度是否至少为 1 1 1 ，且 c c c 尾部是否为 0 0 0 。

2、代码实现

链接 ：792. 高精度减法

给定两个正整数（不含前导 0 0 0 ），计算它们的差，计算结果可能为负数。

输入格式：

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

输出格式：

共一行，包含所求的差。

数据范围：

1 ≤ 整数长度 ≤ 1 0 5 1≤整数长度≤10_{5} 1≤整数长度≤105

输入样例：

32
11

输出样例：

21

思路我们都讲过了，接下来就直接上代码，注意点都在注释里：