大整数类

  1 #include <iostream>
  2 #include <string>
  3 #include <iomanip>
  4 #include <algorithm>
  5 #include <cstring>
  6 using namespace std;
  7 #define MAXN 9999 // 大数类里面的数组中每个单元的最大正整数
  8 #define MAXSIZE 10
  9 #define DLEN 4 // 对应于MAXN的大小
 10 #define MAX_LEN 500
 11 class BigNum{
 12 public:
 13     int a[MAX_LEN];    //可以控制大数的位数
 14     int len;       //大数长度
 15 public:
 16     BigNum(){len = 1; memset(a,0,sizeof(a));} //构造函数
 17     BigNum(const int);   //将一个int类型的变量转化为大数
 18     BigNum(const char*); //将一个字符串类型的变量转化为大数
 19     BigNum(const BigNum&);  //拷贝构造函数
 20     BigNum &operator =(const BigNum&);//重载赋值运算符，大数之间进行赋值运算
 21 
 22     friend istream& operator >>(istream&,BigNum&);//重载输入运算符
 23     friend ostream& operator <<(ostream&,BigNum&);//重载输出运算符
 24 
 25     BigNum operator +(const BigNum&) const;//重载加法运算符，两个大数之间的相加运算
 26     BigNum operator -(const BigNum&) const;//重载减法运算符，两个大数之间的相减运算
 27     BigNum operator *(const BigNum&) const;//重载乘法运算符，两个大数之间的相乘运算
 28     BigNum operator /(const int&) const;//重载除法运算符，大数对一个整数进行相除运算
 29 
 30     BigNum operator ^(const int&) const;//大数的n次方运算
 31     int    operator %(const int&) const;//大数对一个int类型的变量进行取模运算
 32     bool   operator >(const BigNum& T)const;//大数和另一个大数的大小比较
 33     bool   operator >(const int& t)const; //大数和一个int类型的变量的大小比较
 34 
 35     void print(); //输出大数
 36 };
 37 BigNum::BigNum(const int b){//将一个int类型的变量转化为大数
 38     int c,d = b;
 39     len = 0;
 40     memset(a,0,sizeof(a));
 41     while(d > MAXN){
 42         c = d - (d / (MAXN + 1)) * (MAXN + 1);
 43         d = d / (MAXN + 1);
 44         a[len++] = c;
 45     }
 46     a[len++] = d;
 47 }
 48 BigNum::BigNum(const char*s){//将一个字符串类型的变量转化为大数
 49     int t,k,index,l,i;
 50     memset(a,0,sizeof(a));
 51     l = strlen(s);
 52     len = l / DLEN;
 53     if(l % DLEN) len++;
 54     index = 0;
 55     for(i = l - 1 ; i >= 0 ; i -= DLEN){
 56         t = 0;
 57         k = i - DLEN + 1;
 58         if(k < 0) k = 0;
 59         for(int j = k ; j <= i ; j++)
 60             t = t * 10 + s[j] - ‘0‘;
 61         a[index++] = t;
 62     }
 63 }
 64 BigNum::BigNum(const BigNum& T) : len(T.len){//拷贝构造函数
 65     int i;
 66     memset(a,0,sizeof(a));
 67     for(i = 0 ; i < len ; i++)
 68         a[i] = T.a[i];
 69 }
 70 BigNum& BigNum::operator =(const BigNum& n){//重载赋值运算符，大数之间进行赋值运算
 71     int i;
 72     len = n.len;
 73     memset(a,0,sizeof(a));
 74     for(i = 0 ; i < len ; i++)
 75         a[i] = n.a[i];
 76     return *this;
 77 }
 78 istream& operator >>(istream& in,BigNum& b){//重载输入运算符
 79     char ch[MAXSIZE * 4];
 80     int i = -1;
 81     in >> ch;
 82     int l = strlen(ch);
 83     int cnt = 0,sum = 0;
 84     for(i = l - 1 ; i >= 0 ; ){
 85         sum = 0;
 86         int t = 1;
 87         for(int j = 0 ; j < 4 && i >= 0 ; j++,i--,t *= 10)
 88             sum += (ch[i] - ‘0‘) * t;
 89         b.a[cnt] = sum;
 90         cnt++;
 91     }
 92     b.len = cnt++;
 93     return in;
 94 }
 95 ostream& operator <<(ostream& out,BigNum& b){//重载输出运算符
 96     int i;
 97     cout << b.a[b.len - 1];
 98     for(i = b.len - 2 ; i >= 0 ; i--){
 99         cout.width(DLEN);
100         cout.fill(‘0‘);
101         cout << b.a[i];
102     }
103     return out;
104 }
105 BigNum BigNum::operator +(const BigNum& T) const{//两个大数之间的相加运算
106     BigNum t(*this);
107     int i,big;      //位数
108     big = T.len > len ? T.len : len;
109     for(i = 0 ; i < big ; i++){
110         t.a[i] += T.a[i];
111         if(t.a[i] > MAXN){
112             t.a[i + 1]++;
113             t.a[i] -= MAXN+1;
114         }
115     }
116     if(t.a[big] != 0) t.len = big + 1;
117     else t.len = big;
118     return t;
119 }
120 BigNum BigNum::operator -(const BigNum& T) const{  //两个大数之间的相减运算
121     int i,j,big;
122     bool flag;
123     BigNum t1,t2;
124     if(*this > T){
125         t1 = *this;
126         t2 = T;
127         flag = 0;
128     }
129     else{
130         t1 = T;
131         t2 = *this;
132         flag = 1;
133     }
134     big = t1.len;
135     for(i = 0 ; i < big ; i++)
136         if(t1.a[i] < t2.a[i]){
137             j = i + 1;
138             while(t1.a[j] == 0) j++;
139             t1.a[j--]--;
140             while(j > i) t1.a[j--] += MAXN;
141             t1.a[i] += MAXN + 1 - t2.a[i];
142         }
143         else t1.a[i] -= t2.a[i];
144     t1.len = big;
145     while(t1.a[len - 1] == 0 && t1.len > 1){
146         t1.len--;
147         big--;
148     }
149     if(flag) t1.a[big - 1] = 0 - t1.a[big - 1];
150     return t1;
151 }
152 BigNum BigNum::operator *(const BigNum& T) const{//两个大数之间的相乘运算
153     BigNum ret;
154     int i,j,up;
155     int temp,temp1;
156     for(i = 0 ; i < len ; i++){
157         up = 0;
158         for(j = 0 ; j < T.len ; j++){
159             temp = a[i] * T.a[j] + ret.a[i + j] + up;
160             if(temp > MAXN){
161                 temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
162                 up = temp / (MAXN + 1);
163                 ret.a[i + j] = temp1;
164             }
165             else{
166                 up = 0;
167                 ret.a[i + j] = temp;
168             }
169         }
170         if(up != 0) ret.a[i + j] = up;
171     }
172     ret.len = i + j;
173     while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--;
174     return ret;
175 }
176 BigNum BigNum::operator /(const int& b) const{//大数对一个整数进行相除运算
177     BigNum ret;
178     int i,down = 0;
179     for(i = len - 1 ; i >= 0 ; i--){
180         ret.a[i] = (a[i] + down * (MAXN + 1)) / b;
181         down = a[i] + down * (MAXN + 1) - ret.a[i] * b;
182     }
183     ret.len = len;
184     while(ret.a[ret.len - 1] == 0 && ret.len > 1)
185         ret.len--;
186     return ret;
187 }
188 int BigNum::operator %(const int& b) const{//大数对一个int类型的变量进行取模运算
189     int i,d = 0;
190     for (i = len - 1 ; i >= 0 ; i--)
191         d = ((d * (MAXN + 1)) % b + a[i]) % b;
192     return d;
193 }
194 BigNum BigNum::operator ^(const int& n) const{    //大数的n次方运算
195     BigNum t,ret(1);
196     int i;
197     if(n < 0) exit(-1);
198     if(n == 0) return 1;
199     if(n == 1) return *this;
200     int m = n;
201     while(m > 1){
202         t = *this;
203         for(i = 1 ; i << 1 <= m ; i <<= 1) t = t * t;
204         m -= i;
205         ret = ret * t;
206         if(m == 1) ret = ret * (*this);
207     }
208     return ret;
209 }
210 bool BigNum::operator >(const BigNum& T) const{   //大数和另一个大数的大小比较
211     int ln;
212     if(len > T.len) return true;
213     else if(len == T.len){
214         ln = len - 1;
215         while(a[ln] == T.a[ln] && ln >= 0) ln--;
216         if(ln >= 0 && a[ln] > T.a[ln]) return true;
217         else return false;
218     }
219     else return false;
220 }
221 bool BigNum::operator >(const int& t) const{//大数和一个int类型的变量的大小比较
222     BigNum b(t);
223     return *this > b;
224 }
225 void BigNum::print(){    //输出大数
226     int i;
227     cout << a[len - 1];
228     for(i = len - 2 ; i >= 0 ; i--){
229         cout.width(DLEN);
230         cout.fill(‘0‘);
231         cout << a[i];
232     }
233     cout << endl;
234 }
235 int main(void){
236     BigNum val;
237     val = "123456789101112131415161718192021222324252627282930";
238     val.print();
239     val = "10"; BigNum val1 = "1234";
240     BigNum val2 = "11";
241     BigNum tmp = val + val1;
242     tmp.print();
243     tmp = val * val1;
244     tmp.print();
245     tmp = val1 / 10;
246     tmp.print();
247     tmp = val2 ^ 2;
248     tmp.print();
249     return 0;
250 }