本文转载自：http://blog.sina.com.cn/s/blog_4fdb102b010087ng.html
前言:由于计算机运算是有模运算,数据范围的表示有一定限制,如整型int(C++中int 与long相同)表达范围是(-231~231-1),unsigned long(无符号整数)是(02^32-1),都约为几十亿.如果采用实数型,则能保存最大的double只能提供1516位的有效数字,即只能精确表达数百万亿的数.因此,在计算位数超过十几位的数时,不能采用现有类型,只能自己编程计算. 高精度计算通用方法:高精度计算时一般用一个数组来存储一个数,数组的一个元素对应于数的一位(当然,在以后的学习中为了加快计算速度,也可用数组的一个元素表示数的多位数字,暂时不讲),表示时,由于数计算时可能要进位,因此为了方便,将数由低位到高位依次存在数组下标对应由低到高位置上,另外,我们申请数组大小时,一般考虑了最大的情况,在很多情况下,表示有富余,即高位有很多0,可能造成无效的运算和判断,因此,我们一般将数组的第0个下标对应位置来存储该数的位数.如数:3485(三千四百八十五)，表达在数组a[10]上情况是: 下标 0 1 2 3 4 5 6 7 8 9 内容 4 5 8 4 3 0 0 0 0 0 说明：位数 个位 十位 百位 千位 具体在计算加减乘除时方法就是小学时采用的列竖式方法． 注：高精度计算时一般用正数，对于负数，通过处理符号位的修正． 一．高精度数的存储 １．如对数采用的字符串输入
#include <iostream> #include <cstring> using namespace std; const int N=100;//最多100位 int main() { int a[N+1],i; string s1; cin>>s1;//数s1 memset(a,0,sizeof(a)); //数组清0 a[0]=s1.length(); //位数 for(i=1;i<=a[0];i++) a[i]=s1[a[0]-i]-'0';//将字符转为数字并倒序存储． return 0; }2.直接读入
#include <iostream> using namespace std; const int N=100;//最多100位 int main() { int a[N+1],i,s,key; cin>>key;//数key memset(a,0,sizeof(a)); //数组清0 i=0;//第0位 while(key) //当key大于0 { a[++i]=key%10;//取第i位的数 key=key/10; } a[0]=i; //共i位数 return 0; }3.直接初始化(用a[]存储) 初始化为0: memset(a,0,sizeof(a)); 初始化为1: memset(a,0,sizeof(a));a[0]=1;a[1]=1;
以下程序都只写函数，不写完整程序，所有高精度数存储都满足上述约定。
二.高精度数比较 int compare(int a[],int b[]) //比较a和b的大小关系，若a>b则为1，a<b则为-1,a=b则为0 {int i; if (a[0]>b[0]) return 1;//a的位数大于b则a比b大 if (a[0]<b[0]) return -1;//a的位数小于b则a比b小 for(i=a[0];i>0;i–) //从高位到低位比较 {if (a[i]>b[i]) return 1; if (a[i]<b[i]) return -1;} return 0;//各位都相等则两数相等。 }
三、高精度加法 int plus(int a[],int b[]) //计算a=a+b {int i,k; k=a[0]>b[0]?a[0]:b[0]; //k是a和b中位数最大的一个的位数 for(i=1;i<=k;i++) {a[i+1]+=(a[i]+b[i])/10; //若有进位，则先进位 a[i]=(a[i]+b[i])%10;} //计算当前位数字,注意：这条语句与上一条不能交换。 if(a[k+1]>0) a[0]=k+1; //修正新的a的位数（a+b最多只能的一个进位） else a[0]=k; return 0; }
四、高精度减法 int gminus(int a[],int b[]);//计算a=a-b，返加符号位0:正数 1:负数 { int flag,i flag=compare(a,b); //调用比较函数判断大小 if (falg0)//相等 {memset(a,0,sizeof(a));return 0;} //若a=b，则a=0,也可在return前加一句a[0]=1,表示是 1位数0 if(flag1) //大于 { for(i=1;i<=a[0];i++) { if(a[i]<b[i]){ a[i+1]–;a[i]+=10;} //若不够减则向上借一位 a[i]=a[i]-b[i];} while(a[a[0]]0) a[0]–; //修正a的位数 return 0;} if (flag-1)//小于 则用a=b-a,返回-1 { for(i=1;i<=b[0];i++) { if(b[i]<a[i]){ b[i+1]–;b[i]+=10;} //若不够减则向上借一位 a[i]=b[i]-a[i];} a[0]=b[0]; while(a[a[0]]==0) a[0]–; //修正a的位数 return -1;} }
五、高精度乘法1(高精度乘单精度数，单精度数是指通常的整型数) int multi1(int a[],long key) //a=a*key,key是单精度数 {int i,k; if (key==0){memset(a,0,sizeof(a));a[0]=1;return 0;} //单独处理key=0 for(i=1;i<=a[0];i++)a[i]=a[i]*key;//先每位乘起来 for(i=1;i<=a[0];i++){a[i+1]+=a[i]/10;a[i]%=10;} //进位 //注意上一语句退出时i=a[0]+1 while(a[i]>0) {a[i+1]=a[i]/10;a[i]=a[i]%10;i++;a[0]++];} //继续处理超过原a[0]位数的进位,修正a的位数 return 0; }
int multi2(int a[],int b[]) //a=a*b { }
