c++实现大整数-数据结构

在C++中，整型有short int,long int ,long long，其中long long可表示范围最大，为[-2^63+1 , 2^63-1].但当遇到需要表示更大的整数的时候，就需要其他的方法来解决了。题主在刷算法题的时候遇到需要用大整数表示的题目，做完后特地对大整数类的部分常用运算和操作符进行完善与补充，并封装成类。 C++大整数的本质为容器(最好为顺序容器)，原理为将一个整数的每个基数用容器的每个元素表示，比如若整数“12345”用大整数表示，容器的每个元素的值为a[4]=1,a[3]=2,a[2]=3,a[1]=4,a[0]=5.

头文件 “BigInt.h”

//大整数-数据结构 //已实现加减乘运算以及>,<,!=,==,-,<<,>>等操作符 //除法运算待完善 //自增 自减运算符还未重载 //该文件未进行类成员函数声明与定义的分离， #pragma once #include <iostream> using namespace std; #include<assert.h> #include<algorithm> #include <vector> class BigInt :public vector<int> { private: bool NonNegative = true;//是否为非负数 //正整数处理进位 void PositiveProccessDigit() { for (size_t i = 0;i < this->size();i++) { if (at(i) >= 0 && at(i) < 10) continue;//[0,10)不用进位 if (at(i) >= 10) { if (i == this->size() - 1) this->push_back(0); this->at(i + 1) += (at(i) / 10); at(i) %= 10; } else { this->at(i + 1) -= 1; at(i) += 10; } } this->NonNegative = true; } //负整数处理进位 void NegativeProccessDigit() { for (size_t i = 0;i < this->size();i++) { if (at(i) > -10 && at(i) <= 0) continue;//(-10,0]不用退位 if (at(i) <= -10) { if (i == this->size() - 1) this->push_back(0); this->at(i + 1) += (at(i) / 10); at(i) %= 10; } else { this->at(i + 1) += 1; at(i) -= 10; } } this->NonNegative = false; } public: //=================================================================// //默认构造 BigInt() = default; //有参构造 BigInt(const int& num) { if(num==0) return; if (num < 0) { this->push_back(num); this->NegativeProccessDigit(); } else if (num > 0) { this->push_back(num); this->PositiveProccessDigit(); } } //拷贝构造 BigInt(const BigInt& vec) = default; //赋值构造 BigInt& operator=(const BigInt& x) = default; //=================================================================// BigInt operator+(const int& num) const { return this->operator+(BigInt(num)); } friend BigInt operator+(const int& num, const BigInt& x) { return BigInt(num).operator+(x); } BigInt& operator+=(const int& num) { *this = this->operator+(BigInt(num)); return*this; } BigInt operator+(const BigInt& x) const { if (x.NonNegative!=this->NonNegative) return x.operator-(-*this);//异号取相反数转减法 BigInt ret; ret.resize(1+(this->size() > x.size() ? this->size() : x.size())); size_t min_size= (this->size()<x.size() ? this->size() : x.size()); for(size_t i=0;i< min_size;++i) { ret.at(i)=this->at(i)+x.at(i); } if (this->NonNegative) ret.PositiveProccessDigit(); else ret.NegativeProccessDigit(); while (ret.size() && ret[ret.size() - 1] == 0) ret.pop_back(); return ret; } BigInt& operator+=(const BigInt& x) { *this = this->operator+(x); return *this; } //=================================================================// BigInt operator-(const int& num) const { return this->operator-(BigInt(num)); } friend BigInt operator-(const int& num, const BigInt& x) { return BigInt(num).operator-(x); } BigInt& operator-=(const int& num) { *this=this->operator-(BigInt(num)); return*this; } BigInt operator-(const BigInt& x) const { bool flag=true; if (*this < x)flag=false; else if(*this==x) return BigInt(); BigInt ret(*this); BigInt y(x); size_t max_size = this->size() > x.size() ? this->size() : x.size(); ret.resize(max_size); y.resize(max_size); for (size_t i = 0;i < max_size;++i) { ret.at(i)-= y.at(i); } if (flag==true) ret.PositiveProccessDigit(); else ret.NegativeProccessDigit(); while (ret.size() && ret[ret.size() - 1] == 0) ret.pop_back(); return ret; } BigInt& operator-=(const BigInt& x) { *this = this->operator-(x); return *this; } //=================================================================// friend BigInt operator-(const BigInt& x) {//取相反数 BigInt ret(x); ret.NonNegative = !x.NonNegative;//取相反符 for (auto& val : ret) { val = -val; } return ret; } //=================================================================// BigInt operator/(const int& num) const { assert(num != 0);//被除数为0强制弹出 if (this->empty())//当前大整数不为0时才继续 return BigInt(); BigInt ret; ret.resize(this->size()); if (num < 0&& this->NonNegative|| num >0 && !this->NonNegative) { ret.NonNegative = false; } int y = 0;//每一次拿来与num比较的部分 for (int i = this->size()-1;i >= 0;i--) { y = y * 10 + at(i); ret[i] = (y / num); y %= num; } while (ret.size() && ret[ret.size() - 1] == 0) ret.pop_back(); return ret; } BigInt& operator/=(const int& num) { *this = this->operator/(num); return *this; } //=================================================================// BigInt operator*(const int& num)const{ return this->operator*(BigInt(num)); } friend BigInt operator*(const int& num, const BigInt& x) { return x.operator*(num); } BigInt& operator*=(const int& num) { *this= this->operator*(BigInt(num)); return *this; } BigInt operator*(const BigInt& x)const { BigInt ret; ret.resize(this->size()+ x.size()); for (size_t i = 0;i < this->size();++i){ for (int j = 0;j < x.size();++j){ ret.at(i+j)+=(this->at(i) * x.at(j)); } } if (this->NonNegative== x.NonNegative) { ret.NonNegative = true; ret.PositiveProccessDigit(); } else { ret.NonNegative = false; ret.NegativeProccessDigit(); } while (ret.size() && ret[ret.size() - 1] == 0) ret.pop_back(); return ret; } BigInt& operator*=(const BigInt& x){ *this = this->operator*(x); return *this; } //=================================================================// bool operator<(const BigInt& num) const { if (this->NonNegative == false && num.NonNegative == true) return true; if (this->NonNegative == true && num.NonNegative == false) return false; if (this->size() != num.size()) return this->size()<num.size(); if (this->size() == 0) return false; int i = this->size() - 1; for (;i > 0 && this->at(i) == num.at(i);i--) {} return this->at(i) < num.at(i); } bool operator>(const BigInt& num) const { if (this->NonNegative == false && num.NonNegative == true) return false; if (this->NonNegative == true && num.NonNegative == false) return true; if (this->size() != num.size()) return this->size() > num.size(); if (this->size() == 0) return false; int i = this->size() - 1; for (;i > 0 && this->at(i) == num.at(i);--i) {} return this->at(i) > num.at(i); } //=================================================================// bool operator==(const BigInt& num) const { if (this->size() != num.size()||this->NonNegative!= num.NonNegative) return false; if (this->size() == 0) return true; for (int i = this->size() - 1;i >= 0;--i) { if (this->at(i) != num.at(i)) return false; } return true; } bool operator!=(const BigInt& num) const { return !this->operator==(num); } //=================================================================// friend ostream& operator<<(ostream& output, const BigInt& x) { if (x.empty()) return output << 0; if (x.NonNegative == false){ cout << '-'; for (int i = x.size() - 1;i >= 0;i--){ output << -x.at(i); } } else { for (int i = x.size() - 1;i >= 0;i--){ output << x.at(i); } } return output; } friend istream& operator>>(istream& input,BigInt& x) { x.clear(); insert_iterator<BigInt> pInsert = inserter(x, x.begin()); char ch; input >>noskipws>> ch; bool flag = true;//标记是否输入负数 if (ch == '-'){ flag = false; cin >> ch; } while (ch >= 48 && ch <= 57) { *pInsert = ch-48; input >> ch; } assert(ch=='\n'||ch==' '|| ch >= 48 && ch <= 57); reverse(x.begin(),x.end());//记得调转 if(!flag) x = -x; return input>>skipws; } };

##测试用例 源文件"main.cpp"

int main() { BigInt a(123); BigInt b(-234); int c = 345; //加 cout << (a + b) << endl;// -111 //减 cout << (a - b) << endl;// 357 //乘 cout << (a * b) << endl;// -28782 //除 cout << (a / c) << endl;// 0 //取相反数-，大于>、等于==,小于<,等略。 return EXIT_SUCCESS; }