C++手搓大整数类
基本思路
实现大整数有两种方法，一种是将大数当成字符来处理，手动计算加减乘除，另一种则是将大数分成多个小部分用基本类型存储处理
我们这里实现第二种方法的，目前版本是支持非负整数
基本思路是将一个大整数切分成几段小的用int存储，用vector容器来存储每段，例如
1111222233334444 integer[1]=11112222 integer[0]=33334444
重载赋值运算符
重载赋值运算符，实现从基本数据类型到大整数的转换，通过和base取余切分出段
class BigInteger {
static const int width = 8; // 切分段的长度
static const int base = 1e8; // 切分段的数量级
vector<int> integer; // 存储各个段
int segments = 0; // 切分的段数
BigInteger operator=(long long num) { // 重载赋值运算符，从基本数据类型转换大整数存储
integer.clear();
do {
integer.emplace_back(num % base);
num /= base;
segments++;
} while (num > 0);
return *this;
}
};实现默认构造函数和带参构造函数，通过重载的赋值运算符直接赋值
explicit BigInteger(long long num = 0) {
*this = num;
}继续重载赋值运算符，实现从字符串到大整数的转换，首先计算出这个大整数有几段，这里的计算方法十分巧妙，如果直接除以width当不是整除的时候会少数一段，所以先减一再除最后加一的方法可以适用整除和不整除的情况
然后需要计算每段的开始和结束的位置，因为vector存储段的顺序是从后往前，所以这里计算段的位置也是从后往前，然后通过string取子串，再通过stoi函数将字符串转成整型存储
BigInteger operator=(const string &num) { // 重载赋值运算符，从字符串类型转大整数存储
integer.clear();
int length = num.size();
segments = (length - 1) / width + 1; // 这里计算段数的方法十分巧妙
for (int i = 0; i < segments; i++) {
int end = length - i * width; // 计算每段结束的地方，从最后一段开始
int start = max(0, end - width); // 计算每段开始的地方
integer.emplace_back(stoi(num.substr(start, end - start))); // 字符串转整数
}
return *this;
}重载输入输出运算符
接着重载输出运算符，重载输出运算符可以通过友元函数和成员函数两种方法实现，我们这里通过友元函数的方法实现，倒序输出vector
ostream &operator<<(ostream &out) { // 重载输出运算符，vector倒着输出
for (auto it = integer.rbegin(); it != integer.rend(); it++) {
cout << *it;
}
return out;
}重载输入运算符，将输入当成字符串，通过重载的赋值运算符直接赋值
istream &operator>>(istream &in) { // 重载输入运算符，当成字符串输入，用重载的赋值运算符直接赋值
string num;
in >> num;
*this = num;
return in;
}重载加运算符
加
大整数加运算的基本思想是将各个段相加，需要处理段相加的时候出现的进位情况，由于int型可以表示的范围大概是10个数量级，而我们给每段设置的位数是8，因此可以使用int型来存储段加的结果，然后继续存储加结果和base取余的结果，计算出和base整除的结果，留到下一个段继续相加
BigInteger operator+(const BigInteger &bigInteger) const {
BigInteger result;
for (int i = 0, carry = 0; carry || i < segments || i < bigInteger.segments; i++) {
if (i < segments)
carry += integer[i];
if (i < bigInteger.segments)
carry += bigInteger.integer[i];
result.integer.emplace_back(carry % base);
result.segments++;
carry = carry / base;
}
return result;
}顺便实现+=
BigInteger operator+=(const BigInteger &bigInteger) {
*this = *this + bigInteger;
return *this;
}重载比较运算符
这个比较两个大整数的实现比较巧妙
我们先实现一个重载小于的判断，先比较两个大整数的段数，如果段数不同直接返回段数的比较就行，如果段数相同，由于大整数的低位存储在vector的前面，所以从后面段开始比较高位，如果高位不相同，那么返回高位的比较结果就行，如果都相同，那么说明相等
bool operator <(const BigInteger&bigInteger) const{
if(segments!=bigInteger.segments)
return segments<bigInteger.segments;
for(int i=segments-1;i>=0;i--){ // 倒着比较，因为低位在vector的前面，先比较高位
if(integer[i]!=bigInteger.integer[i])
return integer[i]<bigInteger.integer[i];
}
return false; // 相等
}然后接下来的大于、大于等于、小于等于、不等于、等于都可以通过小于实现
bool operator>(const BigInteger &bigInteger) const {
return bigInteger < *this; // a大于b等价于b小于a
}
bool operator<=(const BigInteger &bigInteger) const {
return !(bigInteger < *this); // a<=b等价于b不小于a
}
bool operator>=(const BigInteger &bigInteger) const {
return !(*this < bigInteger); // a>=b等价于a不小于b
}
bool operator!=(const BigInteger &bigInteger) const {
return *this < bigInteger || bigInteger < *this; // a不等于b等价于a大于b或者小于b
}
bool operator==(const BigInteger &bigInteger) const {
return !(*this < bigInteger) && !(bigInteger < *this); // a等于b等价于a既不大于b也不小于b
}巧妙
腾讯云开发者
