XieNaoban's Blog
0%

我的整形大数类(支持正负)

发表于 更新于 分类于 阅读次数： 评论次数：
本文字数： 12k 阅读时长 ≈ 11 分钟

好几天没刷题没看书没写博客了，一直在闭关修炼写大数，现在终于写出来啦！我也终于有了属于我自己的大数~~~~并且以头文件的形式写出的，可以算是一个完整的成品了，拿过来就可以用。 本大数类：longer实现的功能：加减乘除、取余、取绝对值，开根号什么的没精力弄了，只是声明了一下没定义，以后会更新的。同时支持正负号。数据用的vector< long long >存储，long long最大储存9位数，也就是999999999，因为2个999999999相乘刚好不越界。不过后来发现好像没必要，用int就行了，但是写都写一半了，就没改。不过灵活性也蛮高的吧，可以很轻松地把数据类型从long long 改为int，同时只要把MAX改为int的最大值10000，把DIGIT改为4即可（没具体试过，应该没问题）。就是下面这几行：

1
2
3
4
//longer类内定义
typedef long long ll;
static constexpr ll MAX = 1000000000;
static constexpr int DIGIT = 9;

当然有储存，这应该不是最好的方法，不过就我目前的水平就这样吧。而且现在对于编程是“空间换时间”还是“时间换空间”一直很纠结。。。 然后单独定义一个sign表示正负号。那么当然啦，对于这种用单独一个符号标记来表示正负数字的，就会有+0和-0的问题，我也是基本解决了，就是把负的改成正的。当然不排除还有bug，没精力检测了。后续更新吧。 加法减乘除均使用小学教的竖式方法。。。因为网上也没学到更快的方法，最快的方法（尤其是除法）好像看到个，没会。。。所以这个东西在处理比如一千多位除以几百之类的数据时会很慢。。。不过毕竟我现在还算是新手嘛，以后可以还会再写一个更快的大数。使用竖式时，加法减法乘法使用的10^10进制，即统一算出一个ll（long long）的值，进位到下一个。 加法减法本质上由get_addition()与get_subtraction()实现，这两个函数无视正负号，全都看成是正的进行运算，只支持大的数加减小的数。因此对于有不同的正负符号的数字，比如负+正，可以看作-（正-负），所以只要调用get _subtraction()运算后添个负号即可；而对于正-负，可看作正+正，反而调用get _addition()。所以本质上还是正数之间的运算。 乘法与加法类似，甚至还少了符号的问题。 除法也是小学教的竖式法，一位位除，也就是一位位减，但是由于我得先乘以10的好多次，再循环减，再看下一位，速度还是慢，就比如3000位的数字除以50位的数字，那速度醉啦，要十几秒。 取余使用的"this - (this / n)*n"，所以比除号还慢。 比较符号没有很仔细地调试，但是应该没什么问题吧。 截图： 这里写图片描述

这里写图片描述
这里写图片描述

代码：

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
//我的大数类，定义为longer好了[笑哭]
#ifndef _LONGER_H
#define _LONGER_H
#include<vector>
#include<string>
#include<sstream>
#include<iomanip>
//#pragma warning(disable:4996)	//对使用VS2015且开启了“安全开发生命周期(SDL)检测”的项目奏效(VS2013应该也有用)
class longer
{
	//必要定义	(-.-;)
	typedef long long ll;
	static constexpr ll MAX = 1000000000;	//每个ll的存储限制，999999999*999999999刚好不溢出(9个9)
	static constexpr int DIGIT = 9;			//ll支持的最大位数
	//数据储存	(-.-;)
	bool sign;								//正负号：0正1负
	std::vector<ll> number;					//大数存储区

public:
	//构造函数	(-.-;)
	longer();
	longer(const ll&);
	longer(const longer&);
	longer(const char*);
	longer(const std::string&);

	//运算符重载	(-.-;)
	longer operator +()const;
	longer operator +(const longer&)const;
	longer operator -()const;
	longer operator -(const longer&)const;
	longer operator *(const longer&)const;
	longer operator /(const longer&)const;
	longer operator %(const longer&)const;

	longer& operator ++();
	longer operator ++(int);
	longer& operator --();
	longer operator --(int);

	longer& operator =(const ll&);
	longer& operator =(const longer&);
	longer& operator =(const char*);
	longer& operator =(const std::string&);

	longer& operator +=(const longer&);
	longer& operator -=(const longer&);
	longer& operator *=(const longer&);
	longer& operator /=(const longer&);

	inline bool operator <(const longer&)const;
	inline bool operator >(const longer&)const;
	inline bool operator <=(const longer&)const;
	inline bool operator >=(const longer&)const;
	inline bool operator ==(const longer&)const;
	inline bool operator !=(const longer&)const;

	friend std::istream& operator >>(std::istream&, longer&);
	friend std::ostream& operator <<(std::ostream&, const longer&);

	//其他函数	(-.-;)
	int digit()const;
	static longer lrabs(const longer&);		//求绝对值
	static longer lrsqrt(const longer&);	//求算数平方根,暂时没打算完成，先占个茅坑,不拉屎

private:
	//类内部调用	(-.-;)
	longer(const int, const ll&);									//分配多少个vector容量，每个数据均为第一个参数
	static longer& get_addition(longer&, const longer&, bool);		//获得加法结果,仅支持正整数以大加小,无视正负号
	static longer& get_subtraction(longer&, const longer&, bool);	//获得减法结果,仅支持正整数以大减小,无视正负号
	int get_comparison(const longer&)const;							//获得比较结果,仅支持正整数相互比较,无视正负号
	inline ptrdiff_t get_ptrdiff()const;							//获得vector数组元素个数
	inline longer& get_zero();										//若结果为0,且若0的sign为负，则改为0
};



//必要定义	↖(-(●●)-)↗↖(-(●●)-)↗↖(-(●●)-)↗↖(-(●●)-)↗↖(-(●●)-)↗
constexpr longer::ll longer::MAX;
constexpr int longer::DIGIT;



//构造函数	↖(-(●●)-)↗↖(-(●●)-)↗↖(-(●●)-)↗↖(-(●●)-)↗↖(-(●●)-)↗
longer::longer() { number.push_back(0); }
longer::longer(const ll& n) { *this = n; }
longer::longer(const longer& n) { *this = n; }
longer::longer(const char* s) { *this = s; }
longer::longer(const std::string& s) { *this = s; }
longer::longer(const int i, const ll& n) : number(i, n), sign(0) {}



//运算符重载	↖(-(●●)-)↗↖(-(●●)-)↗↖(-(●●)-)↗↖(-(●●)-)↗↖(-(●●)-)↗
//加减乘除取余次方
longer longer::operator +()const { return *this; }

longer longer::operator +(const longer& n)const
{
	bool judge = get_comparison(n) >= 0;
	longer aa(judge ? *this : n);
	auto &bb = (judge ? n : *this);
	if ((!aa.sign) && (!bb.sign)) return get_addition(aa, bb, 0);			//正+正
	if ((!aa.sign) && (bb.sign)) return get_subtraction(aa, bb, !judge);	//正+负
	if ((aa.sign) && (!bb.sign)) return get_subtraction(aa, bb, judge);		//负+正
	return get_addition(aa, bb, 1);											//负+负
}

longer longer::operator -()const { longer t(*this);t.sign = (t.sign ? 0 : 1);return t; }

longer longer::operator -(const longer& n)const
{
	bool judge = get_comparison(n) >= 0;
	longer aa(judge ? *this : n);
	auto &bb = (judge ? n : *this);
	if ((!aa.sign) && (!bb.sign)) return get_subtraction(aa, bb, !judge);	//正-正
	if ((!aa.sign) && (bb.sign)) return get_addition(aa, bb, 0);			//正-负
	if ((aa.sign) && (!bb.sign)) return get_addition(aa, bb, 1);			//负-正
	return get_subtraction(aa, bb, judge);									//负-负
}

longer longer::operator *(const longer& n)const
{//模拟小学老师教的方法
	int leni = get_ptrdiff(), lenj = n.get_ptrdiff();
	longer re(leni + lenj, 0);
	ll flag;
	sign == n.sign ? re.sign = 0 : re.sign = 1;
	for (int i = 0;i < leni;++i) {
		longer t(n);
		int j;
		flag = 0;
		for (j = 0;j < lenj;++j) {
			t.number[j] = t.number[j] * number[i] + flag;
			flag = t.number[j] / MAX;
			t.number[j] -= flag*MAX;
		}
		if (flag) t.number.push_back(flag);
		flag = 0;
		for (j = 0;j < t.get_ptrdiff();++j) {
			re.number[i + j] += t.number[j] + flag;
			if (re.number[i + j] >= MAX) re.number[i + j] -= MAX, flag = 1;
			else flag = 0;
		}
		if (flag) re.number[i + j] += flag;
	}
	while (re.get_ptrdiff() > 1 && !*re.number.rbegin()) re.number.pop_back();
	return re.get_zero();
}

longer longer::operator /(const longer& n)const
{//模拟小学老师教的方法
	if (n == longer((ll)0)) { std::cerr << "除数为0!\n";exit(1); }
	longer th(*this), re((ll)0);
	re.sign = th.sign = 0;
	const int times = digit() - n.digit();
	for (int i = times;i >= 0;--i) {
		longer digi(i / DIGIT + 1, 0);
		*digi.number.rbegin() = ((ll)pow(10, i % DIGIT));
		longer t(n*digi); t.sign = 0;
		while (th.get_comparison(t) == 1) th-=t, re += digi;
		if (th.get_comparison(t) == 0) { re += digi;break; }
	}
	if (sign != n.sign) re.sign = 1;
	return re.get_zero();
}

longer longer::operator %(const longer& n)const
{
	longer re(*this - (*this / n)*n);
	return re.get_zero();
}


//自增自减
longer& longer::operator ++() { return *this = *this + 1; }
longer longer::operator ++(int) { longer t = *this;*this = *this + 1;return t; }
longer& longer::operator --() { return *this = *this - 1; }
longer longer::operator --(int) { longer t = *this;*this = *this - 1;return t; }


//赋值
longer& longer::operator =(const ll& n)
{
	if (n < 0) sign = 1, number.push_back(-n);
	else sign = 0, number.push_back(n);
	return *this;
}

longer& longer::operator =(const longer& n)
{
	number = n.number;
	sign = n.sign;
	return *this;
}

longer& longer::operator =(const char* s)
{
	return *this = std::string(s);
}

longer& longer::operator =(const std::string& s)
{
	auto ps = s.rbegin();
	char c[DIGIT + 1], *pc;
	ll temp;
	sign = 0;
	while (ps != s.rend()) {
		*(pc = &c[DIGIT]) = '\0';
		int i;
		for (i = 0;i < DIGIT && ps != s.rend();++i)
			*--pc = *ps++;
		if (*(ps - 1) == '-') *pc = '0', sign = 1;
		while (i++ < DIGIT) *--pc = '0';
		std::istringstream in(c);
		in >> temp;
		number.push_back(temp);
	}
	if (get_ptrdiff()>1 && !*number.rbegin()) number.pop_back();
	return *this;
}


longer& longer::operator +=(const longer& n) { return *this = *this + n; }
longer& longer::operator -=(const longer& n) { return *this = *this - n; }
longer& longer::operator *=(const longer& n) { return *this = *this * n; }
longer& longer::operator /=(const longer& n) { return *this = *this / n; }


//比较
inline bool longer::operator <(const longer& n)const
{
	if ((!sign) && (n.sign)) return 0;
	if ((sign) && (!n.sign)) return 1;
	if ((!sign) && (!n.sign)) return get_comparison(n) == -1;
	return get_comparison(n) == 1;
}

inline bool longer::operator >(const longer& n)const
{
	if ((!sign) && (n.sign)) return 1;
	if ((sign) && (!n.sign)) return 0;
	if ((!sign) && (!n.sign)) return get_comparison(n) == 1;
	return get_comparison(n) == -1;
}

inline bool longer::operator <=(const longer& n)const
{
	if ((!sign) && (n.sign)) return 0;
	if ((sign) && (!n.sign)) return 1;
	if ((!sign) && (!n.sign)) return get_comparison(n) <= 0;
	return get_comparison(n) >= 0;
}

inline bool longer::operator >=(const longer& n)const
{
	if ((!sign) && (n.sign)) return 1;
	if ((sign) && (!n.sign)) return 0;
	if ((!sign) && (!n.sign)) return get_comparison(n) >= 0;
	return get_comparison(n) <= 0;
}

inline bool longer::operator ==(const longer& n)const
{
	if (((!sign) && (n.sign)) || ((sign) && (!n.sign))) return 0;
	return !get_comparison(n);
}

inline bool longer::operator !=(const longer& n)const
{
	if (((!sign) && (n.sign)) || ((sign) && (!n.sign))) return 1;
	return get_comparison(n) != 0;
}


//输入输出
std::istream& operator >>(std::istream& is, longer& n)
{
	std::string s;is >> s;
	n = s;
	return is;
}

std::ostream& operator <<(std::ostream& os, const longer& n)
{
	auto p = n.number.rbegin();
	if (n.sign) os << '-';
	os << *p;
	for (++p;p != n.number.rend();++p) {
		int i = 0;auto n = *p;
		while (n /= 10) ++i;
		for (;++i < longer::DIGIT;std::cout << '0');
		os << *p;
	}
	return os;
}



//其他函数	↖(-(●●)-)↗↖(-(●●)-)↗↖(-(●●)-)↗↖(-(●●)-)↗↖(-(●●)-)↗
int longer::digit()const
{
	int a = (get_ptrdiff() - 1) * DIGIT;
	ll b = *number.rbegin();
	do ++a;while (b /= 10);
	return a;
}

longer longer::lrabs(const longer& n) { longer t(n);if (t.sign) t.sign = 0;return t; }



//类内部调用	↖(-(●●)-)↗↖(-(●●)-)↗↖(-(●●)-)↗↖(-(●●)-)↗↖(-(●●)-)↗
longer& longer::get_addition(longer& aa, const longer& bb, bool si)
{
	auto a = aa.number.begin(), &aend = aa.number.end();
	auto  b = bb.number.begin(), &bend = bb.number.end();
	bool flag = 0;
	aa.sign = si;
	do {
		*a += (b == bend ? 0 : *b++) + flag;
		if (*a >= MAX) *a -= MAX, flag = 1;
		else if (flag) flag = 0;
	} while (++a != aend && (b != bend || flag));
	if (flag) aa.number.push_back(flag);
	return aa.get_zero();
}

longer& longer::get_subtraction(longer& aa, const longer& bb, bool si)
{
	auto a = aa.number.begin(), &aend = aa.number.end();
	auto  b = bb.number.begin(), &bend = bb.number.end();
	bool flag = 0;
	aa.sign = si;
	do {
		*a -= (b == bend ? 0 : *b++) + flag;
		if (*a < 0) *a += MAX, flag = 1;
		else if (flag) flag = 0;
	} while (++a != aend && (b != bend || flag));
	while (aa.get_ptrdiff()>1 && !*aa.number.rbegin()) aa.number.pop_back();
	return aa.get_zero();
}

int longer::get_comparison(const longer& n)const
{//返回1:左值大,0相等,-1右值大
	if (get_ptrdiff() < n.get_ptrdiff()) return -1;
	if (get_ptrdiff() > n.get_ptrdiff()) return 1;
	auto a = number.rbegin(), b = n.number.rbegin();
	while (a != number.rend()) {
		if (*a < *b) return -1;
		if (*a > *b) return 1;
		++a, ++b;
	}
	return 0;
}

inline ptrdiff_t longer::get_ptrdiff()const { return number.end() - number.begin(); }

inline longer& longer::get_zero()
{
	if (get_ptrdiff() == 1 && number[0] == 0 && sign == 1) sign = 0;
	return *this;
}


#endif