大整數類 - acm1314－IT工程師數位筆記本

文章出處

大整數類又叫高精度。就是求大數的四則運算的算法，（其實就是模擬小學生算數的方法，什么？你不會，那你還不如小學生，哈哈！）。在這里只貼加法運算符的重載，其他的運算符與加法類似。閑言少敘，直接上代碼（小聲告訴你，里面用了幾個庫函數和STL，嘿嘿！！！）。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 #include<iostream>
 5 using namespace std;
 6 
 7 struct BigInteger {         // 定義大整數結構體 
 8   static const int BASE = 100000000; //8位8位的計算 
 9   static const int WIDTH = 8;
10   vector<int> s;                     //用來存8位8位的片段 
11 
12   BigInteger(long long num = 0) { *this = num; } // 構造函數 
13   BigInteger operator = (long long num) { // 賦值運算符。 
14     s.clear();
15     do {
16       s.push_back(num % BASE);
17       num /= BASE;
18     } while(num > 0);
19     return *this;
20   }
21   BigInteger operator = (const string& str) { //賦值運算符 
22     s.clear();
23     int x, len = (str.length() - 1) / WIDTH + 1;
24     for(int i = 0; i < len; i++) {
25       int end = str.length() - i*WIDTH;
26       int start = max(0, end - WIDTH);
27       sscanf(str.substr(start, end-start).c_str(), "%d", &x);//把字符串轉化為8為的整數賦值給 x  
28       s.push_back(x);
29     }
30     return *this;
31   }
32   BigInteger operator + (const BigInteger& b) const {        //計算加法。g表示進位。 
33     BigInteger c;
34     c.s.clear();
35     for(int i = 0, g = 0; ; i++) {
36       if(g == 0 && i >= s.size() && i >= b.s.size()) break;
37       int x = g;
38       if(i < s.size()) x += s[i];
39       if(i < b.s.size()) x += b.s[i];
40       c.s.push_back(x % BASE);
41       g = x / BASE;
42     }
43     return c;
44   }
45 };
46 
47 ostream& operator << (ostream &out, const BigInteger& x) {
48   out << x.s.back();
49   for(int i = x.s.size()-2; i >= 0; i--) {
50     char buf[20];
51     sprintf(buf, "%08d", x.s[i]);
52     for(int j = 0; j < strlen(buf); j++) out << buf[j];
53   }
54   return out;
55 }
56 
57 istream& operator >> (istream &in, BigInteger& x) {
58   string s;
59   if(!(in >> s)) return in;
60   x = s;
61   return in;
62 }
63 
64 #include<set>
65 #include<map>
66 set<BigInteger> s;
67 map<BigInteger, int> m;
68 
69 int main() {
70   BigInteger y;
71   BigInteger x = y;
72   BigInteger z = 123;
73 
74   BigInteger a, b;
75   cin >> a >> b;
76   cout << a + b << "\n";
77   cout << BigInteger::BASE << "\n";
78   return 0;
79 }