bignum.cpp

C++大数类

#include <iostream>
#include <string>


using namespace std;

#define DLLCLASS_API _declspec(dllexport)

const int MAXLEN=2000;//分配数组大小
const int MAXN=100000;//定义每单元最大值
const int NodeLen=4;//log10(MAXN)


class DLLCLASS_API BigNum//定义大数类
{
private:
	int num[MAXLEN];
	int len;//大数位数，真实位数len*NodeLen
public:
	BigNum(){len = 1;memset(num,0,sizeof(num));}//默认值为0 
    BigNum(const int b);
	BigNum(const char in[],int strlen);
    BigNum(const BigNum & T); 

	void Set(const int b);
    int Cmp(const BigNum &) const; 
    BigNum & operator=(const BigNum &); 
    BigNum & Add(const BigNum &); 
    BigNum & Sub(const BigNum &); 
    BigNum operator+(const BigNum &) const; 
    BigNum operator-(const BigNum &) const; 
    BigNum operator*(const BigNum &) const; 
    BigNum operator/(const int   &) const; 
    void Print(); 
};

//定义初始值为整数 
BigNum::BigNum(const int b) 
{ 
   int c,d = b; 

   len = 0;
   memset(num,0,MAXLEN); 
   while(d >= MAXN)
   {
      c = d % MAXN; 
      d = d / MAXN; 
      num[len++] = c; 
   } 
   num[len++] = d; 
}

//
BigNum::BigNum(const char in[],int strlen)
{
	int i,temp;
	len=(strlen-1)/NodeLen+1;//very good
	memset(num,0,MAXLEN);
	for(i=strlen-1;i>=0;i--)
	{
		temp=i/NodeLen;
		num[temp]=num[temp]*10+in[strlen-1-i]-'0';
	}

}

//
BigNum::BigNum(const BigNum & T) : len(T.len) 
{ 
   int i; 
   memset(num,0,MAXLEN); 
   for(i = 0 ; i < len ; i++) 
      num[i] = T.num[i]; 
}

void BigNum::Set(const int b)
{
   int c,d = b; 

   len = 0;
   memset(num,0,MAXLEN); 
   while(d >= MAXN)
   {
      c = d % MAXN; 
      d = d / MAXN; 
      num[len++] = c; 
   } 
   num[len++] = d; 

}

int BigNum::Cmp(const BigNum & T) const
{
	int l;
	if(len>T.len)return 1;
	else if(len<T.len)return -1;
	else
	{
	    l=len-1;
	    while(num[l]==T.num[l]&&l>=0)l--;
        if(l=0&&num[l]==T.num[l])return 0;
	    else if(num[l]>T.num[l])return 1;
	    else return -1;
	}
}

//重载赋值运算 
BigNum & BigNum::operator=(const BigNum & n) 
{
	int i;
    len = n.len; 
    memset(num,0,MAXLEN); 
    for(i = 0 ; i < len ; i++)
        num[i] = n.num[i]; 
    return *this; 
} 

//
BigNum & BigNum::Add(const BigNum & T) 
{ 
   int i,big;

   big = T.len > len ? T.len : len; 
   for(i = 0 ; i < big ; i++) 
   { 
      num[i] = num[i] + T.num[i]; 
      if(num[i] >= MAXN) 
      {
         num[i+1]++; 
         num[i] = num[i] - MAXN; 
      } 
   }
   if(num[big] != 0) len = big + 1; 
   else len = big; 

   return *this; 
} 

//不支持负数
BigNum & BigNum::Sub(const BigNum & T) 
{ 
   int i,j,big; 

   big = T.len > len ? T.len : len; 
   for(i = 0 ; i < big ; i++){ 
      if(num[i] < T.num[i]){ 
         j = i + 1; 
         while(num[j] == 0) j++; 
         num[j--]--; 
         while(j > i) num[j--] += MAXN - 1; 
         num[i] = num[i] + MAXN - T.num[i]; 
      } 
      else num[i] -= T.num[i]; 
   } 
   len = big; 
   while(num[len-1] == 0 && len > 1) len--; 
   return *this; 
} 

BigNum BigNum::operator+(const BigNum & n) const 
{ 
   BigNum a = *this; 

   a.Add(n); 
   return a; 
}
 
BigNum BigNum::operator-(const BigNum & T) const 
{ 
   BigNum b = *this; 

   b.Sub(T); 
   return b; 
}
 
BigNum BigNum::operator*(const BigNum & T) const 
{ 
   BigNum ret; 
   int i,j,up; 
   int temp,temp1; 

   for(i = 0 ; i < len ; i++)
   { 
      up = 0; 
      for(j = 0 ; j < T.len ; j++)
	  { 
         temp = num[i] * T.num[j] + ret.num[i+j] + up; 
         if(temp >= MAXN)
		 {
             temp1 = temp % MAXN;
             up = temp / MAXN;
             ret.num[i+j] = temp1;
         }
         else {
            up = 0; 
            ret.num[i+j] = temp; 
         }
      } 
      if(up != 0) 
         ret.num[i+j] = up; 
   }
   ret.len = i + j; 
   while(ret.num[ret.len - 1] == 0 && ret.len > 1) ret.len--; 
   return ret; 
}
 
BigNum BigNum::operator/(const int & b) const 
{ 
   BigNum ret; 
   int i,down = 0;

   for(i = len - 1 ; i >= 0 ; i--)
   { 
      ret.num[i] = (num[i] + down * MAXN ) / b; 
      down = num[i] + down * MAXN - ret.num[i] * b; 
   } 
   ret.len = len;
   while(ret.num[ret.len - 1] == 0) ret.len--; 
   return ret; 
}
 
void BigNum::Print() 
{ 
   int i; 

   cout << num[len - 1]; 
   for(i = len - 2 ; i >= 0 ; i--){ 
      cout.width(NodeLen); 
      cout.fill('0'); 
      cout << num[i]; 
   } 
   cout << endl; 
}