[FZH] 写了个大数库，欢迎拍砖。

[Devil Wang]

*
*
2010/6/7 严晶涛 <yanjingtao在innlab.net>

> explicit BigInt(int i);这里为啥用显式？直接赋值多好。。。
>

如果你编译过我的code,你就会知道为什么要显示赋值了。

>
> 在 2010年6月6日 下午11:18，Devil Wang <wxjeacen在gmail.com>写道：
>
> > *
> > *#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 =10;
> >
> > 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;
> > }
> >
> > #include<climits>
> > #include<ctime>
> > int main()
> > {
> >    BigInt sum(0);
> >    for( int i =1 ; i<=10;i++)
> >    {
> >    BigInt temp=pow(BigInt(i),i);
> >    sum+=temp;
> >    }
> >    std::cout<<sum<<std::endl;
> > }
> >
> > --
> > Thanks & Regards
> >
> > Linux Developer : Devil Wang
> > _______________________________________________
> > Chinese mailing list
> > Chinese at lists.fedoraproject.org
> > https://admin.fedoraproject.org/mailman/listinfo/chinese
> >
>
>
>
> --
> 此致
> 严晶涛
> _______________________________________________
> Chinese mailing list
> Chinese at lists.fedoraproject.org
> https://admin.fedoraproject.org/mailman/listinfo/chinese
>



-- 
Thanks & Regards

Linux Developer : Devil Wang