C++中怎么实现一个大整数乘法

C++中怎么实现一个大整数乘法

在C++编程中，大整数乘法是一个常见的算法问题。由于标准整数类型无法处理非常大的数值，因此需要通过特殊的数据结构和算法来实现大整数的乘法运算。本文将详细介绍如何在C++中实现大整数乘法，包括算法原理和具体代码实现。

算法竞赛入门经典 这本书并没有对大数乘法实现，所以自己补充了一下，乘法的实现很简单，就是再其数据结构基础上把每宽为8位的十进制数看成多项式的系数，vector的下标看成多项式的指数，然后再对应相乘相加就可以了，注意系数超过8位 将超八位的补分进位。

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
typedef long long LL;
struct BigInteger{
    static const int BASE = 100000000;
    static const int WIDTH = 8;
    vector<int> s;
    BigInteger operator = (const string& str){
        s.clear();
        int x, len=(str.length()-1)/WIDTH+1;
        for(int i=0;i<len;i++){
            x=0;
            for(int j=max(0,str.length()-(i+1)*WIDTH);j<min((int)str.length(),i*WIDTH+WIDTH);j++)
                x=x*10+str[j]-'0';
            s.push_back(x);
        }
        return *this;
    }
    BigInteger operator * (const BigInteger& b) const{
        int lena=s.size(),lenb=b.s.size(),lenc=lena+lenb-1;
        LL *buf =new LL[lenc+1];
        for(int i=0;i<=lenc;i++) buf[i]=0;
        for(int i=0;i<lena;i++)
            for(int j=0;j<lenb;j++)
                buf[i+j]+=((LL)s[i])*((LL)b.s[j]);
        for(int i=0;i<lenc;i++){
            buf[i+1]+=buf[i]/BASE;
            buf[i]=buf[i]%BASE;
        }
        BigInteger c;
        c.s.resize(lenc);
        for(int i=0;i<lenc;i++)
            c.s[i]=buf[i];
        delete[] buf;
        return c;
    }
    void print(){
        printf("%d",s.back());
        for(int i=s.size()-2;i>=0;i--){
            int buf=s[i],h=8;
            while(buf>0){buf/=10;h--;}
            for(int j=0;j<h;j++) printf("0");
            printf("%d",s[i]);
        }
        printf("\n");
    }
};
int main(){
    string a,b;
    cin>>a>>b;
    BigInteger x,y;
    x=a;y=b;
    (x*y).print();
    return 0;
}

关于C++中怎么实现一个大整数乘法就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。