8-高精度计算（加法）

我们知道，在C语言和C++中对于所能存储的数值的最大值是有明确的上限的。但是我们有时候会需要去计算一些数值比较大的数字：例如位数为1000、10000的数字的加减运算，这时候我们就需要使用新的运算方法了。

这里引入高精度的大数据计算，它可以用计算位数很大例如的数字。它的主要思想是利用数组进行存储大数的位数，并且利用计算规则的特点来进行计算，下面我们来看看加法。

首先是大数据的处理过程，我们一般long类型变量如果存不下的数据，我们考虑用一个数组或者vector类型的容器来存储。例如数字1598，我们可以用一个数组将其倒过来存储，arr[0]先存储个位，然后后面位数依次存进去（如下图下方图）。这样存有个好处，因为我们做加法运算时有可能会最大位向前进一位，如果此时我们选择arr[0]为最大位，那么我们进一就需要将整个数组向后镦一位（如下图上方图）。

了解完存储大数字的方式，接下来我们先来回忆一下加法的运算过程：例如我们有两个数组A,B，C，它们存储大数a，b的每个位上的数据，C为存储结果各个位数值的数组。然后我们先从两个数组对应的个位算起，将个位数字计算完后，看其是否需要向十位进位，以此类推计算。因为还要考虑进位问题，所以我们索性定义C每一位都是(A[i]+B[i]+t)%10，这里的t是前一位向本位进的位数。个位是t就是0就可以。例如下面的式子：A={9，3，1}，B={7，3}。C[0]=(A[0]+B[0]+0)%10=16%10=6；C[1]=(A[1]+B[1]+1)%10=7%10=7；C[2]=(A[2]+0)%10=1%10=1。所以C为{6，7，1}。

按照这个思路，我们可以写出大数加法的代码，这里为了方便使用了容器vector：

整体代码分为两段：第一段是处理数据，第二段是大数计算。

先来看处理数据：我们用的是string类型的变量接收数据，所以我们要想换成vector容器存储每一个位，就需要将字符串中每一个数字转换为一个int类型的数据存进去A/B容器中。数字字符和数字有一个对应关系：x(char类型)-'0' = x(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');

接下来就是核心的大数计算的部分了：

我们将两个需要进行加运算的容器传进函数中，然后用一个循环将两容器的每一位相加。举个例子：两个数字相加：120和3，它们结果是123，这里的120中的1和2没有运算，因为3只需和120中的个位运算。同理，两个数相加要么是两个数刚好相等，或者一方比另一方位数高，此时加法停止的条件就是位数高的那个数字的最高位计算完毕。所以循环的结束条件是当加到A、B中最大的那位，此时加法停止。所以有下面的停止判断条件。

 i < A.size() || i < B.size()

 然后我们来看里面的两个if，这两个if是我们不确定A还是B的位数高，所以让位数低的位数计算完后先停止运算，而位数高的继续计算。然后将加得的数据对十取模来获得A、B对应位的结果，赋给C，最后再将t除10获得进位。最后的if(t)是判断两个数相加是否需要增位，判断最后运算完是否需要向下一次进1，也就是判断t是否为1。是就加1，不是不处理。

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 = t / 10;
	}
	if (t) C.push_back(1);
	return C;
}

总体代码： 

#include<iostream>
using namespace std;
#include<vector>


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 = t / 10;
	}
	if (t) C.push_back(1);
	return C;
}




int main()
{
	string a, b;
	vector<int> A, B;
	cin >> 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];

	return 0;
}