STL初步——大整数_stl 大数

大整数类

1.源代码

//2020年4月6日11:25:19
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>//max和min函数的头文件

using namespace std;

struct BigInteger{
	static const int BASE = 100000000;//大整数每位的最大值 相当于10
	static const int WIDTH = 8;//大整数每位最大的宽度
	vector<int> s;//保存大整数的各个位

	BigInteger(long long num = 0){
		*this = num;
	}
	
	BigInteger operator=(long long num){//赋值运算符1  用long long赋值
		s.clear();
		do{
			s.push_back(num%BASE);//低8位
			num /= BASE;//获取高位（高于8位的所有位数）
		} while (num > 0);
		return *this;
	}

	BigInteger operator=(const string & str){//赋值运算符2 string赋值
		s.clear();
		int x;
		int len = (str.length() - 1) / WIDTH + 1;//8的倍数+1位  保证了取的时候能够把最后小于8的最前几位也取到，这里相当于向上取整
		for (int i = 0; i < len; i++){
			int end = str.length() - i*WIDTH;//依次获取8位数的末位
			int start = max(0, end - WIDTH);//依次获取8位数的首位， 由于最终可能不足8位，start会出现负数，故用max来解决
			sscanf(str.substr(start, end).c_str(), "%d", &x);//将字符串赋值为整数
			s.push_back(x);
		}
		return *this;
	}

	//运算符重载部分
	//重载+
	BigInteger operator+(const BigInteger & b) const{
		BigInteger c;//保存相加结果，并返回
		c.s.clear();

		for (int i = 0, g = 0;; i++){//i作为普通循环变量，记录位数，g记录进位
			if (g == 0 && i >= s.size() & i >= b.s.size()){
				break;//进位为0，达到了本对象的最高位和b的最高位，结束加法循环
			}
			int x = g;//x保存各位的加法结果，注意要用g初始化，可以在一开始就把进位加上
			if (i < s.size()){
				x += s[i];
			}
			if (i < b.s.size()){
				x += b.s[i];
			}
			c.s.push_back(x%BASE);
			g = x / BASE;

		}
		return c;
	}
	//重载+=
	BigInteger operator+=(const BigInteger & b){
		*this = *this + b;
		return *this;
	}
	//重载<
	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 !(*this < b);
	}
	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);
	}
};

//重载<<
ostream & operator<<(ostream & out, const BigInteger &x){
	out << x.s.back();//先输出最高位，以为最高位不一定是8位，算法不统一

	for (int i = x.s.size() - 2; i >= 0; i--){
		char buf[20];
		sprintf(buf, "%08d", x.s[i]);//利用sprintf进行缓冲输出
		for (int j = 0; i < strlen(buf); j++){
			out << buf[j];
		}
	}
	return out;
}

//重载>>
istream& operator>>(istream &in, BigInteger &x){
	string s;
	if (!(in >> s)) return in;
	x = s;
	return in;
}

int main()
{

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

2.构造说明

$1.思路

采用vector数组来保存大整数的“各位数”，由于数组元素为int类型，故可以保存的位数可以达到8位，因此，vector数组其实保存的是大整数的“每8位”。并且，采用的是vector数组而不是普通数组，可以动态的添加元素，无需考虑数组大小的问题。
还有一点是对大整数的初始化和赋值问题，可以用long long类型或string类型变量进行赋值，但应每8位进行一次操作，就像把普通整数各位分开保存类似，其中细节要多考虑。

$2.赋值操作的解读

采用long long的赋值操作：num/% BASE 取出后8位，num/BASE，前移8位，继续取，直到num为0.
采用string的赋值操作：先将str的长度按照8个一份分出来保存为len，并且用了向上取整，保证了最后小于8的几位也可以获得。然后利用循环，每次循环，从低位倒着找8位，先设置end，再用end-WIDTH确定start，获取到了8位的字符串范围。注意，在此有个细节，当最后的位数小于8位时，start会小于0，因此出现了max函数的操作，保证了最后一步的正确性。

$3.重载<<

先输出大整数的最高位（s.back（）），其余所有低位都是8位，可以采用统一的循环来输出。注意此处运用了sprintf，将各位先输出到缓冲区buf，再发送给out输出。

$4.重载>>

先创建string变量保存用户输入的大整数，再利用了赋值操作，直接将用户输入的string变量赋值给大整数。

$5.重载算术运算符+

最终的结果由新设置的大整数变量c直接返回。
设置int变量g保存进位，i记录大整数的位数，x暂存各位相加的结果，并push_back到c中。
对于加法结束的判断条件：g==0 && i>=s.size() && i>= b.s.size()的理解。不再产生进位，达到了本大整数对象的最高位和加数的最高位。

$6.重载比较操作符<

应该注意的是，一旦<被重载出来，其他的所有比较操作符都可以利用<重载，这种技巧要记住。
重载方法较为简单，三种情况分别写出来即可。