Loading... 标题说是大整数类，其实是结构体 ~~（因为我不会写类）~~ 这个结构体是我参照一些书上自己魔改的。所以可能会有BUG之类的问题。如果有大佬发现BUG或有优化方案的话请教一下本蒟蒻。 ------------ 那么下面上代码吧 ```cpp #include <iostream> #include <vector> #include <string> #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> using namespace std; typedef long long ll; struct BigInteger { //提前声明这个大整数在vector里面是倒序储存的 static const int BASE = 1E8;//以10^8为一位储存 static const int WIDTH = 8; //同样是8位，以string类读入时用 char symbol;//符号位 这里我定义0的符号为+，方便输出 vector<int> value;//数字位 使用vector可以储存任意大小的数（前提内存够用） BigInteger(ll num = 0)//构造函数，初始为0 { if (num < 0) { num = -num; symbol = '-'; } else symbol = '+'; *this = num; //这个是调用下面重载的的赋值 } BigInteger operator = (const ll &num)//重载当赋值号右边是long long型数的赋值 { value.clear();//构造的时候会有一个0，所以要先清除这个0。下同 num >= 0 ? symbol = '+' : symbol = '-'; ll temp = abs(num); do//这里每次取8位数字 { value.push_back(temp % BASE); temp /= BASE; } while (temp); return *this; } BigInteger operator = (const string &Str)//重载赋值号右边是string时的赋值 { string str = Str; //这一步是为了将const的string改成非const value.clear(); int temp, len = (str.length() - 1) / WIDTH + 1;//这样操作是为了四舍五入 //temp是为了储存每位的数是多少，len代表有几位数 if (str[0] == '-') { symbol = '-'; str.erase(str.begin()); } else symbol = '+'; for (int i = 0; i < len; i++) { int end = str.length() - i * WIDTH; int begin = max(0, end - WIDTH); sscanf(str.substr(begin, end - begin).c_str(), "%d", &temp); //这里的几个函数去网上查吧（我懒得写了），这些用streamstring会更方便一点 value.push_back(temp); } return *this; } //下面是运算符的重载 （取模的运算符懒得写了，谁有思路的话可以教一下我） BigInteger operator + (const BigInteger &num) const { if (symbol == '+' && num.symbol == '-') return *this - -num; if (symbol == '-' && num.symbol == '+') return num - -*this; //上面的有点数学基础应该就看得懂吧→_→ BigInteger res; res.value.clear(); symbol == '+' ? res.symbol = '+' : res.symbol = '-'; for (int i = 0, carry = 0;; i++) { if (i >= value.size() && i >= num.value.size() && !carry) break; //当所有位都加完后终止循环 int temp = carry; if (i < value.size()) temp += value[i]; if (i < num.value.size()) temp += num.value[i]; res.value.push_back(temp % BASE); carry = temp / BASE; } return res; } BigInteger operator + (const ll &num) const { //这个的作用很明显吧，就是重载一个long long型的加法，下面也是类似的 BigInteger temp = num; return *this + temp; } BigInteger operator - () const { //这个是前置负号，是取相反数的重载 BigInteger temp = *this; temp.symbol == '+' ? temp.symbol = '-' : temp.symbol = '+'; return temp; } BigInteger operator - (const BigInteger& num) const { //这里才是减号的重载 if (symbol == '-' && num.symbol == '+') return -(num + -*this); if (symbol == '+' && num.symbol == '-') return -num + *this; BigInteger res, a, b; int len = min(value.size(), num.value.size()); res.value.clear(); //*this >= num ? res.symbol = '+' : res.symbol = '-'; //*this >= num ? a = *this, b = num : a = num, b = *this; //这里注释掉的是用三目运算符，但是会出BUG，如果有大佬知道的话请教一下我（原谅我太菜不知道为什么QAQ） if (*this >= num) { a = *this; b = num; res.symbol = '+'; } else //因为符号位是单独的，所以数字位一定是正的。这里我直接让它大减小 { a = num; b = *this; res.symbol = '-'; } for (int i = 0, borrow = 0;; i++) { if (i >= a.value.size() && i >= b.value.size()) break; int temp = borrow; borrow = 0; //借位和进位不太一样，用完后要清零。 if (i < a.value.size()) temp += a.value[i]; if (i < b.value.size()) temp -= b.value[i]; if (temp < 0 && (i < len - 1 || (i < len && a.value.size() != b.value.size()))) { //只有两者都有的位才有借位（自己模拟一下减法就知道了） temp += BASE; borrow = -1; } else temp = abs(temp); //数字位都是正的 res.value.push_back(temp % BASE); } for (int i = res.value.size() - 1; i > 0; i--) { //做完减法后可能会有前导0，这一步是消去前导0 if (res.value[i] == 0) res.value.pop_back(); else break; } return res; } BigInteger operator - (const ll &num) const { BigInteger temp = num; return *this - temp; } BigInteger operator * (const BigInteger& num) const { //乘号的重载。我的思路是取一个因数的每一位与另一个因数相乘（其实也是模拟小学乘法） BigInteger res; res.value.clear(); if ((symbol == '+' && num.symbol == '-') || (symbol == '-' && num.symbol == '+')) res.symbol = '-'; else res.symbol = '+'; for (int i = 0; i < value.size(); i++) { BigInteger temp = res; ll carry = 0; temp.value.clear(); for (int j = 0; j < i; j++) temp.value.push_back(0); //因为每一位的权值不一样，所以我就在最低位补零。 for (int j = 0; j < num.value.size(); j++) { ll tmp = (ll)num.value[j] * (ll)value[i] + carry; //两个8位数相乘long long足够存了，所以我用long long运算节省步骤 temp.value.push_back(tmp%BASE); carry = tmp / BASE; } if (carry) temp.value.push_back(carry); res = res + temp; } return res; } BigInteger operator * (const ll &num) const { BigInteger temp = num; return *this * temp; } BigInteger operator / (const BigInteger& num) { //除号的重载我认为是四则运算中最不好想的。在这里我用了一种方法 //将除数放大到和被除数一样的数量级，再看被除数可以被除数减去几次 //（其实我觉得这样的时间复杂度会挺高的，但是蒟蒻的我只能想到这里，希望大佬指教） if (num == 0) return -1; if (*this == 0) return 0; if (symbol == '+' && num.symbol == '+' && *this < num) return 0; if (symbol == '+' && num.symbol == '-' && *this < -num) return 0; if (symbol == '-' && num.symbol == '+' && -*this < num) return 0; if (symbol == '-' && num.symbol == '-' && *this > num) return 0; BigInteger res, a = *this; string str; //这里存结果，用long long会溢出，BigInteger不好操作，string我认为是最方便的。 res.value.clear(); if ((symbol == '+' && num.symbol == '-') || (symbol == '-' && num.symbol == '+')) res.symbol = '-'; else res.symbol = '+'; int len = abs((int)(value.size() - num.value.size()))*WIDTH + log10(value.back()) - log10(num.value.back()); //我在这里使用了log10取对数，这样就可以统计出真实的位数差。（注意log这里不能加绝对值） do { BigInteger b = num * pow(10, len);//放大 int tmp = 0; for (tmp; a >= b; tmp++)//循环相减 a -= b; str.push_back('0' + tmp); } while (len--); for (int i = 0; i < (int)(str.length()) - 1; i++) { //除去前导零 if (str[i] == '0') str.erase(str.begin() + i); else break; } res = str; return res; } BigInteger operator ++ ()//自加自减，不用说了吧 { return *this + 1; } BigInteger operator -- () { return *this - 1; } BigInteger operator += (const BigInteger& num)//这下面的其实可以不用返回值的 { *this = *this + num; return *this; } BigInteger operator -= (const BigInteger& num) { *this = *this - num; return *this; } BigInteger operator *= (const BigInteger& num) { *this = *this * num; return *this; } BigInteger operator /= (const BigInteger& num) { *this = *this / num; return *this; } //逻辑运算符的重载。逻辑运算符只需要重载一个就可以推出所有的了。具体看下面 bool operator < (const BigInteger &num) const { if (symbol == '-' && num.symbol == '+') return true; if (symbol == '+' && num.symbol == '-') return false; bool flag = false, res = false;//flag用来判断是否同负。 if (symbol == '-') flag = true; if (value.size() != num.value.size()) res = value.size() < num.value.size(); else { for (int i = value.size() - 1; i >= 0; i--) { if (value[i] > num.value[i]) { res = false; break; } else if (value[i] < num.value[i]) { res = true; break; } } } if (flag)//同负则相反 return !res; return res; } //下面的逻辑运算符都可以直接重载出来了 bool operator > (const BigInteger& num) const { return num < *this; } bool operator >= (const BigInteger& num) const { return !(num > *this); } bool operator <= (const BigInteger& num) const { return !(num < *this); } bool operator == (const BigInteger& num) const { return !((num > *this) || (num < *this)); } //下面是流输入输出的重载。为什么重载在外面下面有说明。这里说一下这个friend //friend意思是友元函数。网上的解释是： //友元函数是指某些虽然不是类成员函数却能够访问类的所有成员的函数。类授予它的友元特别的访问权，这样该友元函数就能访问到类中的所有成员。 //但是我用的不是类而是结构体，所以可以不写下面的这两行。结构体的数据都是公开的。 friend ostream& operator << (ostream &out, const BigInteger& num); friend istream& operator >> (istream &in, BigInteger& num); }; istream& operator >> (istream &in, BigInteger& num) { string s; if (!(in >> s)) return in; //没有输入就等待 //（其实上面那一句我有点不懂，那个注释只是我猜的。如果有大佬知道的话希望可以教一下我） num = s; return in;//这几个地方的return是为了连写。（下面有讲） } ostream& operator << (ostream &out, const BigInteger& num) { if (num.symbol == '-')//先输出符号 out << num.symbol; out << num.value.back();//最高位不用补零，优先输出 for (int i = num.value.size() - 2; i >= 0; i--) { char buf[20]; sprintf(buf, "%08d", num.value[i]);//将整数补零输出到数组buf中 for (int j = 0; j < strlen(buf); j++) out << buf[j];//输出数组 } return out; } ``` 如果有大佬发现什么问题的话请在评论区留言。（本蒟蒻看到后会修改的） 最后修改：2019 年 06 月 10 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏