抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

一方の笔记本

The only source of knowledge is experience.

博客

随笔

朋友

归档

关于

C++的大整数类

算法学习

发布于：2021年11月13日

这两天写高精度计算，发现C++缺少一个方便使用的大整数类，于是自己写了一个，主要的原理是运算符重载。 

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
//file: big_int.h
#ifndef _BIG_INT_H
#define _BIG_INT_H

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

#define __POSITIVE__ false
#define __NEGATIVE__ true
class big_int {
public:
	//构造函数
	big_int() :sign(__POSITIVE__), nums(1, 0) {}
	big_int(int n);
	big_int(const std::string& n);
	big_int(const big_int& _ano);

	//求幂，原理为快速幂
	big_int pow(const big_int& _ano) const;

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

	big_int& operator=(const big_int& _ano);

	big_int& operator+=(const big_int& _ano);
	big_int& operator-=(const big_int& _ano);
	big_int& operator*=(const big_int& _ano);
	big_int& operator/=(const big_int& _ano);
	big_int operator%=(const big_int& _ano);

	big_int operator++(int);
	big_int& operator++();

	bool operator<(const big_int& _ano) const;
	bool operator==(const big_int& _ano) const;
	bool operator>(const big_int& _ano) const;
	bool operator>=(const big_int& _ano) const;
	bool operator<=(const big_int& _ano) const;

	std::string to_string();

	friend std::ostream& operator<<(std::ostream& o, const big_int& _output);

private:
	bool sign;
	std::vector<int> nums;
	
	big_int(bool sign, const std::vector<int>& nums);

	bool absolute_value_A_less_than_B(const std::vector<int>& A, const std::vector<int>& B) const;

	std::vector<int> absolute_value_subtract(const std::vector<int>& A, const std::vector<int>& B) const;
	std::vector<int> absolute_value_mutiply(const std::vector<int>& A, const std::vector<int>& B) const;
};
#endif
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
//file: big_int.cpp
#include "big_int.h"

big_int::big_int(bool sign, const std::vector<int>& nums) :sign(sign), nums(nums) {}

big_int::big_int(int n) :sign(n < 0) {
	if (n == 0) nums.resize(1, 0);
	else {
		if (n < 0)  n = -n;
		while (n) {
			nums.emplace_back(n % 10);
			n /= 10;
		}
	}
}

big_int::big_int(const std::string& n) :sign(n[0] == '-') {
	if (n == "0") nums.resize(1, 0);
	else {
		int highest = sign;
		for (int i = n.size() - 1; i >= highest; i--) {
			nums.emplace_back(n[i] - '0');
		}
	}
}

big_int::big_int(const big_int& _ano) :sign(_ano.sign), nums(_ano.nums) {}

big_int big_int::pow(const big_int& _ano) const {
	big_int ans = 1, _y = _ano, _x = *this;
	while (_y > 0) {
		if (_y % 2 == 1) ans *= _x;
		_x *= _x;
		_y /= 2;
	}
	return ans;
}

big_int big_int::operator+(const big_int& _ano) const {
	if (sign != _ano.sign) return *this - big_int(!_ano.sign, _ano.nums);
	std::vector<int> ans(std::max(_ano.nums.size(), nums.size()) + 1, 0);
	int i = 0, j = 0, k = 0;
	while (i < nums.size() && j < _ano.nums.size()) ans[k++] = nums[i++] + _ano.nums[j++];
	while (i < nums.size()) ans[k++] = nums[i++];
	while (j < _ano.nums.size()) ans[k++] = _ano.nums[j++];
	for (int i = 0, c = 0; i < ans.size(); i++) {
		ans[i] += c;
		c = ans[i] / 10;
		ans[i] %= 10;
	}
	while (ans.size() > 1 && ans.back() == 0) ans.pop_back();
	return big_int(sign, ans);
}

big_int big_int::operator-(const big_int& _ano) const {
	if (sign != _ano.sign) return *this + big_int(!_ano.sign, _ano.nums);
	if (absolute_value_A_less_than_B(nums, _ano.nums)) return big_int(!sign, absolute_value_subtract(_ano.nums, nums));
	else return big_int(sign, absolute_value_subtract(nums, _ano.nums));
}

big_int big_int::operator*(const big_int& _ano) const {
	return big_int(sign ^ _ano.sign, absolute_value_mutiply(_ano.nums, nums));
}

big_int big_int::operator/(const big_int& _ano) const {
	if (absolute_value_A_less_than_B(nums, _ano.nums)) return big_int(0);
	std::vector<int> res, temp, tempMul;
	for (int i = nums.size() - 1; i >= 0; i--) {
		temp.push_back(nums[i]);
		std::reverse(temp.begin(), temp.end());
		while (temp.size() > 1 && temp.back() == 0) temp.pop_back();
		int j = 1;
		for (; j <= 9; j++) {
			std::vector<int> factor(1, j);
			tempMul = absolute_value_mutiply(factor, _ano.nums);
			if (absolute_value_A_less_than_B(temp, tempMul)) {
				break;
			}
		}
		res.emplace_back(--j);
		tempMul = absolute_value_mutiply(std::vector<int>(1, j), _ano.nums);
		temp = absolute_value_subtract(temp, tempMul);
		std::reverse(temp.begin(), temp.end());
	}
	int i = 0;
	while (i < res.size() - 1 && res[i] == 0) i++;
	std::vector<int> ans(std::vector<int>(res.begin() + i, res.end()));
	std::reverse(ans.begin(), ans.end());
	return big_int(sign ^ _ano.sign, ans);
}

big_int big_int::operator%(const big_int& _ano) const { return *this - *this / _ano * _ano; }

big_int& big_int::operator=(const big_int& _ano) {
	sign = _ano.sign;
	nums = _ano.nums;
	return *this;
}

big_int& big_int::operator+=(const big_int& _ano) {
	*this = *this + _ano;
	return *this;
}

big_int& big_int::operator-=(const big_int& _ano) {
	*this = *this - _ano;
	return *this;
}

big_int& big_int::operator*=(const big_int& _ano) {
	*this = *this * _ano;
	return *this;
}

big_int& big_int::operator/=(const big_int& _ano) {
	*this = *this / _ano;
	return *this;
}

big_int big_int::operator%=(const big_int& _ano) {
	*this = *this - *this / _ano * _ano;
	return *this;
}

big_int big_int::operator++(int) {
	big_int temp = *this;
	*this += 1;
	return temp;
}

big_int& big_int::operator++() {
	*this += 1;
	return *this;
}

bool big_int::operator<(const big_int& _ano) const {
	if (sign == _ano.sign) return absolute_value_A_less_than_B(nums, _ano.nums);
	else return sign == __NEGATIVE__;
}

bool big_int::operator==(const big_int& _ano) const { 
	return sign == _ano.sign && nums == _ano.nums; 
}

bool big_int::operator>(const big_int& _ano) const {
	return !(*this == _ano || *this < _ano);
}

bool big_int::operator>=(const big_int& _ano) const {
	return *this > _ano || *this == _ano;
}

bool big_int::operator<=(const big_int& _ano) const {
	return *this < _ano || *this == _ano;
}

std::string big_int::to_string() {
	std::string ans;
	if (sign == __NEGATIVE__) ans.push_back('-');
	for (int i = nums.size() - 1; i >= 0; i--) ans.push_back(nums[i] + '0');
	return ans;
}

std::vector<int> big_int::absolute_value_subtract(const std::vector<int>& A, const std::vector<int>& B) const {
	std::vector<int> ans(A);
	for (int i = 0, c = 0; i < A.size(); i++) {
		ans[i] -= c + (i < B.size() ? B[i] : 0);
		c = ans[i] < 0;
		ans[i] += (ans[i] < 0 ? 10 : 0);
	}
	while (ans.back() == 0 && ans.size() > 1) ans.pop_back();
	return ans;
}

bool big_int::absolute_value_A_less_than_B(const std::vector<int>& A, const std::vector<int>& B) const {
	if (A.size() != B.size()) return A.size() < B.size();
	else {
		for (int i = A.size() - 1; i >= 0; i--) {
			if (A[i] != B[i]) return A[i] < B[i];
		}
	}
	return false;
}

std::vector<int> big_int::absolute_value_mutiply(const std::vector<int>& A, const std::vector<int>& B) const {
	std::vector<int> ans(A.size() + B.size(), 0);
	for (int i = 0; i < A.size(); i++) {
		for (int j = 0; j < B.size(); j++) {
			ans[i + j] += A[i] * B[j];
		}
	}
	for (int i = 0, c = 0; i < ans.size(); i++) {
		ans[i] += c;
		c = ans[i] / 10;
		ans[i] %= 10;
	}
	while (ans.size() > 1 && ans.back() == 0) ans.pop_back();
	return ans;
}

std::ostream& operator<<(std::ostream& o, const big_int& _output) {
	if (_output.sign == __NEGATIVE__) o << '-';
	for (int i = _output.nums.size() - 1; i >= 0; i--) o << _output.nums[i];
	return o;
}

  测试代码如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//file: test.cpp
#include <iostream>
#include <vector>
#include "big_int.h"
using namespace std;
const int N = 100;
big_int fact[N + 1];
int main() {
    fact[0] = 1;
    for (int i = 1; i <= N; i++) {
        fact[i] = fact[i - 1] * i;
    }
    cout << fact[10] << endl;
    return 0;
}

评论