高精度加法的实现
这是C++算法基础-基础算法专栏的第七篇文章，专栏详情请见此处。引入
在C++语言中，int的可存储数据范围是-2147483648~2147483647，long long的可存储数据范围是-9223372036854775808~9223372036854775807，但是假如一些数据比long long的可存储数据还要大时，我们就不得不使用别的方法去储存与计算了，这种方法就是高精度计算。
下面我们就来讲高精度加法的实现。
这里需要说明，此博客（包括反面三篇），都是使用数组实现的，而算法基础课中是使用C++STL中的vector容器实现的，代码上两者有所不同，但是思路是一样的。
界说
高精度计算（Arbitrary-Precision Arithmetic），也被称作大整数（bignum）计算，运用了一些算法结构来支持更大整数间的运算（数字大小超过语言内建整型）。
前置过程
这里我们用数组来实现高精度计算。
扫除
先做一个简单的扫除数组的操作。
void clear(int a[]){
for(int i=0;i<L;i++)
a=0;
} 输入与储存
高精度计算数字的规模太大了，需要输入一个字符串，再把它放进数组里。
Q：怎样字符串转化为数组呢？
A：字符串的每一位都是字符，若想把它转化为数组，就需要用ASCII码进行偏移操作，将此字符减去‘0’。
还有一个问题，读入字符串时，数字最高位在字符串首（下标小的位置）。但是现实我们习惯在下标最小的位置存放数字的个位，即存储一个反转的字符串。
Q：为什么要存储一个反转的字符串呢？
A：这么做是因为两个数进行运算时通常从个位开始，且运算时数字的长度也有大概发生变革，但我们盼望同样个位始终保持对齐，以是反转存储是最好的方式。
下面给出高精度计算的读入与储存代码：
void read(int a[]){
cin>>s;
int L=s.size();
for(int i=0;i<L;i++)
a=s-'0';
} 输出
输出一个数组没什么难的，但在高精度计算中，我们不盼望将数组中的前导零输出，故需要从最高位开始向下探求第一个非零的位置，从这里开始输出。
你会发现在代码中，终止条件是https://latex.csdn.net/eq?i%20%3E%3D%201而不是https://latex.csdn.net/eq?i%20%3E%3D%200，这是因为若这个数字本身就是0，则需要输出个位。
下面给出高精度计算的输出代码：
void print(int a[]){
int i;
for(i=L-1;i>=1;i--){
if(a!=0)
break;
}
for(;i>=0;i--)
cout<<a;
cout<<endl;
}主体过程
高精度加法的原理和小学学习的竖式加法是一样的。
https://img-blog.csdnimg.cn/direct/a82ec48f4d3e403ab9bae12d3c16dc2d.png
概括来说，从个位开始，将两个加数相对应的每一位相加，存进和的对应位置上，若当前位到达https://latex.csdn.net/eq?10，进位，也就是将下一位加https://latex.csdn.net/eq?1，并把当前位减https://latex.csdn.net/eq?10。
https://latex.csdn.net/eq?123+89用高精度计算，先加个位，https://latex.csdn.net/eq?3+9得https://latex.csdn.net/eq?12，发现https://latex.csdn.net/eq?12大于等于https://latex.csdn.net/eq?10，以是将https://latex.csdn.net/eq?12减https://latex.csdn.net/eq?10，得https://latex.csdn.net/eq?2，将其存入答案的个位，将十位加https://latex.csdn.net/eq?1；
再加十位，https://latex.csdn.net/eq?1+2+8得https://latex.csdn.net/eq?11，发现https://latex.csdn.net/eq?11大于等于https://latex.csdn.net/eq?10，以是将https://latex.csdn.net/eq?11减https://latex.csdn.net/eq?10，得https://latex.csdn.net/eq?1，将其存入答案的十位，将十位加https://latex.csdn.net/eq?1；
最后加百位，https://latex.csdn.net/eq?1+1+0得https://latex.csdn.net/eq?2，发现https://latex.csdn.net/eq?2不大于等于https://latex.csdn.net/eq?10，以是直接将https://latex.csdn.net/eq?2存入答案的百位。得到答案https://latex.csdn.net/eq?212。
代码
下面给出高精度加法的代码：
void add(int a[],int b[],int c[]){
clear(c);
for(int i=0;i<L-1;++i){
c+=a+b;
if(c>=10){
c+=1;
c-=10;
}
}
} 上一篇-浮点数二分查找的实现 C++算法基础专栏文章 下一篇-高精度减法的实现
每周六更新一篇文章，内容一般是自己总结的经验或是在其他网站上整理的优质内容
点个赞，关注一下呗~
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]