浅谈高精度算法（加减乘除）

　　在c/c++中，不时会遇到限定数据范围的情况，我们先来看看常用的int和long long两种数据类型的范围吧。

　　c++标准规定，int占一个机器字长。在32位系统中int占32位，也就是4个字节，所以在32位系统中，int的范围是[-2^31,2^31-1]，为10^9数量级；而long long的范围则是[-2^63,2^63-1]，为10^18数量级，但当一些acm/oi题目中测试数据范围超过此范围，甚至超过double（1.7*10^308数量级）时，该怎么办？java有大数类，而python的整数也是不限制长度的，虽然c++的整数长度受到限制，但我们也有高精度算法，下面，我将介绍几种常见的高精度整算法。

　　一、高精度加法。

　　对于10^308以上的大数，确实不能用c++内置的数据类型直接处理，但回想我们曾经做过的小学算术问题，两个整数相加，先从个位算起，过十进位，依照这个思路，我们可以将大数存放在数组中，再利用数组去模拟加法运算的过程，代码如下：

#include<iostream>
#include<cstring>
using namespace std;
char s1[505],s2[505];
int a[505],b[505],c[505];
int main(){
    int m,n,v,t;
    std::ios::sync_with_stdio(false);
    cin>>s1>>s2;
    m=strlen(s1);
    n=strlen(s2);
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
    for(int i=0;i<m;i++){
        a[m-1-i]=s1[i]-'0';
    }
    for(int i=0;i<n;i++){
        b[n-1-i]=s2[i]-'0';
    }
    m=max(m,n);
    m++;
    memset(c,0,sizeof(c));
    for(int i=0;i<m;i++){         
        v=a[i]+b[i];
        if((c[i]+v)<10)
            c[i]+=v;
        else{
            c[i+1]+=(c[i]+v)/10;
            c[i]=(c[i]+v)%10;        
        }    
    }    　　　　

//下面是一种更简单的做法，结果直接储存在a中                    
    /*for(int i=0;i<m;i++){
        a[i]+=b[i];
        a[i+1]+=a[i]/10;
        a[i]%=10;    
    }*/
    if(c[m-1]==0)    m--;
    for(int i=m-1;i>=0;i--)    cout<<c[i];
    return 0;
}

　　二、高精度减法。

　　和高精度加法的基本思路相同，不过在减法中，需要确定输入数字的相对大小来判断是否输出负号，还需要注意是否要"借位"。上代码：

#include<iostream>
#include<cstring>
using namespace std;
bool compare(char s1[],char s2[]){
    int u=strlen(s1),v=strlen(s2);
    if(u!=v)
        return u>v;
    for(int i=0;i<u;i++)
        if(s1[i]!=s2[i])    return s1[i]>s2[i];
    return true;
}                                        　　　　　　　　　　//比较两个数相对大小 
int main(){
    std::ios::sync_with_stdio(false);
    int flag=1,i,j;
    char s1[100005],s2[100005],s3[100005];            　　//这里为节省空间考虑，直接用char数组运算 
    cin>>s1>>s2;
    if(compare(s1,s2));
    else{
        flag=-1;
        strcpy(s3,s1);
        strcpy(s1,s2);
        strcpy(s2,s3);
    }
    int u=strlen(s1),v=strlen(s2);
    for(i=u-1,j=v-1;j>=0;i--,j--){
        if(s1[i]<s2[j]){
            s1[i-1]-=1;
            s3[i]=s1[i]-s2[j]+10+'0';
        }
        else    s3[i]=s1[i]-s2[j]+'0';
    }                                                　　//从最后一位向前减 
    for(;i>=0;i--)    {
        if(s1[i]<'0'){
            s1[i-1]-=1;
            s3[i]=s1[i]+10;
        }
        else    s3[i]=s1[i];
    }                                                　　//s1数位大，所以还有s1减'0' 
    for(i=0;i<u-1&&s3[i]=='0';i++);                    　//只到u-1的原因时 
    if(flag==-1)    cout<<'-';
    cout<<s3+i;
    return 0;
}

　　三、高精度乘法。

　　依旧是模拟算术做竖式乘法的过程，要注意进位，贴代码：

#include<iostream>
#include<cstring>
using namespace std;
char a[2005],b[2005];
int c[2005],d[2005],e[4005];
int u,v,w;
int main(){
    int i,j;
    cin>>a>>b;
    u=strlen(a);
    v=strlen(b);
    memset(c,0,4005);
    for(int i=0;i<u;i++)
        c[u-1-i]=a[i]-'0';
    for(int i=0;i<v;i++)
        d[v-1-i]=b[i]-'0';
    for(i=0;i<u;i++){
        for(j=0;j<v;j++){
            w=c[i]*d[j];
            if(e[i+j]+w<10)    e[i+j]+=w;
            else{
                e[i+j+1]+=(e[i+j]+w)/10;
                e[i+j]=(e[i+j]+w)%10;
            }
        }
    }
    for(i=u+v-1;i>0&&e[i]==0;i--);        　　　　//此处是为了不漏掉输出结果为0而将条件写为i>0 
    for(;i>=0;i--)    cout<<e[i];
    return 0;
}

　　四、高精度除法。

　　高精度除法分两种，都是仿照竖式除法实现，一种是高精度除以低精度，较为容易实现，主要是利用一个数，在线处理：

#include<iostream>
#include<cstring>
#include<string>
using namespace std;
char s1[5005];
int a[5005],b,c[5005],x=0;
int main(){
    cin>>s1>>b;
    a[0]=strlen(s1);
    for(int i=1;i<=a[0];i++)    a[i]=s1[i-1]-48;
    memset(c,0,sizeof(c));
    for(int i=1;i<=a[0];i++){
        c[i]=(x*10+a[i])/b;
        x=(x*10+a[i])%b;　　
    }        　　　　　　　　　　　　　　　　　　　　　　//核心部分
    x=1;
    while(c[x]==0&&x<a[0])    x++;
    for(;x<=a[0];x++)    cout<<c[x]; 
    return 0;
}

　　另一种，是运用逐次相减的方法确定出商和余数，代码如下：

#include<iostream>
#include<cstring>
using namespace std;
int a[5005],b[5005],c[5005],d[5005];
bool compare(int a[],int b[]){
    if(a[0]!=b[0])    return a[0]>b[0];
    for(int i=a[0];i>0;i--){
        if(a[i]!=b[i])    return a[i]>b[i];
    }
    return true;
}
int main(){
    std::ios::sync_with_stdio(false);
    string s1,s2;
    cin>>s1>>s2;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    a[0]=s1.length();
    b[0]=s2.length();
    for(int i=1;i<=a[0];i++)    a[i]=s1[a[0]-i]-'0';
    for(int i=1;i<=b[0];i++)    b[i]=s2[b[0]-i]-'0';
    c[0]=a[0]-b[0]+1;
    for(int i=c[0];i>0;i--){            //c[0]代表最初a,b的数位差 
        memset(d,0,sizeof(d));
        for(int j=1;j<=b[0];j++)
            d[j+i-1]=b[j];
        d[0]=b[0]+i-1;                    　　　　　　　//先让b中存下的数与a在一个数量级 
        while(compare(a,d)){            　　　　　　　　//比较，如果a比较大，用a直接减去d，如果a比较小，下一次大循环中，d的位数会减一 
            c[i]++;
            for(int i=1;i<=a[0];i++){
                a[i]-=d[i];
                if(a[i]<0){
                    a[i+1]--;
                    a[i]+=10;
                }
            }
            while(a[0]>0&&a[a[0]]==0)    a[0]--;
        }
    }
    while(c[0]>1&&c[c[0]]==0)    c[0]--;
    cout<<"商：";
    for(int i=c[0];i>0;i--)    cout<<c[i];
    cout<<endl<<"余数：";
    for(int i=a[0];i>0;i--)    cout<<a[i];        　　　//a中最后剩下的就是余数  
    return 0;
}

　　好的，高精度基础算法介绍完毕，大家不妨自行动手一试。