思想：
由于编程语言提供的基本数值数据类型表示的数值范围有限，不能满足较大规模的高精度数值计算，因此需要利用其他方法实现高精度数值的计算，于是产生了大数运算。大数运算主要有加、减、乘三种方法。
考虑用数组存储整数，并模拟手算的方法进行加减乘除四则运算。为了能像int一样方便的使用大整数，可以定义结构体，大整数类。
结构体biginteger可用于存储高精度非负整数。这里存储的方案是每8位存在一个数组的元素里，所用base为1亿，也就是1e8这么多，从低位向高位存储
比如：123456789123456789 存储为| 23456789 |34567891 |12|在一个数组中。
大数结构体：
代码：
1 struct biginteger
2 {
3 static const int base = 100000000;
4 static const int width = 8;
5 vector<int> s;
6
7 biginteger(long long num = 0) {*this = num;}//构造函数
8 biginteger operator=(long long num)//赋值运算符
9 {
10 s.clear();
11 do
12 {
13 s.push_back(num%base);
14 num /= base;
15 }while(num>0);
16 return *this;
17 }
18 biginteger operator=(const string& str)//赋值运算符
19 {
20 s.clear();
21 int x,len = (str.length()-1)/width+1;
22 for(int i = 0;i<len;i++)
23 {
24 int end = str.length()-i*width;
25 int start = max(0,end-width);
26 sscanf(str.substr(start,end-start).c_str(),"%d",&x);
27 s.push_back(x);
28 }
29 return *this;
30 }
31 }
大数类的输入输出运算符重载：
还可以重载“<<”和“>>”运算符，使用方便
代码：
1 friend ostream& operator<<(ostream &out,const biginteger& x)
2 {
3 out << x.s.back();
4 for(int i = x.s.size()-2;i>=0;i--)
5 {
6 char buf[20];
7 sprintf(buf,"%8d",x.s[i]);
8 for(int j = 0;j<strlen(buf);j++)
9 {
10 out << buf[j];
11 }
12 }
13 return out;
14 }
15 friend istream& operator>>(istream &in,biginteger& x)
16 {
17 string s;
18 if(!(in >> s)) return in;
19 x = s;
20 return in;
21 }
由于c++的继承机制，现在istream类和ostream类都可以使用它来输出输入大整数了
上述代码中base是静态成员变量，属于这个类型而不属于静态对象，用static修饰
大数类的加法：
1 biginteger operator+(const biginteger& b) const
2 {
3 biginteger c;
4 c.s.clear();
5 for(int i = 0,g = 0;;i++)
6 {
7 if(g==0&&i>=s.size()&&i>=b.s.size())//当进位为零并且加完了，退出。如果加完了进位不为零，就继续把进位补上，在退出
8 {
9 break;
10 }
11 int x = g;//g为进位数，满一个base才向下进一位
12 if(i<s.size()) x+=s[i];
13 if(i<b.s.size()) x+=b.s[i];
14 c.s.push_back(x%base);//进位后本位上的数
15 g = x/base;//更新进位数
16 }
17 return c;
18 }
19 biginteger operator+=(const biginteger& b)
20 {
21 *this = *this+b;
22 return *this;
23 }
大数类的比较：
一开始就比较两个数的位数，不相等直接返回，否则从后往前比（低位在前）。注意这是在没有前导零的情况下才能这样比，有前导零最后一位还要单独处理。
代码：
bool operator<(const biginteger& b) const
{
if(s.size()!=b.s.size())
{
return s.size()<b.s.size();
}
for(int i = s.size()-1;i>=0;i--)
{
if(s[i]!=b.s[i])
{
return s[i]<b.s[i];
}
}
return false;
}
bool operator>(const biginteger& b) const
{
return b<*this;
}
bool operator<=(const biginteger& b) const
{
return !(b<*this);
}
bool operator>=(const biginteger& b) const
{
return !(*this<b);
}
bool operator!=(const biginteger& b) const
{
return (b< *this||*this<b);
}
bool operator==(const biginteger& b) const
{
return !(b<*this)&&!(*this<b);
}
这时依赖比较运算符的容器函数就可以支持大整数类了。
代码汇总：
1 #include <cstdio>
2 #include <iostream>
3 #include <vector>
4 #include <cstring>
5 #include<set>
6 #include<map>
7 using namespace std;
8 struct biginteger
9 {
10 static const int base = 100000000;
11 static const int width = 8;
12 vector<int> s;
13
14 biginteger(long long num = 0) {*this = num;}//构造函数
15 biginteger operator=(long long num)//赋值运算符
16 {
17 s.clear();
18 do
19 {
20 s.push_back(num%base);
21 num /= base;
22 }while(num>0);
23 return *this;
24 }
25 biginteger operator=(const string& str)//赋值运算符
26 {
27 s.clear();
28 int x,len = (str.length()-1)/width+1;
29 for(int i = 0;i<len;i++)
30 {
31 int end = str.length()-i*width;
32 int start = max(0,end-width);
33 sscanf(str.substr(start,end-start).c_str(),"%d",&x);
34 s.push_back(x);
35 }
36 return *this;
37 }
38 friend ostream& operator<<(ostream &out,const biginteger& x)
39 {
40 out << x.s.back();
41 for(int i = x.s.size()-2;i>=0;i--)
42 {
43 char buf[20];
44 sprintf(buf,"%8d",x.s[i]);
45 for(int j = 0;j<strlen(buf);j++)
46 {
47 out << buf[j];
48 }
49 }
50 return out;
51 }
52 friend istream& operator>>(istream &in,biginteger& x)
53 {
54 string s;
55 if(!(in >> s)) return in;
56 x = s;
57 return in;
58 }
59
60 bool operator<(const biginteger& b) const
61 {
62 if(s.size()!=b.s.size())
63 {
64 return s.size()<b.s.size();
65 }
66 for(int i = s.size()-1;i>=0;i--)
67 {
68 if(s[i]!=b.s[i])
69 {
70 return s[i]<b.s[i];
71 }
72 }
73 return false;
74 }
75 bool operator>(const biginteger& b) const
76 {
77 return b<*this;
78 }
79 bool operator<=(const biginteger& b) const
80 {
81 return !(b<*this);
82 }
83 bool operator>=(const biginteger& b) const
84 {
85 return !(*this<b);
86 }
87 bool operator!=(const biginteger& b) const
88 {
89 return (b< *this||*this<b);
90 }
91 bool operator==(const biginteger& b) const
92 {
93 return !(b<*this)&&!(*this<b);
94 }
95 biginteger operator+(const biginteger& b) const
96 {
97 biginteger c;
98 c.s.clear();
99 for(int i = 0,g = 0;;i++)
100 {
101 if(g==0&&i>=s.size()&&i>=b.s.size())//当进位为零并且加完了，退出。如果加完了进位不为零，就继续把进位补上，在退出
102 {
103 break;
104 }
105 int x = g;//g为进位数，满一个base才向下进一位
106 if(i<s.size()) x+=s[i];
107 if(i<b.s.size()) x+=b.s[i];
108 c.s.push_back(x%base);//进位后本位上的数
109 g = x/base;//更新进位数
110 }
111 return c;
112 }
113 biginteger operator+=(const biginteger& b)
114 {
115 *this = *this+b;
116 return *this;
117 }
118 };
119 set<biginteger> s;
120 map<biginteger, int> m;
121 int main()
122 {
123 biginteger y;
124 biginteger x = y;
125 biginteger z = 123;
126
127 biginteger a, b;
128 cin >> a >> b;
129 cout << a + b << "\n";
130 cout << biginteger::base << "\n";
131 return 0;
132 }
参考代码：https://github.com/aoapc-book/aoapc-bac2nd/blob/master/ch5/biginteger.cpp
参考文章：
关于sscanf，sprintf的使用：
https://www.runoob.com/cprogramming/c-function-sscanf.html
https://www.runoob.com/cprogramming/c-function-sprintf.html
