大数模板（正整数）
发布时间：2020-12-14 04:18:44 所属栏目：大数据 来源：网络整理
导读：找大数模板的时候发现大部分模板功能不全，或者代码过于冗长，或者函数实现复杂度较高。 于是在现有模板的基础上整理以及优化，写出了下面的大数模板。 一、基本功能 支持int，long long，string和C字符串拷贝构造。 支持常规四则运算和求模运算，但不支持大
|
找大数模板的时候发现大部分模板功能不全，或者代码过于冗长，或者函数实现复杂度较高。 于是在现有模板的基础上整理以及优化，写出了下面的大数模板。 一、基本功能支持int，long long，string和C字符串拷贝构造。 支持常规四则运算和求模运算，但不支持大数相除以及大数求模。 重载了流，支持cin，cout输入输出。 支持自增，自减，左移，右移，比较，支持+=等形式。 除法和求模只支持对int或者long long类型，不是我懒，模拟除法和求模太烧脑，而且时空复杂度都比较高。 特别的重载了^，并非异或，而是求幂运算。 函数能优化的地方基本都优化了，特别的是用int数组存储，每位最大存储9999，降低空间复杂度。 每位存储位数，最大长度等都可以自行更改。 二、函数定义
定义了以上函数。 ? 1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define MAXN 9999 5 #define MAXSIZE 500 //最大长度 6 #define DLEN 4 7 8 class BigNum 9 { 10 private: 11 int a[210]; //控制大数的位数 12 int len; //长度 13 public: 14 BigNum(){ len = 1;memset(a,0,sizeof(a)); } //构造函数 15 void XD(); 16 BigNum(const int); 17 BigNum(const long long int); 18 BigNum(const char*); 19 BigNum(const string &); 20 BigNum(const BigNum &); //拷贝构造函数 21 BigNum &operator = (const BigNum &); //重载赋值运算符 22 BigNum &operator = (const int &); 23 BigNum &operator = (const long long int &); 24 25 friend istream& operator>>(istream&,BigNum&); //重载输入运算符 26 friend ostream& operator<<(ostream&,BigNum&); //重载输出运算符 27 28 BigNum operator << (const int &) const; 29 BigNum operator >> (const int &) const; 30 31 BigNum operator + (const BigNum &) const; //重载加法运算符，大数加大数 32 BigNum operator - (const BigNum &) const; //重载减法运算符，大数减大数 33 BigNum operator * (const BigNum &) const; //重载乘法运算符，大数乘大数 34 BigNum operator / (const int &) const; //重载除法运算符，大数除整数 35 BigNum operator ^ (const int &) const; //大数的n次方 36 int operator % (const int &) const; //大数对int取模 37 bool operator > (const BigNum& b)const; //重载大于 38 bool operator < (const BigNum& b) const; //重载小于 39 40 BigNum operator + (const int& b) {BigNum t = b; *this = *this+t; return *this;} 41 BigNum operator - (const int& b) {BigNum t = b; *this = *this-t; return *this;} 42 BigNum operator * (const int& b) {BigNum t = b; *this = (*this)*t; return *this;} 43 bool operator < (const int& b) const; 44 bool operator > (const int& b) const; 45 46 bool operator <= (const BigNum& b) const{return !(b < *this);} 47 bool operator >= (const BigNum& b) const{return !(*this < b);} 48 bool operator != (const BigNum& b) const{return b < *this || *this < b;} 49 bool operator == (const BigNum& b) const{return !(b < *this) && !(b > *this);} 50 51 bool operator >= (const int& b) const{return !(*this < b);} 52 bool operator <= (const int& b) const{return *this < b || *this == b;} 53 bool operator != (const int& b) const{return *this > b || *this < b;} 54 bool operator == (const int& b) const{return !(*this != b);} 55 56 BigNum& operator += (const BigNum& b) {*this = *this+b; return *this;} 57 BigNum& operator -= (const BigNum& b) {*this = *this-b; return *this;} 58 BigNum& operator *= (const BigNum& b) {*this = *this*b; return *this;} 59 BigNum& operator /= (const int& b) {*this = *this/b; return *this;} 60 BigNum& operator %= (const int& b) {*this = *this/b; return *this;} 61 BigNum& operator += (const int& b) {*this = *this+b; return *this;} 62 BigNum& operator -= (const int& b) {*this = *this-b; return *this;} 63 BigNum& operator *= (const int& b) {*this = *this*b; return *this;} 64 BigNum& operator ^= (const int& b) {*this = *this^b; return *this;} 65 66 //下面是关于long long的重载 不用可以删除相关仿函数 67 BigNum operator + (const long long int& b) {BigNum t = b; *this = *this+t; return *this;} 68 BigNum operator - (const long long int& b) {BigNum t = b; *this = *this-t; return *this;} 69 BigNum operator * (const long long int& b) {BigNum t = b; *this = (*this)*t; return *this;} 70 BigNum operator / (const long long int& b) const; 71 long long int operator % (const long long int& b) const; 72 bool operator > (const long long int& b) const; 73 bool operator < (const long long int& b) const; 74 75 BigNum& operator /= (const long long int& b) {*this = *this/b; return *this;} 76 BigNum& operator %= (const long long int& b) {*this = *this/b; return *this;} 77 BigNum& operator += (const long long int& b) {*this = *this+b; return *this;} 78 BigNum& operator -= (const long long int& b) {*this = *this-b; return *this;} 79 BigNum& operator *= (const long long int& b) {*this = *this*b; return *this;} 80 81 bool operator >= (const long long int& b) const{return !(*this < b);} 82 bool operator <= (const long long int& b) const{return *this < b || *this == b;} 83 bool operator != (const long long int& b) const{return *this > b || *this < b;} 84 bool operator == (const long long int& b) const{return !(*this != b);} 85 86 BigNum operator ++ (int) {BigNum t = *this; *this += 1; return t;} 87 BigNum operator -- (int) {BigNum t = *this; *this -= 1; return t;} 88 BigNum& operator -- () {*this -= 1; return *this;} 89 BigNum& operator ++ () {*this += 1; return *this;} 90 91 BigNum& operator <<= (const int& b) {*this = *this << b; return *this;} 92 BigNum& operator >>= (const int& b) {*this = *this >> b; return *this;} 93 94 void print(); //输出大数 95 int Size(); //返回大数长度 96 int the_first(); //返回第一个数字 97 int the_last(); //返回最后一位数字 98 int to_int(); //转化为整数 99 long long int to_long(); 100 string to_String(); //转化为string类型 101 //char* to_char(); 102 }; 103 104 BigNum operator + (const int& a,BigNum& b) {return b+a;} 105 BigNum operator + (const long long int& a,BigNum& b) {return b+a;} 106 BigNum operator - (const int& a,BigNum& b) {BigNum t(a); t -= b; return t;} 107 BigNum operator - (const long long int& a,BigNum& b) {BigNum t(a); t -= b; return t;} 108 BigNum operator * (const int& a,BigNum& b) {return b*a;} 109 BigNum operator * (const long long int& a,BigNum& b) {return b*a;} 110 bool operator < (const int& a,BigNum& b) {return b>a;} 111 bool operator < (const long long int& a,BigNum& b) {return b>a;} 112 bool operator > (const int& a,BigNum& b) {return b<a;} 113 bool operator > (const long long int& a,BigNum& b) {return b<a;} 114 bool operator <= (const int& a,BigNum& b) {return b>=a;} 115 bool operator <= (const long long int& a,BigNum& b) {return b>=a;} 116 bool operator >= (const int& a,BigNum& b) {return b<=a;} 117 bool operator >= (const long long int& a,BigNum& b) {return b<=a;} 118 bool operator == (const int& a,BigNum& b) {return b==a;} 119 bool operator == (const long long int& a,BigNum& b) {return b==a;} 120 bool operator != (const int& a,BigNum& b) {return b!=a;} 121 bool operator != (const long long int& a,BigNum& b) {return b!=a;} 122 123 BigNum::BigNum(const int b) //将一个int类型的变量转化为大数 124 { 125 int c,d = b; 126 len = 0; 127 memset(a,sizeof(a)); 128 while(d > MAXN){ 129 c = d - (d / (MAXN+1)) * (MAXN+1); 130 d = d / (MAXN+1); 131 a[len++] = c; 132 } 133 a[len++] = d; 134 } 135 BigNum::BigNum(const long long int b) 136 { 137 long long int c,d = b; 138 len = 0; 139 memset(a,sizeof(a)); 140 while(d > MAXN){ 141 c = d - (d / (MAXN+1)) * (MAXN+1); 142 d = d / (MAXN+1); 143 a[len++] = c; 144 } 145 a[len++] = d; 146 } 147 BigNum::BigNum(const string& s) 148 { 149 int t,k,index,l,i; 150 memset(a,sizeof(a)); 151 l = s.size(); 152 len = l/DLEN; 153 if(l%DLEN) 154 len++; 155 index = 0; 156 for(i = l-1; i >=0 ;i -= DLEN){ 157 t = 0; 158 k = i-DLEN+1; 159 if(k < 0) k = 0; 160 for(int j = k; j <= i; j++) 161 t = t*10 + s[j]-‘0‘; 162 a[index++] = t; 163 } 164 } 165 BigNum::BigNum(const char* s) //将一个字符串类型的变量转化为大数 166 { 167 int t,i; 168 memset(a,sizeof(a)); 169 l = strlen(s); 170 len = l/DLEN; 171 if(l%DLEN) 172 len++; 173 index = 0; 174 for(i = l-1; i >= 0; i -= DLEN){ 175 t = 0; 176 k = i - DLEN + 1; 177 if(k < 0) k = 0; 178 for(int j = k; j <= i; j++) 179 t = t*10 + s[j] - ‘0‘; 180 a[index++] = t; 181 } 182 } 183 BigNum::BigNum(const BigNum & b) : len(b.len) //拷贝构造函数 184 { 185 memset(a,sizeof(a)); 186 for(int i = 0 ; i < len ; i++) 187 a[i] = b.a[i]; 188 } 189 BigNum & BigNum::operator = (const BigNum& n) //重载赋值运算符，大数之间进行赋值运算 190 { 191 len = n.len; 192 memset(a,sizeof(a)); 193 for(int i = 0 ; i < len ; i++) 194 a[i] = n.a[i]; 195 return *this; 196 } 197 BigNum & BigNum::operator = (const int& num) 198 { 199 BigNum t(num); 200 *this = t; 201 return *this; 202 } 203 BigNum & BigNum::operator = (const long long int& num) 204 { 205 BigNum t(num); 206 *this = t; 207 return *this; 208 } 209 void XD() 210 { 211 cout << "A hidden egg! Good luck for u!" << endl; 212 } 213 istream& operator >> (istream & in,BigNum & b) //重载输入运算符 214 { 215 char ch[MAXSIZE*4]; 216 int i = -1; 217 in>>ch; 218 int l = strlen(ch); 219 int cnt = 0,sum = 0; 220 for(i = l-1; i >= 0; ){ 221 sum = 0; 222 int t = 1; 223 for(int j = 0; j < 4 && i >= 0; j++,i--,t *= 10) 224 sum += (ch[i]-‘0‘)*t; 225 b.a[cnt] = sum; 226 cnt++; 227 } 228 b.len = cnt++; 229 return in; 230 231 } 232 ostream& operator << (ostream& out,BigNum& b) //重载输出运算符 233 { 234 int i; 235 cout << b.a[b.len - 1]; 236 for(i = b.len - 2 ; i >= 0 ; i--){ 237 cout.width(DLEN); 238 cout.fill(‘0‘); 239 cout << b.a[i]; 240 } 241 return out; 242 } 243 244 BigNum BigNum::operator << (const int& b) const 245 { 246 int temp = 1; 247 for(int i = 0; i < b; i++) 248 temp *= 2; 249 BigNum t = (*this) * temp; 250 return t; 251 } 252 BigNum BigNum::operator >> (const int& b) const 253 { 254 int temp = 1; 255 for(int i = 0; i < b; i++) 256 temp *= 2; 257 BigNum t = (*this) / temp; 258 return t; 259 } 260 261 BigNum BigNum::operator + (const BigNum& b) const //两个大数之间的相加运算 262 { 263 BigNum t(*this); 264 int i,big; 265 big = b.len > len ? b.len : len; 266 for(i = 0 ; i < big ; i++){ 267 t.a[i] += b.a[i]; 268 if(t.a[i] > MAXN){ 269 t.a[i + 1]++; 270 t.a[i] -=MAXN+1; 271 } 272 } 273 if(t.a[big] != 0) 274 t.len = big + 1; 275 else 276 t.len = big; 277 return t; 278 } 279 BigNum BigNum::operator - (const BigNum& b) const //两个大数之间的相减运算 280 { 281 int i,j,big; 282 bool flag; 283 BigNum t1,t2; 284 if(*this>b){ 285 t1 = *this; 286 t2 = b; 287 flag = 0; 288 } 289 else{ 290 t1 = b; 291 t2 = *this; 292 flag = 1; 293 } 294 big = t1.len; 295 for(i = 0 ; i < big ; i++){ 296 if(t1.a[i] < t2.a[i]){ 297 j = i + 1; 298 while(t1.a[j] == 0) 299 j++; 300 t1.a[j--]--; 301 while(j > i) 302 t1.a[j--] += MAXN; 303 t1.a[i] += MAXN + 1 - t2.a[i]; 304 } 305 else 306 t1.a[i] -= t2.a[i]; 307 } 308 t1.len = big; 309 while(t1.a[t1.len - 1] == 0 && t1.len > 1){ 310 t1.len--; 311 big--; 312 } 313 if(flag) 314 t1.a[big-1] = 0-t1.a[big-1]; 315 return t1; 316 } 317 318 BigNum BigNum::operator * (const BigNum& b) const //两个大数之间的相乘运算 319 { 320 BigNum ret; 321 int i,up; 322 int temp,temp1; 323 for(i = 0 ; i < len ; i++){ 324 up = 0; 325 for(j = 0 ; j < b.len ; j++){ 326 temp = a[i] * b.a[j] + ret.a[i + j] + up; 327 if(temp > MAXN){ 328 temp1 = temp - temp / (MAXN + 1) * (MAXN + 1); 329 up = temp / (MAXN + 1); 330 ret.a[i + j] = temp1; 331 } 332 else{ 333 up = 0; 334 ret.a[i + j] = temp; 335 } 336 } 337 if(up != 0) ret.a[i + j] = up; 338 } 339 ret.len = i + j; 340 while(ret.a[ret.len - 1] == 0 && ret.len > 1) 341 ret.len--; 342 return ret; 343 } 344 BigNum BigNum::operator / (const int& b) const //大数对int相除 345 { 346 BigNum ret; 347 int i,down = 0; 348 for(i = len - 1 ; i >= 0 ; i--){ 349 ret.a[i] = (a[i] + down * (MAXN + 1)) / b; 350 down = a[i] + down * (MAXN + 1) - ret.a[i] * b; 351 } 352 ret.len = len; 353 while(ret.a[ret.len - 1] == 0 && ret.len > 1) 354 ret.len--; 355 return ret; 356 } 357 int BigNum::operator % (const int& b) const //大数对int取模 358 { 359 int i,d=0; 360 for (i = len-1; i>=0; i--){ 361 d = ((d * (MAXN+1))% b + a[i])% b; 362 } 363 return d; 364 } 365 BigNum BigNum::operator / (const long long int& b) const //大数对long long相除 366 { 367 BigNum ret; 368 int i,down = 0; 369 for(i = len - 1 ; i >= 0 ; i--){ 370 ret.a[i] = (a[i] + down * (MAXN + 1)) / b; 371 down = a[i] + down * (MAXN + 1) - ret.a[i] * b; 372 } 373 ret.len = len; 374 while(ret.a[ret.len - 1] == 0 && ret.len > 1) 375 ret.len--; 376 return ret; 377 } 378 long long int BigNum::operator % (const long long int& b) const //大数对long long取模 379 { 380 int i; 381 long long int d=0; 382 for (i = len-1; i>=0; i--){ 383 d = ((d * (MAXN+1))% b + a[i])% b; 384 } 385 return d; 386 } 387 BigNum BigNum::operator^(const int& n) const //大数的n次方运算 388 { 389 BigNum t,ret(1); 390 int i; 391 if(n < 0) return 0; 392 if(n == 0) 393 return 1; 394 if(n == 1) 395 return *this; 396 int m = n; 397 while(m > 1){ 398 t =* this; 399 for(i = 1; (i<<1) <= m;i <<= 1) 400 t = t*t; 401 m-=i; 402 ret=ret*t; 403 if(m == 1) ret = ret * (*this); 404 } 405 return ret; 406 } 407 408 bool BigNum::operator>(const BigNum& b) const //大数和另一个大数的大小比较 409 { 410 int tot; 411 if(len > b.len) 412 return true; 413 else if(len == b.len){ 414 tot = len - 1; 415 while(a[tot] == b.a[tot] && tot >= 0) 416 tot--; 417 if(tot >= 0 && a[tot] > b.a[tot]) 418 return true; 419 else 420 return false; 421 } 422 else 423 return false; 424 } 425 426 bool BigNum::operator < (const BigNum& b) const{ 427 int tot; 428 if(len > b.len) 429 return false; 430 else if(len == b.len){ 431 tot = len - 1; 432 while(a[tot] == b.a[tot] && tot >= 0) 433 tot--; 434 if(tot >= 0 && a[tot] > b.a[tot]) 435 return false; 436 else 437 return true; 438 } 439 else 440 return true; 441 } 442 443 bool BigNum::operator > (const int& b) const //大数和int大小比较 444 { 445 BigNum t(b); 446 return *this>t; 447 } 448 449 bool BigNum::operator < (const int& b) const 450 { 451 BigNum t(b); 452 return *this<t; 453 } 454 bool BigNum::operator > (const long long int& b) const //大数和long long大小比较 455 { 456 BigNum t(b); 457 return *this>t; 458 } 459 460 bool BigNum::operator < (const long long int& b) const 461 { 462 BigNum t(b); 463 return *this<t; 464 } 465 466 void BigNum::print() //输出大数 467 { 468 int i; 469 cout << a[len - 1]; 470 for(i = len-2; i >= 0; i--){ 471 cout.width(DLEN); 472 cout.fill(‘0‘); 473 cout << a[i]; 474 } 475 cout << endl; 476 } 477 int BigNum::Size() 478 { 479 int t = a[len-1],cnt = 0; 480 while(t){ t /= 10; cnt++; } 481 cnt += (len-1)*4; 482 return cnt; 483 } 484 int BigNum::the_first() 485 { 486 int t = a[len-1]; 487 while(t > 10){ t /= 10;} 488 return t; 489 } 490 int BigNum::the_last() 491 { 492 int t = a[0]; 493 return t%10; 494 } 495 int BigNum::to_int() 496 { 497 int i,num; 498 num = a[len-1]; 499 for(i = len-2; i >= 0; i--) 500 num = num*(MAXN+1) + a[i]; 501 return num; 502 } 503 long long int BigNum::to_long() 504 { 505 int i; 506 long long int num; 507 num = a[len-1]; 508 for(i = len-2; i >= 0; i--) 509 num = num*(MAXN+1) + a[i]; 510 return num; 511 } 512 string BigNum::to_String() 513 { 514 int i; 515 string s = "",tp = ""; 516 s += to_string(a[len-1]); 517 for(i = len-2; i >= 0; i--){ 518 tp = to_string(a[i]); 519 int tot = tp.size(); 520 tp.insert(tp.begin(),4-tot,‘0‘); 521 s = s + tp; 522 } 523 return s; 524 } 525 int main() 526 { 527 BigNum a; 528 } ? 关于支持位运算的二进制存储大数模板，以后有空的化也弄一个出来吧。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |