首页 > 代码库 > BigInteger之高精度乘法

BigInteger之高精度乘法

(接上篇http://www.cnblogs.com/daipeiwu/p/4134694.html)

重写*

 1 BigInteger operator * (const BigInteger& b){ 2         BigInteger c,d; 3         c.s.clear(); 4         d.s.clear(); 5         int rst; 6         for(int i=0;i<s.size();i++){ 7             for(int j = 0;j<b.s.size();j++){ 8                 stringstream ss; 9                 string str;10                 rst = s[i]*b.s[j];11                 ss<<rst;12                 ss>>str;13                 str+=func((i+j)*WIDTH);14                 d = str;15                 c = c+d;16             }17         }18         return c;19     }

完整代码:

 1 #include <iostream> 2 #include <cstring> 3 #include <vector> 4 #include<stdio.h> 5 #include<sstream> 6 using namespace std; 7 string func(int n){ 8     string s; 9     for(int i=0;i<n;i++)10         s+="0";11     return s;12 }13 struct BigInteger {14     static const int BASE = 10000;15     static const int WIDTH = 4;16     vector<int> s;17     BigInteger (long long num = 0){*this = num;}18     BigInteger operator = (long long num){19         s.clear();20         do{21             s.push_back(num % BASE);22             num/= BASE;23         }while(num>0);24         return *this;25     }26     BigInteger operator = (const string& str) {27         s.clear();28         int x,len = (str.length()-1)/WIDTH +1;29         for(int i =0; i<len; i++) {30             int end = str.length() - i*WIDTH;31             int start = max(0,end-WIDTH);32             sscanf(str.substr(start,end-start).c_str(),"%d",&x);33             s.push_back(x);34         }35         return *this;36     }37     BigInteger operator + (const BigInteger& b){38         BigInteger c;39         c.s.clear();40         for(int i=0,g=0;;i++){41             if(g==0&& i>=s.size()&&i>=b.s.size()) break;42             int x = g;43             if(i< s.size())x+=s[i];44             if(i<b.s.size())x+=b.s[i];45             c.s.push_back(x%BASE);46             g = x/BASE;47         }48         return c;49     }50     BigInteger operator * (const BigInteger& b){51         BigInteger c,d;52         c.s.clear();53         d.s.clear();54         int rst;55         for(int i=0;i<s.size();i++){56             for(int j = 0;j<b.s.size();j++){57                 stringstream ss;58                 string str;59                 rst = s[i]*b.s[j];60                 ss<<rst;61                 ss>>str;62                 str+=func((i+j)*WIDTH);63                 d = str;64                 c = c+d;65             }66         }67         return c;68     }69 };70 71 ostream& operator << (ostream &out,const BigInteger& x) {72     BigInteger c;73     c = x;74   while(c.s.end()-1!=c.s.begin()){75         if(c.s.back()==0) c.s.pop_back();76        else break;77    }78     out<<c.s.back();79     for(int i=c.s.size()-2; i>=0; i--) {80         char buf[20];81         sprintf(buf,"%0*d",BigInteger::WIDTH,c.s[i]);82         for(int j=0; j<strlen(buf); j++)83             out<<buf[j];84     }85     return out;86 }87 istream& operator >> (istream &in,BigInteger& x){88     string s;89     if(!(in>>s))return in;90     x = s;91     return in;92 }93 94 int main() {95     BigInteger a,b;96     cin>>a>>b;97     cout<<a*b<<endl;98     return 0;99 }

 

BigInteger之高精度乘法