C++

自定义大整型

通过定义大整型来学习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
 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

const int MAXN = 10000;

struct BigInteger {
    // 定义大数组
    int digit[MAXN];
    // 定义BigInteger长度
    int length;
    // 构造函数初始化
    BigInteger();
    // 普通整型初始化
    BigInteger(int x);
    // 字符串初始化
    BigInteger(string str);
    // 另外一个大整型来初始化这个大整型
    BigInteger(const BigInteger& b);
    // 重载运算符
    BigInteger operator=(int x);
    BigInteger operator=(string str);
    // 通过添加const标识，使用非const和const都能作为参数传递使用
    // &除了引用和位址之外，还有防止拷贝的功能，&会改变对象本身，加const就防止对象发生改变
    // &引用必须在创建时被初始化，一旦被初始化为一个对象，就不能指向另外一个对象
    // const BigInteger &b 达到了无法修改货真价实的目的
    BigInteger operator=(const BigInteger& b);
    bool operator<(const BigInteger& b);
    bool operator<=(const BigInteger& b);
    bool operator==(const BigInteger& b);
    BigInteger operator+(const BigInteger& b);
    BigInteger operator-(const BigInteger& b);
    BigInteger operator*(const BigInteger& b);
    BigInteger operator/(const BigInteger& b);
    BigInteger operator%(const BigInteger& b);
    // cin,cout输入输出的符号
    // istream 和 ostream对象都不能复制，所以必须引用。其次引用可以减少拷贝的发生提高效率
    // 如果不是引用，那么函数就会产生一个新的临时对象，返回的就是这个临时对象，与原对象就不匹配
    // 重载赋值运算符，连续赋值可以不返回引用
    // 重载加法操作符，连续相加不能返回引用
    friend istream& operator>>(istream& in, BigInteger& b);
    friend ostream& operator<<(ostream& out, const BigInteger& b);
    // 总结：&的主要目的是为了确保传入或返回的值为真实值，而非一个拷贝或新创建的临时对象
};

istream& operator>>(istream& in, BigInteger& b) {
    string str;
    in >> str;
    b = str;
    return in;
}

ostream& operator<<(ostream& out, const BigInteger& b) {
    for (int i = b.length - 1; i >= 0; --i) {
        out << b.digit[i];
    }
    return out;
}
// 此处域运算符::表示BigInteger中的成员BigInteger，若为::BigInteger则为全局域中的BigInteger
// ::域运算符限定作用域
BigInteger::BigInteger() {
    // 初始化为全0，可以直接使用BigInteger结构体中包含的digit数组
    memset(digit, 0, sizeof(digit));
    length = 0;
}

BigInteger::BigInteger(int x) {
    memset(digit, 0, sizeof(digit));
    length = 0;
    if (x == 0) {
        digit[length++] = x;
    }
    while (x != 0) {
        digit[length++] = x % 10;
        x /= 10;
    }
}

BigInteger::BigInteger(string str) {
    memset(digit, 0, sizeof(digit));
    length = str.size();
    for (int i = 0; i < length; ++i) {
        digit[i] = str[length - i - 1] - '0';
    }
}

BigInteger::BigInteger(const BigInteger& b) {
    memset(digit, 0, sizeof(digit));
    length = b.length;
    for (int i = 0; i < length; ++i) {
        digit[i] = b.digit[i];
    }
}

// 重载BigInteger类中的等号运算符，同时返回一个BigInteger型的结构体
BigInteger BigInteger::operator=(int x) {
    memset(digit, 0, sizeof(digit));
    length = 0;
    if (x == 0) {
        digit[length++] = x;
    }
    while (x != 0) {
        digit[length++] = x % 10;
        x /= 10;
    }
    // 返回对象本身
    return *this;
}

BigInteger BigInteger::operator=(string str) {
    memset(digit, 0, sizeof(digit));
    length = str.size();
    for (int i = 0; i < length; ++i) {
        digit[i] = str[length - i - 1] - '0';
    }
    return *this;
}

BigInteger BigInteger::operator=(const BigInteger& b) {
    memset(digit, 0, sizeof(digit));
    length = b.length;
    for (int i = 0; i < length; ++i) {
        digit[i] = b.digit[i];
    }
    return *this;
}
// 重载比较运算符
bool BigInteger::operator<(const BigInteger& b) {
    // 比较每一位的大小
    if (length < b.length) {
        return true;
    } else if (b.length < length) {
        return false;
    } else {
        for (int i = length - 1; i >= 0; --i) {
            if (digit[i] == b.digit[i]) {
                continue;
            } else {
                return digit[i] < b.digit[i];
            }
        }
    }
    return false;
}

bool BigInteger::operator<=(const BigInteger& b) {
    if (length < b.length) {
        return true;
    } else if (b.length < length) {
        return false;
    } else {
        for (int i = length - 1; i >= 0; --i) {
            if (digit[i] == b.digit[i]) {
                continue;
            } else {
                return digit[i] < b.digit[i];
            }
        }
    }
    return true;
}

bool BigInteger::operator==(const BigInteger& b) {
    if (length != b.length) {
        return false;
    } else {
        for (int i = length - 1; i >= 0; --i) {
            if (digit[i] != b.digit[i]) {
                return false;
            }
        }
    }
    return true;
}
// 重载加减乘除运算符
BigInteger BigInteger::operator+(const BigInteger& b) {
    BigInteger answer;
    int carry = 0; // 进位位
    for (int i = 0; i < length || i < b.length; ++i) {
        int current = carry + digit[i] + b.digit[i];
        carry = current / 10;
        answer.digit[answer.length++] = current % 10;
    }
    if (carry != 0) {
        answer.digit[answer.length++] = carry;
    }
    return answer;
}

BigInteger BigInteger::operator-(const BigInteger& b) {
    BigInteger answer;
    int carry = 0; //借位位
    for (int i = 0; i < length; ++i) {
        int current = digit[i] - b.digit[i] - carry;
        if (current < 0) {
            // 不够减，向高位借1，即+10
            current += 10;
            carry = 1;
        } else {
            carry = 0;
        }
        answer.digit[answer.length++] = current;
    }
    while (answer.digit[answer.length - 1] == 0 && answer.length > 1)  {
        answer.length--;
    }
    return answer;
}

BigInteger BigInteger::operator*(const BigInteger& b) {
    BigInteger answer;
    answer.length = length + b.length;
    // 保留各个位的乘积
    for (int i = 0; i < length; ++i) {
        for (int j = 0; j < b.length; ++j) {
            answer.digit[i + j] += digit[i] * b.digit[j];
        }
    }
    // 处理各个位的值,>10则向下一位进1
    for (int i = 0; i < answer.length; ++i) {
        answer.digit[i + 1] += answer.digit[i] / 10;
        answer.digit[i] %= 10;
    }
    // 除去多余的0
    while (answer.digit[answer.length - 1] == 0 && answer.length > 1)  {
        answer.length--;
    }
    return answer;
}

BigInteger BigInteger::operator/(const BigInteger& b) {
    BigInteger answer;
    answer.length = length;
    BigInteger remainder = 0;
    BigInteger temp = b;
    for (int i = length - 1; i >= 0; --i) {
        if (!(remainder.length == 1 && remainder.digit[0] == 0)) {
            // 依次向后移一位，大位在后，小位在前
            for (int j = remainder.length - 1; j >= 0; --j) {
                remainder.digit[j + 1] = remainder.digit[j];
            }
            // 余数长度增加1
            remainder.length++;
        }
        remainder.digit[0] = digit[i];
        // 够减就减，不够商0
        while (temp <= remainder) {
            remainder = remainder - temp;
            answer.digit[i]++;
        }
    }
    // 除去多余的0
    while (answer.digit[answer.length - 1] == 0 && answer.length > 1)  {
        answer.length--;
    }
    return answer;
}

BigInteger BigInteger::operator%(const BigInteger& b) {
    BigInteger remainder = 0;
    BigInteger temp = b;
    for (int i = length - 1; i >= 0; --i) {
        if (!(remainder.length == 1 && remainder.digit[0] == 0)) {
            for (int j = remainder.length - 1; j >= 0; --j) {
                remainder.digit[j + 1] = remainder.digit[j];
            }
            remainder.length++;
        }
        remainder.digit[0] = digit[i];
        while (temp <= remainder) {
            remainder = remainder - temp;
        }
    }
    return remainder;
}
C++

The ideal is a steel city, external again strong also difficult to break; Ideal is fragile, internal shake a few to collapse

理想是钢铁城池，外部再强也难以击破；理想是脆弱不堪，内部动摇就几欲崩塌

© 2020 - 2023 小程同学的博客
Website Built By Cheng