using namespace std;
CBigInt :: CBigInt() : values(""), flag(true)
{
}
CBigInt :: CBigInt(const int i)
{
values.clear() ;
if (i >= 0) flag = true ;
else
flag = false ;
int v = abs(i) ;
while(v)
{
values.push_back(char('0' + (v % 10))) ;
v /= 10 ;
}
reverse(values.begin(), values.end()) ;
if (values.empty())
{
values.push_back('0') ;
flag = true ;
}
}
CBigInt :: CBigInt(const string& strValues)
{
setValue(strValues) ; //Calling member function
}
CBigInt :: CBigInt(const CBigInt& bigInt) : values(), flag()
{
}
CBigInt :: ~CBigInt()
{}
const CBigInt CBigInt :: absolute() const
{
CBigInt ret(*this) ;
= true ;
return ret ;
}
int CBigInt :: compareBitInt(const CBigInt& rhs)const
{
//State number situation
if (flag && !) return 1 ;
if (!flag && ) return -1 ;
//In the case of the same number, first compare the absolute value, and then judge the size according to the symbol
int ret = 0 ;
if (values.length() > .length()) ret = 1 ;
else
if (values.length() < .length()) ret = -1 ;
else
ret = values.compare() ;
if (flag) return ret ;
return -ret ;
}
void CBigInt :: setValue(const string& strValues)
{
values.clear() ;
string tmpStr(() + strValues.find_first_not_of(' '), ()) ; //Remove the spaces in front
if (tmpStr.empty())
{
values.push_back('0') ;
flag = true ;
return ;
}
if (tmpStr.at(0) == '-' )
flag = false ;
else
flag = true ;
int i = tmpStr.find_first_of("0123456789") ;
int j = tmpStr.find_last_of("0123456789") ;
values = tmpStr.substr(i, j - i + 1) ;//All numbers starting after the sign bit until the first non-digit bit is encountered
}
CBigInt& CBigInt :: operator = (const CBigInt& rhs)
{
this->values = ;
this->flag = ;
return *this ;
}
ostream& operator << (ostream& ou, const CBigInt& bigInt)
{
if (!)
ou << '-';
ou << ;
return ou ;
}
istream& operator >> (istream& in, CBigInt& bigInt)
{
string str ;
in >> str ;
bigInt.setValue(str) ; //Set the new value read in
return in ;
}
const CBigInt operator + (const CBigInt& lhs, const CBigInt& rhs)
{
CBigInt ret ;
if ( == ) //The symbol is the same
{
string lvalues() , rvalues() ;
reverse(lvalues.begin(), lvalues.end()) ;
reverse(rvalues.begin(), rvalues.end()) ;
// Addition by bit
int i = 0;
for ( ; i < lvalues.length() && i < rvalues.length(); ++ i)
.push_back(lvalues.at(i) + rvalues.at(i) - '0') ;
if (i < lvalues.length())
for (; i < lvalues.length(); ++ i)
.push_back(lvalues.at(i)) ;
else
for (; i < rvalues.length(); ++ i)
.push_back(rvalues.at(i)) ;
//Processing carry
int carry = 0;
for (int i = 0; i < .length(); ++ i)
{
int newValue = .at(i) - '0' + carry ;
carry = newValue/ 10 ;
.at(i) = newValue - carry * 10 + '0' ;
}
if (carry)
.push_back(carry + '0') ;
//Processing symbols
= ;
}
else //The symbols are different
{
CBigInt absL = lhs.absolute() ;
CBigInt absR = rhs.absolute() ;
int compFlag = absL.compareBitInt(absR) ;
if (compFlag == 0)
{
ret.setValue("0") ;
= true ;
return ret ;
}
else
{
if (compFlag == -1) //Switch positions so that absL > absR
{
CBigInt tmp(absL) ;
absL = absR ;
absR = tmp ;
}
reverse(.begin(), .end()) ;
reverse(.begin(), .end()) ;
//Processing the difference
int i = 0;
for (; i < .length() && i < .length(); ++ i)
.push_back(.at(i) - .at(i) + '0') ;
if (i < .length()) //Impossible if i < ()
for (; i < .length(); ++ i)
.push_back(.at(i)) ;
//Processing borrowing
int carry = 0 ;
for (i = 0; i < .length(); ++ i)
{
int newValue = .at(i) - carry - '0' ;
if (newValue < 0) carry = 1 ; //Borrow a position forward
else carry = 0 ;
.at(i) = newValue + carry * 10 + '0' ;
}
//Processing symbols
if (compFlag == 1)
= ;
else
= ;
}
}
reverse(.begin(), .end()) ;
int i = .find_first_not_of(" 0") ;
if (i == string :: npos)//Empty, the result is 0
{
ret.setValue("0") ;
= true ;
return ret ;
}
= string(.begin() + .find_first_not_of(" 0"), .end()) ; //Remove the previous blanks and 0
return ret ;
}
const CBigInt operator - (const CBigInt& lhs, const CBigInt& rhs)
{
CBigInt tmpRhs(rhs) ;
= ! ; //Get negative sign
return (lhs + tmpRhs) ;
}
//Multiple operator overload
const CBigInt operator * (const CBigInt& lhs, const CBigInt& rhs)
{
CBigInt ret ;
int flag1 = lhs.compareBitInt(CBigInt(0)) ;
int flag2 = rhs.compareBitInt(CBigInt(0)) ;
if (flag1 == 0 || flag2 == 0)
{
ret.setValue("0") ;
= true ;
return ret ;
}
if ( == )
= true ;//The same number is positive, and the same number is negative
else
= false ;
string lvalues(), rvalues() ;
reverse(lvalues.begin(), lvalues.end()) ;
reverse(rvalues.begin(), rvalues.end()) ;
.resize(lvalues.size() + rvalues.size(), '0') ;
//Multiple together
for (int i = 0; i < lvalues.size(); ++ i)
for (int j = 0; j < rvalues.size(); ++ j)
{
int newValue = [i + j] + (lvalues[i] - '0') * (rvalues[j] - '0') - '0';
int carry = newValue / 10 ;
[i + j] = newValue % 10 + '0' ;
//The reason for carrying each bit here is to prevent overflow, such as '0' + 9 * 9 = 48 + 81 > 127 has already overflowed
for (int k = i + j + 1; carry != 0 && k < .size(); ++ k) //Processing carry
{
[ k - 1 ] = newValue % 10 + '0' ;
newValue = [k] + carry - '0';
[k] = newValue % 10 + '0' ;
carry = newValue / 10 ;
}
}
reverse(.begin(), .end()) ; //Flip
= string(.begin() + .find_first_not_of(" 0"), .end()) ; //Remove the previous blanks and 0
return ret ;
}
const CBigInt operator / (const CBigInt& lhs, const CBigInt& rhs) //Divide operation overload
{
CBigInt ret ;
assert(rhs.compareBitInt(CBigInt(0)) != 0) ;
ret.setValue("0") ; //Initialize to 0
CBigInt absL(()) ;
CBigInt absR(()) ;
int comFlag = absL.compareBitInt(absR) ;
if (comFlag < 0)
return ret ;
if(comFlag == 0)
{
ret.setValue("1") ;
if ( == ) = true ;
else
= false ;
return ret ;
}
int movCount = .size() - .size() ;
const CBigInt tenBigInt(10) ;
//Use subtraction to achieve division
do
{
CBigInt tmp(absR) ;
for (int i = 0; i < movCount; ++ i) //tmp is movCount power of 10
tmp = tmp * tenBigInt ;
int addNum = 0 ;
while(absL.compareBitInt(tmp) >= 0)
{
absL = absL - tmp ;
addNum ++ ;
}
ret = ret * tenBigInt + CBigInt (addNum) ;
movCount -- ;
}while (movCount >= 0);
if ( == ) = true ;
else
= false ;
return ret ;
}
const CBigInt operator % (const CBigInt& lhs, const CBigInt& rhs) //Module operation operator overload
{
CBigInt divTmp = lhs / rhs ;
return (lhs - rhs * divTmp) ;
}