C++的高精度加法

当C++中计算的数据位数超过了自身所具有的位数，那么在计算中就容易出错。高精度计算就是自己编程，自己进行计算。下面介绍一些关于高精度的计算。

高精度的计算主要就是模拟手工计算，比如加法，我们小学的时候通常学过使用竖式计算。

现在我们一起来回忆一下竖式计算的过程：

比如对于473+259，我们可以列出竖式：

473

+259

732

上面的过程是这样的：

第一个加数的个位3与第二个加数的个位9相加，得到12，保留2，进1；然后7+5等于12，12要加上之前的进位1，为13，保留3，进1；最后4+2等于6，再加上进位1，得到7，保留7，无进位。所以最终的答案为732。

接下来，便将这个计算过程写成C++的程序。

首先，我们要读入两个加数并存储。由于数据太大，长度太长，所以使用基本类型是不可能读入的。所以这时我们会想到使用字符串读入。假设我们定义的字符串为s，那么使用以下语句进行读入：

cin>>s;

读入之后，我们就将一个高精度数据以字符串的形式进行存储。但是由于字符串之间的数字不能直接进行加减运算，所以我们要使用数组来存储这个数，假设我们定义一个数组a，大小为100，那么，转换的程序便可以是：

1. 
   
2. la=s.length();
3. for(int i=0;i<la;i++)
4. a[la-i]=s[i]-48;

注意在下面要把下标反一下，假设我们读入9348这个数，那么9,3,4,8的下标分别为0,1,2,3，但是我们存储的时候，9,3,4,8的下标分别为4,3,2,1，所以我们要用4减去字符串的下标，而这里的4刚好为字符串的长度。

这样，我们便将字符串转换为数组了，同时也知道了它的长度。由于共有两个加数，所以这一步还需要做一遍。假设另一个数的数组名为b。

接下来的计算过程就是关键了，我们需要模拟手工运算，即竖式运算。在竖式运算的时候一定要保持数位对齐，个位与个位相加，十位与十位相加， 同时还要进位。那么在我们的C++程序中，就是两个数组相同下标的部分进行相加，相加的结果除以10可以得到进位，然后将相加的结果mod 10，下一位的计算的时候就加上进位。

下面是计算过程的代码：

1. 
   
2. int i,x=0;
3. for(i=1;i<=la||i<=lb;i++) {
4. c[i]=a[i]+b[i]+x;
5. x=c[i]/10;
6. c[i]%=10;
7. }
8. c[i]=x;

注意算到最后的时候，最高位要加上进位。

算出来的结果可能会有多余的前导零，所以我们需要去除前导零，只要将长度减小就可以了。但注意最小的长度为1，否则如果计算的结果是0，那么最终的长度就会是0，不符合实际。

1. 
   
2. lc=i;
3. while(c[lc]==0&&lc>1)
4. lc--;

最后，我们需要将结果进行输出，输出的时候，从高位到低位，一个一个输出。代码：

1. 
   
2. for(int i=lc;i>=1;i--)
3. cout<<c[i];

这样，你的高精度加法就完成了，下面给出完整的代码：

1. 
   
2. #include<iostream>
3. #include<cstdio>
4. #include<string>
5. using namespace std;
6. const int maxn=100;
7. int a[maxn],b[maxn],c[maxn];
8. int la,lb,lc;
9. string s;
10. int main() {
11. cin>>s;
12. la=s.length();
13. for(int i=0;i<la;i++)
14. a[la-i]=s[i]-48;
15. cin>>s;
16. lb=s.length();
17. for(int i=0;i<lb;i++)
18. b[lb-i]=s[i]-48;
19. int i,x=0;
20. for(i=1;i<=la||i<=lb;i++) {
21. c[i]=a[i]+b[i]+x;
22. x=c[i]/10;
23. c[i]%=10;
24. }
25. c[i]=x;
26. lc=i;
27. while(c[lc]==0&&lc>1)
28. lc--;
29. for(int i=lc;i>=1;i--)
30. cout<<c[i];
31. return 0;
32. }

这就是全部的过程了，算法的时间复杂的为n（n为数的长度大小），当然还有一些更加快的算法，比如二分进行计算，时间复杂度可以降低很多。