ToB企服应用市场:ToB评测及商务社交产业平台
标题:
高精度加法的实现
[打印本页]
作者:
海哥
时间:
2024-6-20 14:57
标题:
高精度加法的实现
这是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[i]=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[i]=s[L-1-i]-'0';
}
复制代码
输出
输出一个数组没什么难的,但在高精度计算中,我们不盼望将数组中的前导零输出,故需要从最高位开始向下
探求第一个非零的位置
,从这里开始输出。
你会发现在代码中,终止条件是
而不是
,这是因为若这个数字本身就是0,则需要
输出个位
。
下面给出高精度计算的输出代码:
void print(int a[]){
int i;
for(i=L-1;i>=1;i--){
if(a[i]!=0)
break;
}
for(;i>=0;i--)
cout<<a[i];
cout<<endl;
}
复制代码
主体过程
高精度加法的原理和小学学习的
竖式加法
是一样的。
概括来说,从个位开始,将两个加数相对应的每一位相加,存进和的对应位置上,若当前位到达
,
进位
,也就是将下一位加
,并把当前位减
。
用高精度计算,先加个位,
得
,发现
大于等于
,以是将
减
,得
,将其存入答案的个位,将十位加
;
再加十位,
得
,发现
大于等于
,以是将
减
,得
,将其存入答案的十位,将十位加
;
最后加百位,
得
,发现
不大于等于
,以是直接将
存入答案的百位。得到答案
。
代码
下面给出高精度加法的代码:
void add(int a[],int b[],int c[]){
clear(c);
for(int i=0;i<L-1;++i){
c[i]+=a[i]+b[i];
if(c[i]>=10){
c[i+1]+=1;
c[i]-=10;
}
}
}
复制代码
上一篇-浮点数二分查找的实现 C++算法基础专栏文章 下一篇-高精度减法的实现
每周六更新一篇文章,内容一般是自己总结的经验或是在其他网站上整理的优质内容
点个赞,关注一下呗~
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。
欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)
Powered by Discuz! X3.4