【基础算法】关于高精度计算的问题【很高位数数据的加减乘除(相关代码用C++实现)】

前言

• 当我们在利用计算机进行一些计算时，可能会遇到这类问题 ： 有些计算要求精度高，希望计算的数的位数可达几十位甚至几百位，虽然计算机的计算精度也算较高了，但因受到硬件的限制，往往达不到实际问题所要求的精度。
• 这时我们就可以通过程序设计来解决这类问题，例如：创建一个数组，通过数组来存放高精度数的每一位上的数。

---

1.高精度加法

• 高精度加法是两个位数很大的两个数相加，例如1234567898756432123456789 + 66666666666666666666666，这时候我们用平常的整型或者长整型去存放数据都是会溢出导致数据丢失的，所以此时我们可以用一个数组来存放每个数相对应位上的数（使用vector<int>， 假设这两个高精度数都大于0）。

• 不过在C++中，直接将数输入到vector中是不可取的，并且加法是从两个数的低位开始相加一直加到高位，如果我们正常输入从高位开始存放的话，对于后面程序的设计是不方便的，所以这里我们用string来表示相应高精度数，然后将这个string从低位开始转化成整数依次存放在vector<int>当中，这样两个vector<int>就是我们想要的高精度数了。

• 同时我们需要另一个vector<int>来存放相加后的数，由于相加数的存放是倒着的，所以最终的结果也是倒着存放在vector<int>中的，此时打印就需要从后面往前面打印输出。

• 加法不难，但要注意的是，如何在程序中表示进位，我们都知道，每一位数相加超过10就要进位1，表示这一位的前一位要+1。3和5相加为8不用进位，而7和8相加要进位，最后在这一位留下来的是（7 + 8）- 10 = 5，在程序中可以表示为（7 + 8）% 10。而这个%10就显得格外重要了，如果你相加后的数小于10，它%10后，还是它本身，如果大于10，它就相当于去掉一个10，剩下的数就放进表示最终答案的vector<int>。

• 最后要注意的是，两个位上的数相加后的结果要/=10,这是表示要除去这一位该留下的结果以及得到需要进的位，例如：7 + 8 = 15 ，在该位应该留下的最终结果为 15 % 10 = 5，最后 15 /= 10 得到1，表示要进位1，该位的结果5除去。

下面是相关操作的代码实现：

#include <iostream>
#include <vector>using namespace std;vector<int> add(vector<int>& A, vector<int>& B)
{vector<int> C;int tmp = 0;for (int i = 0; i < A.size() || i < B.size() || tmp; i++){if (i < A.size()) tmp += A[i];if (i < B.size()) tmp += B[i];C.push_back(tmp % 10);tmp /= 10;}while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}int main()
{string a, b;cin >> a >> b;vector<int> 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];cout << endl;return 0;
}

代码测试：

代码细节解释：

• 这里是将高精度数分别从低位到高位存放到两个vector<int>中；

	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');

• 这个for循环便是相加的代码，两个if表示如果这个数的位数加完了，就停止加入tmp，判断条件表示将tmp加完为止（也就是如果两个数位数相同，最高位相加完后又进了一位，此时 tmp 为 1 并且不在加入数据，这个1 也是有效位，因此需要加入C中）

	for (int i = 0; i < A.size() || i < B.size() || tmp; i++){if (i < A.size()) tmp += A[i];if (i < B.size()) tmp += B[i];C.push_back(tmp % 10);tmp /= 10;}

• 这个while表示去掉前导0，虽然加法不会出现前导0的情况，但不排除输入的数据都为0的情况。

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

---

2.高精度减法

• 高精度减法是两个很高位数的数相减，值得注意的是，减法需要借位，并且相减会出现结果为正还是负的情况，因此，高精度减法的程序比高精度加法的程序稍复杂。

• 对于结果是正还是负的情况，我们可以写一个cmp函数对存放两个高精度数的string进行比较，然后规定sub函数第一个参数为大的那个数，我们只要将大的那个传入第一个参数即可。如果是第二个输入的高精度数较大，在打印结果的时候先打印一个‘ - ’即可。

• 在进行相减的时候，我们可以先定义一个标记借位的变量tmp(初始化为0)，如果一位上相减为负数，说明需要向前借一位，所以在减的循环中第一条语句可以为：tmp = big[i] - tmp;，如果结果小于零，将tmp置为1，等进入下一次循环，第一条语句就自动减一，起到借位的效果。

• 那么结果小于0，我们该如何确定这一位的最终答案呢？我们只需要在push_back时，里面的参数设为（tmp + 10）% 10,这样就可以处理tmp所有的情况了（详细点看代码注释）。

• 由于我们是通过将高精度数的每一位存入数组来计算的，并且减法会出现最高位依次连续是0的情况，因此作为答案的数组，高位可能存放有0，在打印的时候这些0都会被打印出来，所以这里要有删去高位0的操作。

下面是相关操作的代码实现：

#include <iostream>
#include <vector>
using namespace std;bool cmp(vector<int>& A, vector<int>& 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];return true;
}vector<int> sub(vector<int>& A, vector<int>& B)
{vector<int> C;int tmp = 0; // 用来标记借位// 这里A要大，所以 i < A.size()for (int i = 0; i < A.size(); i++){tmp = A[i] - tmp; // 表示上一步有没有借位if (i < B.size()) tmp -= B[i];// (tmp + 10) % 10 这是因为：// 当tmp<0时，说明这一位A的小于B的，因此要借位//    所以tmp+10后就相当于借位后的数，%10后便是留在这一位的最终结果// 当tmp>0时，说明这一位A的大于B的，尽管加了10//    但%10后加10与不加10是一样的（可脑补一下）C.push_back((tmp + 10) % 10);// 如果tmp<0,表示这一位A的小于B的，因此将tmp置为1，下一次循环的第一步减去一if (tmp < 0) tmp = 1;else tmp = 0;}// 由于高位会出现0的情况(22226 - 22223 = 3)，所以这里要去前导0while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}int main()
{string a, b;cin >> a >> b;vector<int> 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');if (cmp(A, B)){auto C = sub(A, B);for (int i = C.size() - 1; i >= 0; i--) cout << C[i];}else{auto C = sub(B, A);cout << '-';for (int i = C.size() - 1; i >= 0; i--) cout << C[i];}return 0;
}

代码测试：

3.高精度乘法

• 在学完高精度加法和减法后，对于高精度乘法理解起来是很快的，这里我们规定，输入的第一个数为高精度数，第二个数为int范围内的数,并且两个数都是正整数。

• 有了上面的规定，接下来的操作就简单了，我们只需要关注如何乘，如何push,以及去前导0即可。

• 相乘前的准备与高精度加减类似，只不过输入的其中一个参数变为了int 。

• 整个相乘的过程：定义一个tmp ，将高精度数的每一位与int数相乘加入tmp(每一次循环将每一位相乘后的结果加入tmp)，然后每一次循环中，将tmp%10（每次取出个位上的数）push_back，再tmp/=10丢掉个位上的数，直到高精度的每一位数都乘过或者tmp为0循环结束，这样就完成了高精度的乘法。

• 如果输入的两个数有0，那么结果终究会是0，所以高精度乘法也要有去除前导零的操作。

下面是相关操作的代码实现：

#include <iostream>
#include <vector>using namespace std;vector<int> mul(vector<int>& A, int b)
{vector<int> C;int tmp = 0;for (int i = 0; i < A.size() || tmp; i++){// 如果A没有遍历完就一直将每一位与b相乘加入tmpif (i < A.size()) tmp += A[i] * b;// （tmp % 10）是push tmp的个位C.push_back(tmp % 10);// 丢弃个位tmp /= 10;}while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}int main()
{string a;int b, flag = 1;cin >> a >> b;vector<int> A;for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');auto C = mul(A, b);for (int i = C.size() - 1; i >= 0; i--) cout << C[i];return 0;
}

代码测试：

选取测试案例图解：

4.高精度除法

• 高精度除法与高精度乘法相比，多了一个变量r用来储存余数，其余的输入与乘法相同，但最后输出要把r打印。同样的，这里我们规定，两个数都是正整数，并且int范围内的那个数不能为0(一个高精度数除以一个int范围内的整数)。

• 对于整个相除的过程，肯定也是需要一个循环的。我们都知道，每一位相处的余数，都要相当于乘以10与下一位相加，由于r初始为0,因此循环的第一句可以写为r = r * 10 + A[i] ,A[i]为当前位的数，r*10表示上一位数相除得到的余数，如果上一位数余数为零，则这个表达式结果为0。

• 执行完上一条语句后便得到了被除数，此时就可以push:r / 除数，表示当前位的结果，最后再r %= 除数 除去除完的除数，这样整个过程就设计完成了。

• 由于main函数打印正确答案是从尾开始将每一位打印到头的，并且正确答案是由高位到低位从数组的头依次存放的，因此下一步需要逆置一下结果数组。

• 最后，除法会有高位为0的情况,因此还要有一步去除前导0的操作。

下面是相关操作的代码实现：

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;// 要改变main函数里的余数r，因此要引用
vector<int> div(vector<int>& A, int b, int& r)
{vector<int> C;// 根据除法的过程，从高位开始除for (int i = A.size() - 1; i >= 0; i--){// r开始为0，则第一次循环就为A的最高位与b相除// 如果 r>b 则会有余数 ，所以下一次循环将这个余数 乘以10+A[i] 便是第二次循环要除的数// 如果 r<b 则余数就是r本身，第三条语句 r%=b 就相当于没执行过r = r * 10 + A[i];C.push_back(r / b); // push 这一次除b的结果，如果r<b，则push:0r %= b;}// 由于得到的结果是从高位向低位开始存的，所以这里逆置一下，便于去除前导0reverse(C.begin(), C.end());// 除法会出现0的情况，因此这里要处理前导0while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}int main()
{string a;// b为int范围内的数// 创建一个变量r来储存余数int b, r = 0;cin >> a >> b;// A用来储存高精度数vector<int> A;for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');auto C = div(A, b, r);// 打印还是与前面一样，因为div中结果逆置了for (int i = C.size() - 1; i >= 0; i--) cout << C[i];// 这里打印余数cout << endl << r << endl;return 0;
}

代码测试：

选取测试案例图解：

输入

128
8

输出

16
0

写在最后

上述可以说都是高精度计算的基础模板，实际上在很多题目中都可以用到这一模板，比如某些链表的题。所以我们要增强对这一类模板的熟练度，以便在后面的刷题中遇到能用此模板解决的问题能够想起来有这一模板可以用。

感谢阅读本小白的博客，错误的地方请严厉指出噢！