大整数类-白红宇

大整数类

阅读量：6973 次

发布时间：2019-06-27

本文共 26202 字，大约阅读时间需要 87 分钟。

参考来源：

#include
    
       #include
     
        #include
      
         #include
       
          using namespace std;  class BigInt  {  public:      BigInt();      BigInt(long int s);      BigInt(string str);      BigInt(BigInt& a);      BigInt operator=(BigInt a);      friend BigInt operator+(BigInt a,BigInt b);      friend BigInt operator-(BigInt a,BigInt b);      friend BigInt operator*(BigInt a,BigInt b);      friend BigInt operator/(BigInt a,BigInt b);//除法算法不太好      friend ostream& operator<<(ostream& out,BigInt& a);      friend istream& operator>>(istream& in,BigInt& a);      friend int SizeJudge(BigInt a,BigInt b);  private:    vector
        
          vec;      int negative;//0为正，1为负  };  BigInt::BigInt()  {      vec.push_back(0);      negative = 0;  }  BigInt::BigInt(long int s)  {      if(s<0)      {          negative = 1;          s = -s;      }      else          negative = 0;      int i;      while(s>9)      {          i = s%10;          vec.push_back(i);          s /=10;      }      vec.push_back(s);  }  BigInt::BigInt(string str)  {      if(str[0] == '-')      {          negative = 1;          str = str.substr(1,str.size()-1);      }      else          negative = 0;      for(int i=str.size()-1;i>=0;i--)      {          vec.push_back(str[i]-'0');      }  }  BigInt::BigInt(BigInt& a)  {      vec = a.vec;      negative = a.negative;  }  BigInt BigInt::operator=(BigInt a)  {      vec = a.vec;      negative = a.negative;      return *this;  }  ostream& operator<<(ostream& out,BigInt& a)  {      string str="";      int judge = 0;      if((a.vec[a.vec.size()-1]+'0') == '-')          judge = 1;      if((a.negative == 1)&&judge == 0)      {          str += '-';      }      for(int i=a.vec.size()-1;i>=0;i--)      {          str += (a.vec[i]+'0');      }      out<
         
          >(istream& in,BigInt& a) { string str=""; in>>str; a.vec.clear(); for(int i=str.size()-1;i>=0;i--) { a.vec.push_back(str[i]-'0'); } return in; } BigInt operator+(BigInt a,BigInt b) { int negative_judge = 0; if(a.negative == 1&&b.negative == 1)//全负 { negative_judge = 1; } if(a.negative == 0&&b.negative == 0)//全正 { negative_judge = 0; } if(a.negative == 0&&b.negative == 1)//a正b负 { b.negative = 0; return (a-b); } if(a.negative == 1&&b.negative == 0)//a负b正 { a.negative = 0; return (b-a); } BigInt c,tmp; int alen,blen,min,max,i; alen = a.vec.size(); blen = b.vec.size(); if(alen>blen) { c.vec = a.vec; tmp.vec = b.vec; min = blen; max = alen; } else { c.vec = b.vec; tmp.vec = a.vec; min = alen; max = blen; } for(i=0;i
          
           9) { c.vec[i] -= 10; c.vec[i+1] += 1; } } c.vec[i] +=tmp.vec[i]; if(c.vec[i]>9) { c.vec[i] -=10; if(min == max) c.vec.push_back(1); else c.vec[i+1] +=1; } for(i=min;i
           
            9) { c.vec[i] -=10; c.vec[i+1] +=1; } } if(c.vec[max-1]>9) { c.vec[max-1] -=10; c.vec.push_back(1); } i=c.vec.size()-1;//去掉前面的0 while(c.vec[i] == 0) { c.vec.pop_back(); i--; } if(negative_judge == 1) { string str = "-"; c.vec.push_back(str[0]-'0'); } return c; } BigInt operator-(BigInt a,BigInt b) { int negative_judge = 0; if(a.negative == 1&&b.negative == 1)//全负 { a.negative = 0; b.negative = 0; return (b-a); } if(a.negative == 0&&b.negative == 0)//全正 { negative_judge = 0; } if(a.negative == 0&&b.negative == 1)//a正b负 { b.negative = 0; return (a+b); } if(a.negative == 1&&b.negative == 0)//a负b正 { b.negative =1; return (a+b); } BigInt c,tmp; int alen,blen,min,max,i,judge=0; alen = a.vec.size(); blen = b.vec.size(); //大值赋给c，小值赋给tmp if(alen>blen) { c.vec = a.vec; tmp.vec = b.vec; min = blen; max = alen; judge = 1; } else if(alen == blen) { for(i=alen-1;i>=0;i--) { if(a.vec[i]>b.vec[i]) { c.vec = a.vec; tmp.vec = b.vec; min = blen; max = alen; judge = 1; break; } else if(a.vec[i]
            
             tmp { c.vec[i] -= tmp.vec[i]; if(c.vec[i]<0) { c.vec[i] += 10; c.vec[i+1] -= 1; } } if(min
             
              9) { if(i+j+1
              
               0) { j *=10; i--; } BigInt count(j); tmp = count*b; if(SizeJudge(a,tmp) == 1) { while(SizeJudge(a,tmp) == 1) { count = count+1; tmp = b*count; } } else if(SizeJudge(a,tmp) == -1) { while(SizeJudge(a,tmp) == -1) { count = count-1; tmp = b*count; } } if((a.negative == 0&&b.negative == 1)||(a.negative == 1&&b.negative == 0))//a正b负//a负b正 { string str="-"; count.vec.push_back(str[0]-'0'); count.negative = 1; } else { count.negative = 0; } return count; } int SizeJudge(BigInt a,BigInt b) {//1代表大于，0代表等于，-1代表小于 int alen,blen,i; alen = a.vec.size(); blen = b.vec.size(); if(alen>blen) { return 1; } else if(alen == blen) { for(i=alen-1;i>=0;i--) { if(a.vec[i]>b.vec[i]) { return 1; } else if(a.vec[i]
               
                >b; //cout<<"the input:"<
                <
                 
                  0) { c = c*a; a = a-1; i--; } cout<<"30! = "<
                  
                   <

//简化的template 
    
         class big_int    {    public:        big_int();        big_int(int int_value);        big_int(unsigned char *buffer, size_t size);        big_int(const big_int &that);        big_int &operator = (const big_int &that);        ~big_int();    protected:        Array
     
       m_aValue;        bool m_bPositive;    public:        big_int operator +(const big_int &that) const;        big_int operator -(const big_int &that) const;    };			template 
      
           big_int
       
        ::big_int(): m_bPositive(true)    {    }			template 
        
             big_int
         
          ::big_int(unsigned char *buffer, size_t size) : m_bPositive(true) { for (size_t i = 0; i < size / sizeof(T); ++i, buffer += sizeof(T)) { m_aValue.PushBack(*(T *)buffer); } size_t rest = size % sizeof(T); if (rest > 0) { T val = 0; unsigned char *p = (unsigned char *)&val; for (size_t i = 0; i < rest; ++i) { p[i] = buffer[i]; } m_aValue.PushBack(val); } } template 
          
            big_int
           
            ::big_int(int int_value) : m_bPositive(true) { unsigned long long val = (unsigned long long)int_value; if (int_value < 0) { val = (unsigned long long)-int_value; m_bPositive = false; } while (val > 0) { m_aValue.PushBack((T)val); val >>= sizeof(T) * 8; } } template 
            
              big_int
             
              ::big_int(const big_int &that) : m_bPositive(true) { this->m_bPositive = that.m_bPositive; this->m_aValue = that.m_aValue; } template 
              
                big_int
               
                 &big_int
                
                 ::operator = (const big_int
                 
                   &that) { if (this != &that) { this->m_aValue = that.m_aValue; this->m_bPositive = that.m_bPositive; } return *this; } template 
                  
                    big_int
                   
                    ::~big_int() { } template 
                    
                      big_int
                     
                       big_int
                      
                       ::operator +(const big_int
                       
                         &addend) { if (this->m_bPositive != addend.m_bPositive) { big_int
                        
                          subtrahend = addend; subtrahend.Neg(); Sub(subtrahend); return *this; } const Array
                         
                           &rhs = addend.m_aValue; Array
                          
                            &res = this->m_aValue; for (size_t i = 0; i < rhs.Size(); ++ i) { T overflow = 0; while (res.Size() <= i) { res.PushBack((T)0); } res[i] += rhs[i]; if (res[i] < rhs[i]) { ++overflow; } for (size_t j = i + 1; overflow > 0; ++j) { if (res.Size() <= j) { res.PushBack((T)0); } res[j] += overflow; if (res[j] < overflow) { overflow = 1; } else { overflow = 0; } } } big_int
                           
                             ret(*this); return ret; } template 
                            
                              big_int
                             
                               big_int
                              
                               ::operator -(const big_int
                               
                                 &subtrahend) { if (this->m_bPositive != subtrahend.m_bPositive) { big_int
                                
                                  addend = subtrahend; addend.Neg(); Add(subtrahend); big_int
                                 
                                   ret(*this); return ret.Sub(that); } if (*this == subtrahend) { m_bPositive = true; m_aValue.Clear(); big_int
                                  
                                    ret(*this); return ret.Sub(that); } if (*this < subtrahend) { big_int
                                   
                                     minuend = subtrahend; minuend.Sub(*this); minuend.Neg(); *this = minuend; big_int
                                    
                                      ret(*this); return ret.Sub(that); } const Array
                                     
                                       &rhs = subtrahend.m_aValue; Array
                                      
                                        &res = this->m_aValue; for (size_t i = 0; i < rhs.Size(); ++ i) { T overflow = 0; T original = res[i]; res[i] -= rhs[i]; if (res[i] > original) { ++overflow; } for (size_t j = i + 1; overflow > 0; ++j) { original = res[j]; res[j] -= overflow; if (res[j] > original) { overflow = 1; } else { overflow = 0; } } } while (!res.Empty() && *res.ReverseBegin() == 0) { res.Delete(res.ReverseBegin()); } big_int
                                       
                                         ret(*this); return ret.Sub(that); }

#ifndef __XLBigIntT_H_4ED560E8_F226_4D72_9016_828D1AA8696E_INCLUDED__#define __XLBigIntT_H_4ED560E8_F226_4D72_9016_828D1AA8696E_INCLUDED__#include 
    
     #include 
     
      #include 
      
       namespace xl{    template 
       
            class BigIntT    {    public:        BigIntT();        BigIntT(char char_value);        BigIntT(unsigned char uchar_value);        BigIntT(short short_value);        BigIntT(unsigned short ushort_value);        BigIntT(int int_value);        BigIntT(unsigned int uint_value);        BigIntT(long long_value);        BigIntT(unsigned long ulong_value);        BigIntT(long long int64_value);        BigIntT(unsigned long long uint64_value);        BigIntT(unsigned char *buffer, size_t size);        BigIntT(const wchar_t *string_value, unsigned int base = 10, const String &alphabet = L"0123456789ABCDEF");        BigIntT(const String &string_value, unsigned int base = 10, const String &alphabet = L"0123456789ABCDEF");        BigIntT(const BigIntT &that);        BigIntT &operator = (const BigIntT &that);        ~BigIntT();    protected:        Array
        
          m_aValue;        bool m_bPositive;    public:        bool IsPositive() const;        Array
         
           GetData() const; public: bool operator ==(const BigIntT &that) const; bool operator !=(const BigIntT &that) const; bool operator <(const BigIntT &that) const; bool operator >(const BigIntT &that) const; bool operator <=(const BigIntT &that) const; bool operator >=(const BigIntT &that) const; public: BigIntT &Neg(); BigIntT &Inc(); BigIntT &Dec(); BigIntT &Add(const BigIntT &addend); BigIntT &Sub(const BigIntT &subtrahend); BigIntT Mul(const BigIntT &multiplicator) const; BigIntT Div(const BigIntT &divisor, BigIntT &remainder) const; BigIntT Exp(const BigIntT &exponent) const; BigIntT ExpMod(const BigIntT &exponent, const BigIntT &divisor) const; public: BigIntT operator -() const; BigIntT &operator ++(); BigIntT operator ++(int); BigIntT &operator --(); BigIntT operator --(int); BigIntT operator +(const BigIntT &that) const; BigIntT operator -(const BigIntT &that) const; BigIntT operator *(const BigIntT &that) const; BigIntT operator /(const BigIntT &that) const; BigIntT operator %(const BigIntT &that) const; BigIntT &operator +=(const BigIntT &that); BigIntT &operator -=(const BigIntT &that); BigIntT &operator *=(const BigIntT &that); BigIntT &operator /=(const BigIntT &that); BigIntT &operator %=(const BigIntT &that); public: char ToChar() const; short ToShort() const; int ToInt() const; long ToLong() const; long long ToLongLong() const; public: BigIntT &FromString(const wchar_t *string_value, unsigned int base = 10, const String &alphabet = L"0123456789ABCDEF"); BigIntT &FromString(const String &string_value, unsigned int base = 10, const String &alphabet = L"0123456789ABCDEF"); String ToString(unsigned int base = 10, const String &alphabet = L"0123456789ABCDEF") const; }; typedef BigIntT
          
            BigInt; template 
           
             BigIntT
            
             ::BigIntT() : m_bPositive(true) { } template 
             
               BigIntT
              
               ::BigIntT(char char_value) : m_bPositive(true) { unsigned long long val = (unsigned long long)char_value; if (char_value < 0) { val = (unsigned long long)-char_value; m_bPositive = false; } while (val > 0) { m_aValue.PushBack((T)val); val >>= sizeof(T) * 8; } } template 
               
                 BigIntT
                
                 ::BigIntT(unsigned char uchar_value) : m_bPositive(true) { unsigned long long val = (unsigned long long)uchar_value; while (val > 0) { m_aValue.PushBack((T)val); val >>= sizeof(T) * 8; } } template 
                 
                   BigIntT
                  
                   ::BigIntT(short short_value) : m_bPositive(true) { unsigned long long val = (unsigned long long)short_value; if (short_value < 0) { val = (unsigned long long)-short_value; m_bPositive = false; } while (val > 0) { m_aValue.PushBack((T)val); val >>= sizeof(T) * 8; } } template 
                   
                     BigIntT
                    
                     ::BigIntT(unsigned short ushort_value) : m_bPositive(true) { unsigned long long val = (unsigned long long)ushort_value; while (val > 0) { m_aValue.PushBack((T)val); val >>= sizeof(T) * 8; } } template 
                     
                       BigIntT
                      
                       ::BigIntT(int int_value) : m_bPositive(true) { unsigned long long val = (unsigned long long)int_value; if (int_value < 0) { val = (unsigned long long)-int_value; m_bPositive = false; } while (val > 0) { m_aValue.PushBack((T)val); val >>= sizeof(T) * 8; } } template 
                       
                         BigIntT
                        
                         ::BigIntT(unsigned int uint_value) : m_bPositive(true) { unsigned long long val = (unsigned long long)uint_value; while (val > 0) { m_aValue.PushBack((T)val); val >>= sizeof(T) * 8; } } template 
                         
                           BigIntT
                          
                           ::BigIntT(long long_value) : m_bPositive(true) { unsigned long long val = (unsigned long long)long_value; if (long_value < 0) { val = (unsigned long long)-long_value; m_bPositive = false; } while (val > 0) { m_aValue.PushBack((T)val); val >>= sizeof(T) * 8; } } template 
                           
                             BigIntT
                            
                             ::BigIntT(unsigned long ulong_value) : m_bPositive(true) { unsigned long long val = (unsigned long long)ulong_value; while (val > 0) { m_aValue.PushBack((T)val); val >>= sizeof(T) * 8; } } template 
                             
                               BigIntT
                              
                               ::BigIntT(long long int64_value) : m_bPositive(true) { unsigned long long val = (unsigned long long)int64_value; if (int64_value < 0) { val = (unsigned long long)-int64_value; m_bPositive = false; } while (val > 0) { m_aValue.PushBack((T)val); val >>= sizeof(T) * 8; } } template 
                               
                                 BigIntT
                                
                                 ::BigIntT(unsigned long long uint64_value) : m_bPositive(true) { unsigned long long val = (unsigned long long)uint64_value; while (val > 0) { m_aValue.PushBack((T)val); val >>= sizeof(T) * 8; } } template 
                                 
                                   BigIntT
                                  
                                   ::BigIntT(unsigned char *buffer, size_t size) : m_bPositive(true) { for (size_t i = 0; i < size / sizeof(T); ++i, buffer += sizeof(T)) { m_aValue.PushBack(*(T *)buffer); } size_t rest = size % sizeof(T); if (rest > 0) { T val = 0; unsigned char *p = (unsigned char *)&val; for (size_t i = 0; i < rest; ++i) { p[i] = buffer[i]; } m_aValue.PushBack(val); } } template 
                                   
                                     BigIntT
                                    
                                     ::BigIntT(const wchar_t *string_value, unsigned int base = 10, const String &alphabet = L"0123456789ABCDEF") { FromString(string_value, base, alphabet); } template 
                                     
                                       BigIntT
                                      
                                       ::BigIntT(const String &string_value, unsigned int base = 10, const String &alphabet = L"0123456789ABCDEF") { FromString(string_value, base, alphabet); } template 
                                       
                                         BigIntT
                                        
                                         ::BigIntT(const BigIntT &that) : m_bPositive(true) { this->m_bPositive = that.m_bPositive; this->m_aValue = that.m_aValue; } template 
                                         
                                           BigIntT
                                          
                                            &BigIntT
                                           
                                            ::operator = (const BigIntT
                                            
                                              &that) { if (this != &that) { this->m_aValue = that.m_aValue; this->m_bPositive = that.m_bPositive; } return *this; } template 
                                             
                                               BigIntT
                                              
                                               ::~BigIntT() { } template 
                                               
                                                 bool BigIntT
                                                
                                                 ::IsPositive() const { return m_bPositive; } template 
                                                 
                                                   Array
                                                  
                                                    BigIntT
                                                   
                                                    ::GetData() const { return m_aValue; } template 
                                                    
                                                      bool BigIntT
                                                     
                                                      ::operator ==(const BigIntT
                                                      
                                                        &that) const { return (this->m_bPositive == that.m_bPositive) && (this->m_aValue == that.m_aValue); } template 
                                                       
                                                         bool BigIntT
                                                        
                                                         ::operator !=(const BigIntT
                                                         
                                                           &that) const { return !(*this == that); } template 
                                                          
                                                            bool BigIntT
                                                           
                                                            ::operator <(const BigIntT
                                                            
                                                              &that) const { if (this->m_bPositive != that.m_bPositive) { return !this->m_bPositive; } if (this->m_aValue.Size() != that.m_aValue.Size()) { return this->m_aValue.Size() < that.m_aValue.Size(); } if (!this->m_aValue.Empty()) { for (size_t i = this->m_aValue.Size() - 1; true; --i) { if (this->m_aValue[i] != that.m_aValue[i]) { return this->m_aValue[i] < that.m_aValue[i]; } if (i == 0) { break; } } } return false; } template 
                                                             
                                                               bool BigIntT
                                                              
                                                               ::operator >(const BigIntT
                                                               
                                                                 &that) const { if (this->m_bPositive != that.m_bPositive) { return this->m_bPositive; } if (this->m_aValue.Size() != that.m_aValue.Size()) { return this->m_aValue.Size() > that.m_aValue.Size(); } if (!this->m_aValue.Empty()) { for (size_t i = this->m_aValue.Size() - 1; true; --i) { if (this->m_aValue[i] != that.m_aValue[i]) { return this->m_aValue[i] > that.m_aValue[i]; } if (i == 0) { break; } } } return false; } template 
                                                                
                                                                  bool BigIntT
                                                                 
                                                                  ::operator <=(const BigIntT
                                                                  
                                                                    &that) const { if (this->m_bPositive != that.m_bPositive) { return !this->m_bPositive; } if (this->m_aValue.Size() != that.m_aValue.Size()) { return this->m_aValue.Size() < that.m_aValue.Size(); } if (!this->m_aValue.Empty()) { for (size_t i = this->m_aValue.Size() - 1; true; --i) { if (this->m_aValue[i] != that.m_aValue[i]) { return this->m_aValue[i] < that.m_aValue[i]; } if (i == 0) { break; } } } return true; } template 
                                                                   
                                                                     bool BigIntT
                                                                    
                                                                     ::operator >=(const BigIntT
                                                                     
                                                                       &that) const { if (this->m_bPositive != that.m_bPositive) { return this->m_bPositive; } if (this->m_aValue.Size() != that.m_aValue.Size()) { return this->m_aValue.Size() > that.m_aValue.Size(); } if (!this->m_aValue.Empty()) { for (size_t i = this->m_aValue.Size() - 1; true; --i) { if (this->m_aValue[i] != that.m_aValue[i]) { return this->m_aValue[i] > that.m_aValue[i]; } if (i == 0) { break; } } } return true; } template 
                                                                      
                                                                        BigIntT
                                                                       
                                                                         &BigIntT
                                                                        
                                                                         ::Neg() { m_bPositive = !m_bPositive; return *this; } template 
                                                                         
                                                                           BigIntT
                                                                          
                                                                            &BigIntT
                                                                           
                                                                            ::Inc() { Add(1u); return *this; } template 
                                                                            
                                                                              BigIntT
                                                                             
                                                                               &BigIntT
                                                                              
                                                                               ::Dec() { Sub(1u); return *this; } template 
                                                                               
                                                                                 BigIntT
                                                                                
                                                                                  &BigIntT
                                                                                 
                                                                                  ::Add(const BigIntT
                                                                                  
                                                                                    &addend) { if (this->m_bPositive != addend.m_bPositive) { BigIntT
                                                                                   
                                                                                     subtrahend = addend; subtrahend.Neg(); Sub(subtrahend); return *this; } const Array
                                                                                    
                                                                                      &rhs = addend.m_aValue; Array
                                                                                     
                                                                                       &res = this->m_aValue; for (size_t i = 0; i < rhs.Size(); ++ i) { T overflow = 0; while (res.Size() <= i) { res.PushBack((T)0); } res[i] += rhs[i]; if (res[i] < rhs[i]) { ++overflow; } for (size_t j = i + 1; overflow > 0; ++j) { if (res.Size() <= j) { res.PushBack((T)0); } res[j] += overflow; if (res[j] < overflow) { overflow = 1; } else { overflow = 0; } } } return *this; } template 
                                                                                      
                                                                                        BigIntT
                                                                                       
                                                                                         &BigIntT
                                                                                        
                                                                                         ::Sub(const BigIntT
                                                                                         
                                                                                           &subtrahend) { if (this->m_bPositive != subtrahend.m_bPositive) { BigIntT
                                                                                          
                                                                                            addend = subtrahend; addend.Neg(); Add(subtrahend); return *this; } if (*this == subtrahend) { m_bPositive = true; m_aValue.Clear(); return *this; } if (*this < subtrahend) { BigIntT
                                                                                           
                                                                                             minuend = subtrahend; minuend.Sub(*this); minuend.Neg(); *this = minuend; return *this; } const Array
                                                                                            
                                                                                              &rhs = subtrahend.m_aValue; Array
                                                                                             
                                                                                               &res = this->m_aValue; for (size_t i = 0; i < rhs.Size(); ++ i) { T overflow = 0; T original = res[i]; res[i] -= rhs[i]; if (res[i] > original) { ++overflow; } for (size_t j = i + 1; overflow > 0; ++j) { original = res[j]; res[j] -= overflow; if (res[j] > original) { overflow = 1; } else { overflow = 0; } } } while (!res.Empty() && *res.ReverseBegin() == 0) { res.Delete(res.ReverseBegin()); } return *this; } template 
                                                                                              
                                                                                                BigIntT
                                                                                               
                                                                                                 BigIntT
                                                                                                
                                                                                                 ::Mul(const BigIntT
                                                                                                 
                                                                                                   &multiplicator) const { BigIntT
                                                                                                  
                                                                                                    product; const Array
                                                                                                   
                                                                                                     &lhs = this->m_aValue, &rhs = multiplicator.m_aValue; Array
                                                                                                    
                                                                                                      &res = product.m_aValue; if (lhs.Empty() || rhs.Empty()) { return product; } for (size_t i = 0; i < lhs.Size(); ++i) { for (size_t j = 0; j < rhs.Size(); ++j) { unsigned long long temp = lhs[i]; temp *= rhs[j]; for (size_t k = 0; temp > 0; ++k) { while (res.Size() <= i + j + k) { res.PushBack((T)0); } res[i + j + k] += (T)temp; if (res[i + j + k] < (T)temp) { temp >>= sizeof(T) * 8; ++temp; } else { temp >>= sizeof(T) * 8; } } } } if ((this->m_bPositive != multiplicator.m_bPositive) && !res.Empty()) { product.m_bPositive = !product.m_bPositive; } return product; } template 
                                                                                                     
                                                                                                       BigIntT
                                                                                                      
                                                                                                        BigIntT
                                                                                                       
                                                                                                        ::Div(const BigIntT
                                                                                                        
                                                                                                          &divisor, BigIntT
                                                                                                         
                                                                                                           &remainder) const { if (divisor.m_aValue.Empty()) { return 0; } BigIntT
                                                                                                          
                                                                                                            dividend(*this), div(divisor); dividend.m_bPositive = true; div.m_bPositive = true; BigIntT
                                                                                                           
                                                                                                             quotient; while (dividend >= div) { size_t zeros = dividend.m_aValue.Size() - div.m_aValue.Size(); BigIntT
                                                                                                            
                                                                                                              temp; temp.m_aValue.Insert(temp.m_aValue.Begin(), dividend.m_aValue.Begin() + zeros, dividend.m_aValue.End()); unsigned long long a = temp.m_aValue[temp.m_aValue.Size() - 1]; unsigned long long b = div.m_aValue[div.m_aValue.Size() - 1]; if (temp < div) { --zeros; temp.m_aValue.Insert(temp.m_aValue.Begin(), dividend.m_aValue.Begin() + zeros, dividend.m_aValue.Begin() + zeros + 1); a <<= sizeof(T) * 8; a += temp.m_aValue[temp.m_aValue.Size() - 2]; } unsigned long long test = a / b; if (div.m_aValue.Size() >= 2) { while (b * test + ((div.m_aValue[div.m_aValue.Size() - 2] * test) >> sizeof(T) * 8) > a) { --test; } } BigIntT
                                                                                                             
                                                                                                               product = div.Mul(test); while (product > temp) { --test; product = div.Mul(test); } BigIntT
                                                                                                              
                                                                                                                res(test); for (size_t i = 0; i < zeros; ++i) { res.m_aValue.PushFront((T)0); product.m_aValue.PushFront((T)0); } quotient.Add(res); dividend.Sub(product); } remainder = dividend; remainder.m_bPositive = this->m_bPositive; quotient.m_bPositive = (this->m_bPositive == divisor.m_bPositive); return quotient; } template 
                                                                                                               
                                                                                                                 BigIntT
                                                                                                                
                                                                                                                  BigIntT
                                                                                                                 
                                                                                                                  ::Exp(const BigIntT
                                                                                                                  
                                                                                                                    &exponent) const { if (!exponent.m_bPositive) { return 0u; } if (exponent.m_aValue.Empty()) { return 1u; } BigIntT
                                                                                                                   
                                                                                                                     power(1u); for (size_t i = exponent.m_aValue.Size() - 1; true; --i) { T n = exponent.m_aValue[i]; for (T mask = (1u << (sizeof(T) * 8 - 1)); mask > 0; mask >>= 1) { power = power.Mul(power); if ((n & mask) != 0) { power = power.Mul(*this); } } if (i == 0) { break; } } return power; } template 
                                                                                                                    
                                                                                                                      BigIntT
                                                                                                                     
                                                                                                                       BigIntT
                                                                                                                      
                                                                                                                       ::ExpMod(const BigIntT
                                                                                                                       
                                                                                                                         &exponent, const BigIntT
                                                                                                                        
                                                                                                                          &divisor) const { if (!exponent.m_bPositive) { return 0u; } if (exponent.m_aValue.Empty()) { return 1u; } BigIntT
                                                                                                                         
                                                                                                                           power(1u); for (size_t i = exponent.m_aValue.Size() - 1; true; --i) { T n = exponent.m_aValue[i]; for (T mask = (1u << (sizeof(T) * 8 - 1)); mask > 0; mask >>= 1) { power = power.Mul(power); power.Div(divisor, power); if ((n & mask) != 0) { power = power.Mul(*this); power.Div(divisor, power); } } if (i == 0) { break; } } return power; } template 
                                                                                                                          
                                                                                                                            BigIntT
                                                                                                                           
                                                                                                                             BigIntT
                                                                                                                            
                                                                                                                             ::operator -() const { BigIntT
                                                                                                                             
                                                                                                                               ret(*this); return ret.Neg(); } template 
                                                                                                                              
                                                                                                                                BigIntT
                                                                                                                               
                                                                                                                                 &BigIntT
                                                                                                                                
                                                                                                                                 ::operator ++() { return Inc(); } template 
                                                                                                                                 
                                                                                                                                   BigIntT
                                                                                                                                  
                                                                                                                                    BigIntT
                                                                                                                                   
                                                                                                                                    ::operator ++(int) { BigIntT
                                                                                                                                    
                                                                                                                                      ret(*this); Inc(); return ret; } template 
                                                                                                                                     
                                                                                                                                       BigIntT
                                                                                                                                      
                                                                                                                                        &BigIntT
                                                                                                                                       
                                                                                                                                        ::operator --() { return Dec(); } template 
                                                                                                                                        
                                                                                                                                          BigIntT
                                                                                                                                         
                                                                                                                                           BigIntT
                                                                                                                                          
                                                                                                                                           ::operator --(int) { BigIntT
                                                                                                                                           
                                                                                                                                             ret(*this); Dec(); return ret; } template 
                                                                                                                                            
                                                                                                                                              BigIntT
                                                                                                                                             
                                                                                                                                               BigIntT
                                                                                                                                              
                                                                                                                                               ::operator +(const BigIntT
                                                                                                                                               
                                                                                                                                                 &that) const { BigIntT
                                                                                                                                                
                                                                                                                                                  ret(*this); return ret.Add(that); } template 
                                                                                                                                                 
                                                                                                                                                   BigIntT
                                                                                                                                                  
                                                                                                                                                    BigIntT
                                                                                                                                                   
                                                                                                                                                    ::operator -(const BigIntT
                                                                                                                                                    
                                                                                                                                                      &that) const { BigIntT
                                                                                                                                                     
                                                                                                                                                       ret(*this); return ret.Sub(that); } template 
                                                                                                                                                      
                                                                                                                                                        BigIntT
                                                                                                                                                       
                                                                                                                                                         BigIntT
                                                                                                                                                        
                                                                                                                                                         ::operator *(const BigIntT
                                                                                                                                                         
                                                                                                                                                           &that) const { return Mul(that); } template 
                                                                                                                                                          
                                                                                                                                                            BigIntT
                                                                                                                                                           
                                                                                                                                                             BigIntT
                                                                                                                                                            
                                                                                                                                                             ::operator /(const BigIntT
                                                                                                                                                             
                                                                                                                                                               &that) const { BigIntT
                                                                                                                                                              
                                                                                                                                                                reminder; return Div(that, reminder); } template 
                                                                                                                                                               
                                                                                                                                                                 BigIntT
                                                                                                                                                                
                                                                                                                                                                  BigIntT
                                                                                                                                                                 
                                                                                                                                                                  ::operator %(const BigIntT
                                                                                                                                                                  
                                                                                                                                                                    &that) const { BigIntT
                                                                                                                                                                   
                                                                                                                                                                     reminder; Div(that, reminder); return reminder; } template 
                                                                                                                                                                    
                                                                                                                                                                      BigIntT
                                                                                                                                                                     
                                                                                                                                                                       &BigIntT
                                                                                                                                                                      
                                                                                                                                                                       ::operator +=(const BigIntT
                                                                                                                                                                       
                                                                                                                                                                         &that) { return Add(that); } template 
                                                                                                                                                                        
                                                                                                                                                                          BigIntT
                                                                                                                                                                         
                                                                                                                                                                           &BigIntT
                                                                                                                                                                          
                                                                                                                                                                           ::operator -=(const BigIntT
                                                                                                                                                                           
                                                                                                                                                                             &that) { return Sub(that); } template 
                                                                                                                                                                            
                                                                                                                                                                              BigIntT
                                                                                                                                                                             
                                                                                                                                                                               &BigIntT
                                                                                                                                                                              
                                                                                                                                                                               ::operator *=(const BigIntT
                                                                                                                                                                               
                                                                                                                                                                                 &that) { return *this = Mul(that); } template 
                                                                                                                                                                                
                                                                                                                                                                                  BigIntT
                                                                                                                                                                                 
                                                                                                                                                                                   &BigIntT
                                                                                                                                                                                  
                                                                                                                                                                                   ::operator /=(const BigIntT
                                                                                                                                                                                   
                                                                                                                                                                                     &that) { BigIntT
                                                                                                                                                                                    
                                                                                                                                                                                      reminder; return *this = Div(that, reminder); } template 
                                                                                                                                                                                     
                                                                                                                                                                                       BigIntT
                                                                                                                                                                                      
                                                                                                                                                                                        &BigIntT
                                                                                                                                                                                       
                                                                                                                                                                                        ::operator %=(const BigIntT
                                                                                                                                                                                        
                                                                                                                                                                                          &that) { BigIntT
                                                                                                                                                                                         
                                                                                                                                                                                           reminder; Div(that, reminder); return *this = reminder; } template 
                                                                                                                                                                                          
                                                                                                                                                                                            char BigIntT
                                                                                                                                                                                           
                                                                                                                                                                                            ::ToChar() const { long long ret = 0, temp = 0; size_t i = 0; while (i * sizeof(T) < sizeof(char) && m_aValue.Size() > i) { temp = m_aValue[i]; temp <<= i * sizeof(T) * 8; ret |= temp; ++i; } if (!m_bPositive) { ret = - ret; } return (char)ret; } template 
                                                                                                                                                                                            
                                                                                                                                                                                              short BigIntT
                                                                                                                                                                                             
                                                                                                                                                                                              ::ToShort() const { long long ret = 0, temp = 0; size_t i = 0; while (i * sizeof(T) < sizeof(short) && m_aValue.Size() > i) { temp = m_aValue[i]; temp <<= i * sizeof(T) * 8; ret |= temp; ++i; } if (!m_bPositive) { ret = - ret; } return (short)ret; } template 
                                                                                                                                                                                              
                                                                                                                                                                                                int BigIntT
                                                                                                                                                                                               
                                                                                                                                                                                                ::ToInt() const { long long ret = 0, temp = 0; size_t i = 0; while (i * sizeof(T) < sizeof(int) && m_aValue.Size() > i) { temp = m_aValue[i]; temp <<= i * sizeof(T) * 8; ret |= temp; ++i; } if (!m_bPositive) { ret = - ret; } return (int)ret; } template 
                                                                                                                                                                                                
                                                                                                                                                                                                  long BigIntT
                                                                                                                                                                                                 
                                                                                                                                                                                                  ::ToLong() const { long long ret = 0, temp = 0; size_t i = 0; while (i * sizeof(T) < sizeof(long) && m_aValue.Size() > i) { temp = m_aValue[i]; temp <<= i * sizeof(T) * 8; ret |= temp; ++i; } if (!m_bPositive) { ret = - ret; } return (long)ret; } template 
                                                                                                                                                                                                  
                                                                                                                                                                                                    long long BigIntT
                                                                                                                                                                                                   
                                                                                                                                                                                                    ::ToLongLong() const { long long ret = 0, temp = 0; size_t i = 0; while (i * sizeof(T) < sizeof(long long) && m_aValue.Size() > i) { temp = m_aValue[i]; temp <<= i * sizeof(T) * 8; ret |= temp; ++i; } if (!m_bPositive) { ret = - ret; } return (long long)ret; } template 
                                                                                                                                                                                                    
                                                                                                                                                                                                      BigIntT
                                                                                                                                                                                                     
                                                                                                                                                                                                       &BigIntT
                                                                                                                                                                                                      
                                                                                                                                                                                                       ::FromString(const wchar_t *string_value, unsigned int base = 10, const String &alphabet = L"0123456789ABCDEF") { m_aValue.Clear(); m_bPositive = true; if (base < 2 || base > (unsigned int)alphabet.Length()) { return *this; } size_t begin = 0; bool positive = true; if (string_value[begin] == L'-') { positive = false; ++begin; } Map
                                                                                                                                                                                                       
                                                                                                                                                                                                         alphabet_reverse; for (unsigned char i = 0; i < alphabet.Length(); ++i) { alphabet_reverse.Insert(alphabet[i], i); } for (size_t i = begin; string_value[i] != '\0'; ++i) { wchar_t ch = string_value[i]; Map
                                                                                                                                                                                                        
                                                                                                                                                                                                         ::Iterator it = alphabet_reverse.Find(ch); if (it == alphabet_reverse.End()) { break; } *this = (*this) * base + it->Value; } this->m_bPositive = positive; return *this; } template 
                                                                                                                                                                                                         
                                                                                                                                                                                                           BigIntT
                                                                                                                                                                                                          
                                                                                                                                                                                                            &BigIntT
                                                                                                                                                                                                           
                                                                                                                                                                                                            ::FromString(const String &string_value, unsigned int base = 10, const String &alphabet = L"0123456789ABCDEF") { return FromString(string_value, base, alphabet); } template 
                                                                                                                                                                                                            
                                                                                                                                                                                                              String BigIntT
                                                                                                                                                                                                             
                                                                                                                                                                                                              ::ToString(unsigned int base = 10, const String &alphabet = L"0123456789ABCDEF") const { if (base < 2 || base > (unsigned int)alphabet.Length()) { return L""; } BigIntT
                                                                                                                                                                                                              
                                                                                                                                                                                                                temp(*this); temp.m_bPositive = true; String ret; const unsigned int EXP[] = { 0, 0, 1, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4 }; unsigned int exp = 0; if (base <= 16 && ((exp = EXP[base]) != 0)) { for (size_t i = m_aValue.Size() - 1; true; --i) { T val = m_aValue[i]; T mask = base - 1; unsigned int bits = 0; while ((mask & (1 << (sizeof(T) * 8 - 1))) == 0) { mask *= base; bits += exp; } if (i == m_aValue.Size() - 1) { while ((mask & val) == 0) { mask /= base; bits -= exp; } } while (mask != 0) { ret.AppendBack(alphabet[(val & mask) >> bits]); mask /= base; bits -= exp; } if (i == 0) { break; } } } else { do { BigIntT
                                                                                                                                                                                                               
                                                                                                                                                                                                                 reminder; temp = temp.Div(base, reminder); ret.AppendFront(alphabet[reminder.ToChar()]); } while (temp > 0u); } if (!this->m_bPositive) { ret.AppendFront(L'-'); } return ret; }} // namespace xl#endif // #ifndef __XLBigIntT_H_4ED560E8_F226_4D72_9016_828D1AA8696E_INCLUDED__