高精度计算：C++ LongInt实现

更新：2023-05-13 07:08

一、为什么需要高精度计算

在进行数字计算的时候，常常会遇到数值过大（超过计算机所能表示的范围）的情况。例如，计算排列组合数、大数乘法、大数除法、高精度加减法、高精度幂等计算等。这时，就需要用到高精度计算。

高精度计算是通过将一个大数拆分成多个小数，然后利用计算机的机制来进行处理，进而达到表示大数的目的。一般情况下，我们可以利用数组存储一个数，每个元素存储这个数的一位，这样就可以表示任意长度的大数。

二、C++ LongInt实现

C++语言本身就支持很好的高精度计算，用STL即可。例如vector、string等类，都可以进行高精度运算。另外，我们还可以自己实现一些高精度的类，例如LongInt。

下面给出一个简单的LongInt类实现，包括加、减、乘、除、取模、赋值、大小比较等基本操作。

#include<vector>
#include<iostream>
using namespace std;
class LongInt{
public:
    vector<int>num;
    bool flag;
    LongInt(){flag=false;}
    LongInt(string s){init(s);}
    LongInt(const LongInt&a){num=a.num;flag=a.flag;}
    void init(string&s){
        int len=s.length()-1;
        while(len>=0){num.push_back(s[len]-'0');len--;}
        flag=s[0]=='-';
        if(flag)num.pop_back();
    }
    LongInt&operator+(LongInt&rhs){
        int carry=0;
        int len=max(num.size(),rhs.num.size());
        for(int i=0;i=num.size())num.push_back(0);
            num[i]=carry%10;
            carry/=10;
        }
        if(carry)num.push_back(carry);
        return*this;
    }
    LongInt&operator-(LongInt&rhs){
        int borrow=0;
        for(int i=0;i
     1&&num.back()==0)num.pop_back();
        return*this;
    }
    LongInt&operator*(LongInt&rhs){
        vector<int>result(num.size()+rhs.num.size(),0);
        for(int i=0;i
      1&&num.back()==0)num.pop_back();
        return*this;
    }
    LongInt&operator/(LongInt&rhs){
        int len=num.size()-rhs.num.size();
        LongInt quotient;quotient.flag=flag^rhs.flag;
        if(len<0){
            quo.num.push_back(0);
            return quotient;
        }
        LongInt dividend(*this<
       =0;i--){
            int l=0,r=10,ans=0;
            while(l<=r){
                int mid=(l+r)>>1;
                if(dividend>=(divisor*mid)){l=mid+1;ans=mid;}
                else r=mid-1;
            }
            quotient.num.insert(q.n.begin(),ans);
            dividend-=(divisor*ans);
            divisor>>1;
        }
        while(quotient.num.size()>1&&quotient.num.back()==0)quotient.num.pop_back();
        return quotient;
    }
    LongInt&operator%(LongInt&rhs){
        *this-*((*this/rhs)*rhs);
        return*this;
    }
    LongInt&operator<<(int n){
        while(n--)num.insert(num.begin(),0);
        return*this;
    }
    bool operator>(LongInt&r){
        if(num.size()!=r.num.size())return num.size()>r.num.size();
        for(int i=num.size()-1;i>=0;i--)if(num[i]!=r.num[i])return num[i]>r.num[i];
        return false;
    }
    bool operator<(LongInt&rhs){return rhs>*this;}
    bool operator=(LongInt&rhs){
        num=rhs.n;
        return flag=rhs.flag;
    }
    void print(){
        if(flag)putchar('-');
        for(int i=num.size()-1;i>=0;i--)putchar(num[i]+'0');
    }
};

三、使用LongInt类实现高精度计算

下面，我们来利用上面实现的LongInt类进行高精度计算。可以实现加法、减法、乘法、除法、取模等计算。

#include<iostream>
#include<string>
#include"LongInt.h"
using namespace std;
int main(){
    string s1="123456789012345678901234567890";
    string s2="987654321098765432107654321098";
    
    LongInt a(s1),b(s2);
    cout<<"a=";a.print();cout<<endl;
    cout<<"b=";b.print();cout<<endl;
    cout<<"add=";(a+b).print();cout<<endl;
    cout<<"sub=";(a-b).print();cout<<endl;
    cout<<"mul=";(a*b).print();cout<<endl;
    cout<<"div=";(a/b).print();cout<<endl;
    cout<<"mod=";(a%b).print();cout<<endl;
    
    return 0;
}