2020年5月18日 下午4:45
- 我再原先的版本上增加了：
- 默认初始化
- 字符串的输入的初始化
- <<的重载
- 参考：C++ 高精度整数，大数的进制转换_c/c++_chenmeiqi的博客-CSDN博客
- 大数10进制的原理
- 本质：将一个超大10进制数进行分解
- ….
- 多少个10^8
- 多少个10^4
- 多少个10^0
- bigInteger数据结构：
- 本质：将一个超大10进制数进行分解
- 其中的bug局限：
- 进行乘、除、余数时，只能使用0~10^4次范围内的10进制数，因为这份代码每次进位只能进一位，也就是10^4
- 解决办法：digit[]中的每个元素的最大值，可以从9999 -> MAX_INT
- 这样我们就可以乘以MAX_INT
- bigInteger不支持：
- bigInteger * bigInteger
- bigInteger / bigInteger
- bigInteger % bigInteger
- bigInteger支持：
- bigInteger * int
- bigInteger / int
- bigInteger % int
- 进行乘、除、余数时，只能使用0~10^4次范围内的10进制数，因为这份代码每次进位只能进一位，也就是10^4
- 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19int main() {
bigInteger A("999999999999999999");
bigInteger B = A * 10;
bigInteger C = B / 10;
int D = C % 100;
cout << A << endl;
cout << B << endl;
cout << C << endl;
cout << D << endl;
cout << 1 << endl;
return 0;
}
输出：
999999999999999999
9999999999999999990
999999999999999999
991
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
using namespace std;
unsigned long max_len;
struct bigInteger{ // 大数结构
int digit[1000] = {0};
int size;
// 默认初始化
bigInteger(){
}
// 使用字符串初始化
bigInteger(string input) {
size=0;
int s_len=input.length();
int len=0;
if(s_len%4!=0){ // 一个存 4 位，不足的+1
len=s_len/4+1;
}
else{
len=s_len/4;
}
for(int i=0;i<len;i++){
int pos = max(0,s_len-1-4*i-3);
for (int j=s_len-1-4*i; j>=pos; j-=1) { // 从字符串后往前存
digit[i]+=(input[j]-'0')*pow(10,s_len-4*i-j-1); // char to int, 每次存4位，所以 -4*i
}
size=i+1;
}
}
// 重载输出
friend ostream& operator<<(ostream& os, bigInteger &x)
{
os << x.out() << endl;
return os;
}
// 10进制的字符串形式
string out(){
unsigned long temp;
string res="";
string s;
for (int i=size-1; i>=0; i--) {
s=to_string(digit[i]); // int 转 string
temp=res.length(); // 结果字符串长度
if(i!=size-1){ // 最高位不补 0
for (unsigned long len=s.length(); len<4; len++) { // 其余位不够 4 位补 0
if(temp+1==max_len){ // 结果字符串长度将等于最大位数，不再补 0（针对最低位）
break;
}
else{ // 补 0
s="0"+s;
temp++;
}
}
}
res+=s; // 结果字符串拼接
}
return res;
};
bigInteger operator + (const bigInteger & B) const{
bigInteger res;
bool ifCarry=false; // 是否进位
int carry=0; // 进位值
int index=0; // 在第几位进位
res.size =max(size, B.size);
for (int i=0; i<res.size; i++) { // 逐个相加
res.digit[i]=B.digit[i]+digit[i]+carry;
if(res.digit[i]>9999){
index=i;
ifCarry=true;
}
carry=res.digit[i]/10000;
res.digit[i]=res.digit[i]%10000;
}
if(ifCarry && index==res.size-1){ // 有进位且进位后大于原来位数
res.digit[res.size]=1;
res.size++;
}
if(ifCarry && index==res.size-2){ // 有进位但位数不变
max_len++;
}
return res;
};
bigInteger operator * (int x) const{
bigInteger res;
bool ifCarry=false; // 是否进位
int carry=0; // 进位
int index=0; // 在第几位进位
res.size =size;
for (int i=0; i<res.size; i++) { // 逐个相乘
res.digit[i]=x*digit[i]+carry;
if(res.digit[i]>9999){
index=i;
ifCarry=true;
}
carry=res.digit[i]/10000;
res.digit[i]=res.digit[i]%10000;
}
if(ifCarry && index==res.size-1){ // 有进位且进位后大于原来位数
res.digit[res.size]=carry;
res.size++;
}
return res;
};
bigInteger operator / (int x)const{
bigInteger res;
int reminder=0; // 余数
res.size =size;
for (int i=res.size-1; i>=0; i--) { // 逐个相除
res.digit[i]=(digit[i]+reminder*10000)/x;
reminder=(digit[i]+reminder*10000)%x;
}
if(res.size==1 && digit[0]<x){ // 被除数小于 x
res.digit[0]=0;
}
if(res.size>1 && digit[res.size-1]<x){ // 最高位有余数，位数 -1
res.digit[res.size-1]=0;
res.size--;
}
return res;
}
int operator % (int x)const{
bigInteger res;
int reminder=0; // 余数
res.size =size;
for (int i=res.size-1; i>=0; i--) { // 逐个相除
res.digit[i]=(digit[i]+reminder*10000)/x;
reminder=(digit[i]+reminder*10000)%x;
}
return reminder;
}
};