程序代码：
#ifndef __BIGINT__H__
#define __BIGINT__H__
#include<iostream>
#include<deque>
#include<string>
#include<cassert>
#include<exception>
class BigInt
{
public:
explicit BigInt(int i);
BigInt(const BigInt &other);
BigInt(const std::string &);
~BigInt();
friend BigInt operator += (BigInt &, const BigInt &);
friend BigInt operator -= (BigInt &, const BigInt &);
friend BigInt operator *= (BigInt &, int );
friend BigInt operator *= (BigInt &, const BigInt &);
friend BigInt operator +(const BigInt & , const BigInt & );
friend BigInt operator -(const BigInt & , const BigInt & );
friend BigInt operator - (const BigInt &);
friend BigInt operator *(const BigInt & , int);
friend BigInt operator *( const int ,const BigInt &);
friend BigInt operator *(const BigInt & , const BigInt & );
friend bool operator == (const BigInt &, const BigInt & );
friend bool operator > ( const BigInt &, const BigInt &);
friend bool operator < ( const BigInt &, const BigInt & );
friend bool operator >= ( const BigInt &, const BigInt &);
friend bool operator <= ( const BigInt &, const BigInt &);
BigInt & operator = (const BigInt &);
friend std::ostream & operator << ( std::ostream & out, BigInt &bg);
friend BigInt fab(const BigInt &);
friend BigInt pow ( const BigInt &,int );
protected:
void trim(){
while( 0 == dt.back() )
{
dt.pop_back();
}
}
private:
bool sign;
static const unsigned int Base;
std::deque<unsigned int> dt;
};
const unsigned int BigInt::Base =10000;
BigInt::BigInt(int i=0)
{
sign= i >= 0? true: false;
i = i > 0 ? i : -i;
assert(dt.empty());
for ( ; i > 0; i /= Base)
{
dt.push_back(i%Base);
}
}
BigInt::BigInt(const BigInt &other)
{
assert(this->dt.empty());
dt=other.dt;
sign=other.sign;
}
BigInt & BigInt::operator = (const BigInt & other)
{
this->sign=other.sign;
this->dt=other.dt;
return *this;
}
BigInt::BigInt( const std::string & s)
{
try{
std::string::const_reverse_iterator it=s.rbegin();
for( ; it!=s.rend(); it++)
{
if ( * it == '-' || (* it <='9' && * it >='0'))
{
if( *it != '-')
dt.push_back((unsigned)( *it-'0' ));
else
sign=false;
}
else
throw std::exception();
}
}catch ( std::exception e)
{
std::cerr<<e.what()<<std::endl;
}
}
BigInt::~BigInt()
{
dt.clear();
}
std::ostream & operator << ( std::ostream & out, BigInt &bg)
{
if( 0 == bg.dt.size())
out<< unsigned(0);
if( !bg.sign)
out<<"-";
std::deque<unsigned int>::const_reverse_iterator rit = bg.dt.rbegin();
for( ; rit != bg.dt.rend() ; rit++ )
{
out<<*rit;
}
return out;
}
BigInt operator - (const BigInt & bg)
{
BigInt ret(bg);
ret.sign=!ret.sign;
return ret;
}
bool operator == ( const BigInt& op1 , const BigInt &op2)
{
return op1.sign==op2.sign && op1.dt== op2.dt;
}
bool operator > ( const BigInt &op1, const BigInt & op2)
{
if( op1.sign> op2.sign)
return true;
if ( op1 == op2 )
return false;
if( op1.dt.size()== op2.dt.size())
{
std::deque<unsigned>::const_reverse_iterator it,jt;
it=op1.dt.rbegin();
jt=op2.dt.rbegin();
while( *it == *jt && it != op1.dt.rend() && jt !=op2.dt.rend() )
{
it++;
jt++;
}
if( op1.sign > 0 )
return *it > *jt;
else
return *it < *jt;
}
else
{
if( op1.sign > 0 )
return op1.dt.size()>op2.dt.size()? true:false;
else
return op1.dt.size()>op2.dt.size()? false: true;
}
}
bool operator >= ( const BigInt & op1, const BigInt & op2 )
{
return op1 == op2 || op1 > op2;
}
bool operator <= ( const BigInt & op1, const BigInt & op2 )
{
return op1 == op2 || op1 < op2;
}
bool operator < ( const BigInt & op1, const BigInt & op2)
{
if( op1.sign > op2.sign)
return true;
else if( op1.sign < 0 && op2.sign <0 )
{
return fab(op1) > fab(op2) ;
}
else
return ! (op1 > op2);
}
BigInt operator += ( BigInt & op1,const BigInt & op2 )
{
if (op1.sign != op2.sign)
{
BigInt tmp(op2);
tmp=-tmp;
op1-=tmp;
return op1;
}
BigInt bg,other;
bg=fab(op1)>fab(op2)?op1:op2;
other= bg==op1? op2: op1;
unsigned int carry = 0;
std::deque<unsigned int>::iterator it;
std::deque<unsigned int>::const_iterator jt;
for( it = bg.dt.begin(),jt = other.dt.begin(); it < bg.dt.end() || jt < other.dt.end() || carry > 0 ; )
{
if( it < bg.dt.end() && jt < other.dt.end() )
{
carry += * it + *jt ;
*it = carry % BigInt::Base;
carry /= BigInt::Base;
it ++;
jt ++;
}
else if ( it < bg.dt.end() )
{
carry += *it;
*it = carry % BigInt::Base;
carry /= BigInt::Base;
it ++;
}
else if( jt< other.dt.end())
{
carry += *jt;
bg.dt.push_back(carry % BigInt::Base);
carry /= BigInt::Base;
jt++;
}
else
{
while ( carry > 0 )
{
bg.dt.push_back(carry%BigInt::Base);
carry /= BigInt::Base;
}
}
}
op1=bg;
return op1;
}
BigInt operator + ( const BigInt & op1, const BigInt & op2 )
{
BigInt ret(op1);
ret+=op2;
return ret;
}
BigInt operator -=( BigInt & bg, const BigInt &other )
{
if ( bg.sign != other.sign )
{
BigInt tmp(other);
tmp=-tmp;
bg+=tmp;
return bg;
}
int carry=0;
BigInt op1,op2;
if ( bg.dt.size() == other.dt.size() )
{
op1 = bg.dt.back() >= other.dt.back() ? bg: other;
op2 = bg.dt.back() >= other.dt.back() ? other: bg;
}
else
{
op1 = bg.dt.size() > other.dt.size()? bg:other;
op2 = bg.dt.size() > other.dt.size()? other:bg;
}
op1.sign= (op1 == bg );
assert( op1.dt.size() >= op2.dt.size() );
std::deque<unsigned int>::iterator it;
std::deque<unsigned int>::const_iterator jt;
try
{
for( it = op1.dt.begin(),jt = op2.dt.begin(); it< op1.dt.end()||jt<op2.dt.end()|| carry < 0; )
{
if( it < op1.dt.end() && jt<op2.dt.end() )
{
carry += (int) *it- (int)*jt;
*it= carry >=0 ? (unsigned)(carry % BigInt::Base) :(unsigned) (carry + BigInt::Base)% BigInt::Base;
carry = carry >= 0 ? carry/BigInt::Base: -((-carry + BigInt::Base)/(BigInt::Base));
it++;
jt++;
}
else if ( it < op1.dt.end() )
{
carry += (int)* it;
*it= carry >=0 ?(unsigned) (carry % BigInt::Base) :(unsigned) (carry + BigInt::Base)% BigInt::Base;
carry = carry >= 0 ? carry/BigInt::Base: -((-carry + BigInt::Base)/(BigInt::Base));
it++;
}
else if( jt < op2.dt.end() )
{
throw std::exception();
}
}
}catch( std::exception e )
{
std::cerr<<e.what()<<std::endl;
}
op1.trim();
bg=op1;
return bg;
}
BigInt operator -( const BigInt & op1, BigInt &op2)
{
BigInt ret(op1);
ret-=op2;
return ret;
}
BigInt operator *= ( BigInt & bg, int other)
{
bg.sign = bg.sign== (other>=0?true:false) ? true:false;
other = other>=0? other:-other;
unsigned int carry=0;
if ( 0 == other )
{
bg.dt.clear();
bg.dt.push_back(0);
return bg;
}
std::deque<unsigned int>::iterator it=bg.dt.begin();
for( ; it != bg.dt.end(); it ++ )
{
carry += *it* other;
*it= carry % BigInt::Base;
carry /= BigInt::Base;
}
while ( carry > 0 )
{
bg.dt.push_back(carry%BigInt::Base);
carry/=BigInt::Base;
}
return bg;
}
BigInt operator * ( int n, BigInt & other)
{
BigInt bg(other);
bg*=n;
return bg;
}
BigInt operator *( const int n,const BigInt & bg)
{
BigInt ret(bg);
ret*=n;
return ret;
}
BigInt operator *=(BigInt& op1, const BigInt & op2)
{
if ( op1 == BigInt(0) || op2 == BigInt(0) )
return BigInt (0);
BigInt out(0);
BigInt tmp;
int carry=0;
for( std::deque<unsigned>::const_iterator it = op2.dt.begin(); it != op2.dt.end();it ++,carry++ )
{
tmp= op1* (*it);
for( int i=0;i<carry; i++)
{
tmp.dt.push_front(unsigned(0));
}
out+=tmp;
}
op1=out;
op1.sign= !op1.sign ^ op2.sign;
return op1;
}
BigInt operator * ( const BigInt &op1, const BigInt & op2 )
{
BigInt ret(op1);
ret*=op2;
return ret;
}
BigInt operator * ( const BigInt & op1, int other)
{
BigInt ret(op1);
ret*=other;
return ret;
}
BigInt fab( const BigInt & bg)
{
BigInt ret(bg);
ret.sign=true;
return ret;
}
BigInt pow( const BigInt & bg, int n)
{
assert( n >= 0 );
if ( n == 0 )
return BigInt(0);
BigInt ret(bg);
for( int i=0; i < n-1 ; i++)
{
ret*=bg;
}
return ret;
}
#endif
