常考题型 大整数运算

最近刷题发现机试很喜欢考大整数运算，于是我自己写了几个大整数运算的函数。

可能写的不是很好，主要帮助自己理解原理。

代码：

#include <iostream>
#include <vector>

using namespace std;

vector<int> ToBigInt(string str){
    //将字符转换串转换成int向量
    vector<int> num;
    for(int i=0;i<str.size();i++)
        num.push_back(str[i]-'0');
    return num;
}

int compare(vector<int> num1,vector<int> num2){
    //比较大小，小于输出1，大于输出-1，等于输出0
    if(num1.size()<num2.size()) return 1;
    else if(num1.size()>num2.size()) return -1;
    else{
        for(int i=0;i<num1.size();i++){
            if(num1[i]<num2[i]) return 1;
            else if(num1[i]>num2[i]) return -1;
        }
        return 0;
    }
}

vector<int> Add(vector<int> num1,vector<int> num2){
    //加法运算

    //补零使得两数对齐
    if(num1.size()>num2.size())
        num2.insert(num2.begin(),num1.size()-num2.size(),0);
    else if(num1.size()<num2.size())
        num1.insert(num1.begin(),num2.size()-num1.size(),0);

    vector<int> num3;
    int ci=0;//进位
    for(int i=num1.size()-1;i>=0;i--){
        num3.insert(num3.begin(),(num1[i]+num2[i]+ci)%10);
        ci=(num1[i]+num2[i]+ci)/10;
    }
    if(ci!=0) num3.insert(num3.begin(),ci);//如果还有进位，插入结果头部
    return num3;
}

vector<int> Sub(vector<int> num1,vector<int> num2){
    //减法运算
    int sign=0;//标记结果符号
    if(compare(num1,num2)==1){//num1<num2则交换两数，同时标记结果为负
        swap(num1,num2);
        sign=1;
    }
    //补零使两数对齐
    if(num1.size()>num2.size())
        num2.insert(num2.begin(),num1.size()-num2.size(),0);
    else if(num1.size()<num2.size())
        num1.insert(num1.begin(),num2.size()-num1.size(),0);

    vector<int> num3;
    int carry=0;//借位
    for(int i=num1.size()-1;i>=0;i--){
        num3.insert(num3.begin(),(num1[i]+10-num2[i]-carry)%10);
        if(num1[i]-num2[i]-carry<0) carry=1;
        else carry=0;
    }
    //去掉前缀0
    int pos=0;
    while(num3[pos]==0)
        pos++;
    num3.erase(num3.begin(),num3.begin()+pos);
    //如果是负数加上负号
    if(sign==1) num3[0]=-num3[0];
    return num3;
}

vector<int> Mul(vector<int> num1,vector<int> num2){
    //乘法运算
    vector<int> num3(num1.size()+num2.size(),0);
    for(int i=num1.size()-1;i>=0;i--)//记录每位结果
        for(int j=num2.size()-1;j>=0;j--)
            num3[num3.size()-1-(num1.size()-1-i+num2.size()-1-j)]+=num1[i]*num2[j];
    for(int i=num3.size()-1;i>0;i--){//修改进位
        if(num3[i]>=10){
            num3[i-1]+=num3[i]/10;
            num3[i]=num3[i]%10;
        }
    }
    //去掉前缀0
    int pos=0;
    while(num3[pos]==0)
        pos++;
    num3.erase(num3.begin(),num3.begin()+pos);
    if(num3.size()==0) num3.push_back(0);
    return num3;
}

vector<int> Div(vector<int> num1,int num2,int &r){
    //除法运算，r表示余数，引用返回
    if((num1.size()==1 && num1[0]==0)){
        vector<int> zero;
        zero.push_back(0);
        return zero;
    }

    vector<int> num3;
    for(int i=0;i<num1.size();i++){
        r=r*10+num1[i];
        num3.push_back(r/num2);
        r=r%num2;
    }
    //去掉前缀0
    int pos=0;
    while(num3[pos]==0)
        pos++;
    num3.erase(num3.begin(),num3.begin()+pos);
    if(num3.size()==0) num3.push_back(0);
    return num3;
}

int main() {
    cout<<"输入两个大整数：";
    string str1, str2;
    cin >> str1 >> str2;

    vector<int> num1= ToBigInt(str1),num2= ToBigInt(str2);

    int CompareRes= compare(num1,num2);
    if(CompareRes==1) cout<<"num1<num2";
    else if(CompareRes==0) cout<<"num1=num2";
    else cout<<"num1>num2";
    cout<<endl;

    vector<int> AddRes= Add(num1,num2);
    cout<<"num1+num2=";
    for(int i=0;i<AddRes.size();i++) cout<<AddRes[i];
    cout<<endl;

    vector<int> SubRes= Sub(num1,num2);
    cout<<"num1-num2=";
    for(int i=0;i<SubRes.size();i++) cout<<SubRes[i];
    cout<<endl;

    vector<int> MulRes= Mul(num1,num2);
    cout<<"num1*num2=";
    for(int i=0;i<MulRes.size();i++) cout<<MulRes[i];
    cout<<endl;
    cout<<endl;

    cout<<"输入一个大整数被除数和一个小整数除数：";
    string str;
    cin>>str;
    getchar();
    int x;
    cin>>x;
    int r=0;
    vector<int> num= ToBigInt(str);
    vector<int> DivRes=Div(num,x,r);
    cout<<"num1/num2=";
    for(int i=0;i<DivRes.size();i++)
        cout<<DivRes[i];
    cout<<endl;
    cout<<"余数r="<<r<<endl;

}

运行结果：