HugeInt 大整数的四则运算

Leave a reply

h

/*-------------------------------------------------------*
* CopyRight 2007 北京交通大学         
*              
* 最后修改日期:2007-4-7                                        
*              
* 文件名:HugeInt.h          
*              
* 描述：HugeInt类的定义文件，定义了四则运算的接口
*              
---------------------------------------------------------*/
#include <iostream>

const int MAXLEN=2000;
class HugeInt
{
public:
 //构造函数
 HugeInt();
 HugeInt(const int& iOperand);

 //拷贝函数
 void operator =(int iOperand);
 void operator =(HugeInt &hOperand);

 //IO接口

 friend std::ostream& operator <<(std::ostream& out,HugeInt &R);

 //关系运算接口
 bool operator == (HugeInt &R);
 bool operator == (const int &iOperand);
 bool operator != (HugeInt &R);
 bool operator != (const int &R);
 
 bool operator <= (HugeInt &R);
 bool operator <= (const int &R);
 bool operator < (HugeInt &hInt);
 bool operator < (const int &iOperand);

 bool operator >= (HugeInt &hOperand);
 bool operator >= (const int &iOperand);
 bool operator > (HugeInt &hOperand);
 bool operator > (const int &iOperand);

 //加法接口

 HugeInt operator + (HugeInt &hOperand);
 HugeInt operator + (int iOperand);
 HugeInt& operator += (HugeInt &R);
 HugeInt& operator += (int R);
 HugeInt& operator ++ ();//前置
 void operator ++ (int);//后置

 //减法接口
 HugeInt operator - (HugeInt& hOperand);
 HugeInt operator - (int iOperand);
 void  operator -= (HugeInt &hOperand);
 void operator -= (const int &iOperand);
 void operator -- ();
 void operator -- (int);
 
 //除法接口
 HugeInt operator /(HugeInt &hOperand);
 HugeInt operator /(int R);
 HugeInt& operator /=(HugeInt &hOperand);
 HugeInt& operator /=(int iOperand);
 

 //乘法接口
 HugeInt operator *(HugeInt &R);
 HugeInt operator *(int R);
 HugeInt& operator *=(HugeInt &R);
 HugeInt& operator *=(int R);
 
 //输出接口
 Print();

 //公用接口
 int Len(){return m_len;}
 HugeInt FillTen(HugeInt &hInt,int start,int end,int len);
 HugeInt TakeHigh(HugeInt &hInt,int start,int end);

private:

 int m_sign;    //符号
 int m_len;    //长度
 char m_num[MAXLEN];  //存储空间
};

cpp

/*-------------------------------------------------------*
* CopyRight 2007 北京交通大学                       *
*              
* 最后修改日期:2007-4-7                                             
*              
* 文件名:HugeInt.cpp         
*                                                       
* 描述：HugeInt类的实现文件，实现了四则运算
*                                                       
---------------------------------------------------------*/
 
#include "HugeInt.h"
#include <iostream>
#include <memory>
#include <cmath>
using namespace std;

HugeInt::HugeInt()
{
 memset(m_num,0,sizeof(char)*MAXLEN);
 m_sign=0;
 m_len=0;
}


HugeInt::Print()
{
 int i;
 if(m_sign==-1)
  std::cout<<"-";
 for(i=m_len;i!=0;i--)
  std::cout<<m_num[i]+0;
 std::cout<<std::endl;
}

HugeInt::HugeInt(const int & ioperand)
{
 memset(m_num,0,sizeof(char)*MAXLEN);
 if(ioperand!=0)
 {
  if(ioperand>0)
   m_sign=1;
  else
   m_sign=-1;
  int i=0,k=1;
  int abs_R=abs(ioperand);
  do
  {
  i++;
  m_num[i]=abs_R%10;
  abs_R/=10;
  }while(abs_R);
  m_len=i;
 }
 else
 {
  m_num[1]=0;
  m_len=1;
  m_sign=1;
 }
}

HugeInt HugeInt::operator +(HugeInt &hOperand)
{
 if(this->m_sign==-1 && hOperand.m_sign==-1)
 {
  HugeInt hTmp1(*this),hTmp2(hOperand),hTmp;
  hTmp1.m_sign=1;
  hTmp2.m_sign=1;
  hTmp=hTmp1+hTmp2;
  hTmp.m_sign=-1;
  return hTmp;
 }
 else if(this->m_sign==-1 && hOperand.m_sign==1)
 {
  HugeInt hTmp1(*this),hTmp;
  hTmp1.m_sign=1;
  hTmp=hOperand-hTmp1;
  return hTmp;
 }
 else if(this->m_sign==1 && hOperand.m_sign==-1)
 {
  HugeInt hTmp1(hOperand),hTmp;
  hTmp1.m_sign=1;
  hTmp=*this-hTmp1;
  return hTmp;
 }
 else
 {
  HugeInt Result(0);
  char *p,*q,*r;
  p=q=r=NULL;
  int len1,len2;
  if(Len()>hOperand.Len())
  {
   p=this->m_num;
   q=hOperand.m_num;
   r=Result.m_num;
   len1=Len();
   len2=hOperand.Len();
  }
  else
  {
   p=hOperand.m_num;
   q=this->m_num;
   r=Result.m_num;
   len1=hOperand.Len();
   len2=Len();
  }
  int i=1,j=1,k=1,carry=0;
  
  while(j<=len2)
  {
   r[k]=p[i++]+q[j++]+carry;
   carry=r[k]/10;
   r[k]%=10;
   k++;
  }
  while(i<=len1)
  {
   r[k]=p[i++]+carry;
   carry=r[k]/10;
   r[k]%=10;
   k++;
  }
  if(carry>0)
  {
   r[k]=carry;
   Result.m_len=k;
  }
  else
  {
   Result.m_len=k-1;
  }
  Result.m_sign=1;
  return Result;
 }


}

HugeInt &HugeInt::operator +=(HugeInt &hoperand)
{
 *this=*this+hoperand;
 return *this;
}


HugeInt& HugeInt::operator ++()
{
 *this=*this+1;
 return *this;
}

HugeInt HugeInt::operator +(int ioperand)
{
 HugeInt hInt(ioperand);
 return (*this)+hInt;
}

void HugeInt::operator =(int iOperand)
{
 if(iOperand!=0)
 {
  if(iOperand>0)
   m_sign=1;
  else
   m_sign=-1;
  int i=0,k=1;
  int abs_R=abs(iOperand);
  do
  {
  i++;
  m_num[i]=abs_R%10;
  abs_R/=10;
  }while(abs_R);
  m_len=i;
 }
 else
 {
  m_num[1]=0;
  m_len=1;
  m_sign=1;
 }
}

HugeInt& HugeInt::operator +=(int R)
{
 HugeInt hInt=R;
 *this=*this+hInt;
 return *this;
}

HugeInt HugeInt::operator *(HugeInt &R)
{
 HugeInt Result=0;
 Result.m_sign=this->m_sign*R.m_sign;
 char *muti1,*muti2,*result=Result.m_num;
 int len1,len2;
 if(this->m_len>R.Len())
 {
  muti1=this->m_num;
  muti2=R.m_num;
  len1=this->m_len;
  len2=R.m_len;
 }
 else
 {
  muti1=R.m_num;
  muti2=this->m_num;
  len2=this->m_len;
  len1=R.m_len;
 }
 

 int i=1,j=1,k=1,carry=0;
 
 
 while(j<=len2)
 {
  i=1;
  k=j;
  while(i<=len1)
  {
   result[k]+=muti1[i++]*muti2[j]+carry;
   carry=result[k]/10;
   result[k]%=10;
   k++;
  }
  if(carry!=0)
  {
   result[k]+=carry;
   Result.m_len=k;
   carry=0;
  }
  else
  {
   Result.m_len=k-1;
  }
  j++;
 }
 return Result;
}

HugeInt HugeInt::operator *(int R)
{
 HugeInt hInt=R;
 return (*this)*hInt;
}
bool HugeInt::operator !=(HugeInt &R)
{
 if(R.m_len==this->m_len&&R.m_sign==this->m_sign)
 {
  int i;
  for(i=1;i<=this->m_len;i++)
   if(m_num[i]!=R.m_num[i])
    return true;
  return false;
 }
 else
  return true;
}

bool HugeInt::operator !=(const int &R)
{
 HugeInt hInt(R);
 if(hInt.m_len==this->m_len && hInt.m_sign==this->m_sign)
 {
  int i;
  for(i=1;i<=this->m_len;i++)
   if(m_num[i]!=hInt.m_num[i])
    return true;
  return false;
 }
 else
  return true;
}

bool HugeInt::operator <=(HugeInt &R)
{
 if(*this == R)
  return true;
 
 if (this->m_sign==-1 && R.m_sign==1)
 {
  return true;
 }
 else if (this->m_sign==1 && R.m_sign==-1)
 {
  return false;
 }
 else if (this->m_sign==-1 && R.m_sign==-1)
 {
  HugeInt hTmp1(*this),hTmp2(R);
  hTmp1.m_sign=1;
  hTmp2.m_sign=1;
  return !(hTmp1<=hTmp2);
 }
 else
 {
    
  if(this->m_len==R.m_len)
  {
   int i=1;
   for(i=R.m_len;i!=0;i--)
   {
    if(this->m_num[i]<R.m_num[i])
    {
     return true;
    }
    else if(this->m_num[i]>R.m_num[i])
     return false;
   }
    return true;
  }
  else
  {
   if(this->m_len<R.m_len)
    return true;
   else
    return false;
  }
 }

}

bool HugeInt::operator <=(const int &R)
{
 HugeInt hInt=R;
 return (*this)<=hInt;
}

HugeInt& HugeInt::operator *=(HugeInt &R)
{
 *this=(*this)*R;
 return *this;
}

HugeInt& HugeInt::operator *=(int R)
{
 HugeInt hInt=R;
 *this=*this*hInt;
 return *this;
}

std::ostream& operator <<(std::ostream &out,HugeInt &R)
{
 int i;
 if(R.m_sign==-1)
  out<<"-";
 for(i=R.m_len;i!=0;i--)
  out<<R.m_num[i]+0;
 out<<std::endl;
 return out;
}

bool HugeInt::operator <(HugeInt &hOperand)
{
 if(this->m_sign==1 && hOperand.m_sign==1)
 {
  if(this->m_len==hOperand.m_len)
  {
   for (int i=m_len;i!=0;i--)
   {
    if(this->m_num[i]<hOperand.m_num[i])
     return true;
    else if(this->m_num[i]>hOperand.m_num[i])
     return false;
   }
   return false;
  }
  else
  {
   if(this->m_len<hOperand.m_len)
    return true;
   else
    return false;
  }
 }
 else if(this->m_sign==1 && hOperand.m_sign==-1)
 {
  return false;
 }
 else if (this->m_sign==-1 && hOperand.m_sign==1)
 {
  return true;
 }
 else if (this->m_sign==-1 && hOperand.m_sign==-1)
 {
  HugeInt hTmp1(*this),hTmp2(hOperand);
  hTmp1.m_sign=1;
  hTmp2.m_sign=1;
  return !(hTmp1<hTmp2);
 }
 return false;
}


HugeInt HugeInt::operator -(HugeInt &hOperand)
{
 int iLen1,iLen2,i=1,j=1,k=1;
 char *ptr1,*ptr2,*ptr3;
 if (*this == hOperand)
 {
  HugeInt hTmp(0);
  return hTmp;
 }
 
 if (this->m_sign==-1 && hOperand.m_sign==-1)
 {
  HugeInt hTmp1(hOperand),hTmp;
  hTmp1.m_sign=1;
  hTmp=*this+hTmp1;
  hTmp.m_sign=-1;
  return hTmp;
 }
 else if (this->m_sign==-1 && hOperand.m_sign==1)
 {
  HugeInt hTmp1(*this),hTmp2(hOperand),hTmp;
  hTmp1.m_sign=1;
  hTmp2.m_sign=1;
  hTmp=hTmp1+hTmp2;
  hTmp.m_sign=-1;
  return hTmp;
 }
 else if (this->m_sign==1 && hOperand.m_sign==-1)
 {
  HugeInt hTmp1(hOperand);
  hTmp1.m_sign=1;
  return *this+hTmp1;
 }
 else
 {
  HugeInt hResult=0;
  if((*this)<hOperand)
  {
   iLen2=this->m_len;
   iLen1=hOperand.m_len;
   ptr2=this->m_num;
   ptr1=hOperand.m_num;
   hResult.m_sign=-1;
  }
  else
  {
   iLen1=this->m_len;
   iLen2=hOperand.m_len;
   ptr1=this->m_num;
   ptr2=hOperand.m_num;
   hResult.m_sign=1;
  }
  ptr3=hResult.m_num;
  while(j<=iLen2)
  {
   if(ptr1[i]<ptr2[j])
   {
    --ptr1[i+1];
    ptr3[k]=ptr1[i]+10-ptr2[j];
   }
   else
   {
    ptr3[k]=ptr1[i]-ptr2[j];
   }
   i++;
   j++;
   k++;
  }
  while(i<=iLen1)
  {
   if(ptr1[i]<0)
   {
    --ptr1[i+1];
    ptr3[k]=ptr1[i]+10;
    
   }
   else
   {
    ptr3[k]=ptr1[i];
   }
   k++;
   i++;
  }
  for(int iCount=k;ptr3[iCount]==0;iCount--);
  hResult.m_len=iCount;
  return hResult;
 }


}


HugeInt HugeInt::operator /(HugeInt &hOperand)
{
 HugeInt hResult,h1=*this,tmp;
 if(h1==hOperand)
 {
  hResult=1;
  hResult.m_sign=1;
 }
 else if(h1<hOperand)
  hResult=0;
 else
 {
  int i1,i2,n;
  hResult.m_sign=h1.m_sign*hOperand.m_sign;
  while(hOperand<=h1)
  {
   i1=i2=h1.m_len;
   n=1;
   while(TakeHigh(h1,i1,i2)<=hOperand)
    i2--;
   if(TakeHigh(h1,i1,i2+1)==hOperand)
   {
    ++i2;
   }
   if(hResult.m_len==0)
    hResult.m_len=i2;
   tmp=TakeHigh(h1,i1,i2);
   
   while(hOperand*n<=tmp)
   {
    n++;
   }
   tmp=hOperand*(n-1);
   

   h1=h1-FillTen(tmp,tmp.m_len,1,tmp.m_len+i2-1);

   hResult.m_num[i2]+=n-1;
  }
 }
 return hResult;
}

HugeInt HugeInt::TakeHigh(HugeInt &hInt,int start,int end)
{
 HugeInt hResult=0;
 hResult.m_len=start-end+1;
 int i,j=hResult.m_len;
 for(i=start;i>=end;i--,j--)
 {
  hResult.m_num[j]=hInt.m_num[i];
 }
 return hResult;
}
HugeInt HugeInt::FillTen(HugeInt &hInt,int start,int end,int len)
{
 HugeInt hResult;
 hResult.m_len=len;
 int i=start,j=hResult.m_len;
 while(i>=end)
 {
  hResult.m_num[j--]=hInt.m_num[i--];
 }
 return hResult;
}

void HugeInt::operator --()
{
 *this=*this-1;
}

bool HugeInt::operator ==(HugeInt &hOperand)
{
 if(this->m_len!=hOperand.m_len || this->m_sign!=hOperand.m_sign)
  return false;
 else
 {
  int i;
  for(i=1;i<=hOperand.m_len;i++)
   if(this->m_num[i]!=hOperand.m_num[i])
    return false;
  return true;
 }
}

void HugeInt::operator =(HugeInt &hOperand)
{
 this->m_len=hOperand.m_len;
 this->m_sign=hOperand.m_sign;
 memcpy(this->m_num,hOperand.m_num,sizeof(char)*MAXLEN);
}

HugeInt HugeInt::operator /(int iOperand)
{
 HugeInt hInt(iOperand);
 return *this/hInt;
}

HugeInt& HugeInt::operator /=(HugeInt &hOperand)
{
 *this=*this/hOperand;
 return *this;
}

HugeInt &HugeInt::operator /=(int iOperand)
{
 HugeInt hTmp(iOperand);
 *this=*this/hTmp;
 return *this;
}

void HugeInt::operator ++(int)
{
 *this=*this+1;
}
HugeInt HugeInt::operator -(int iOperand)
{
 HugeInt hTmp(iOperand);
 return *this-hTmp;
}

void HugeInt::operator -- (int)
{
 *this=*this-1;
 
}

bool HugeInt::operator < (const int &iOperand)
{
 HugeInt hTmp(iOperand);
 return *this<hTmp;
}

bool HugeInt::operator >=(HugeInt &hOperand)
{
 if(*this == hOperand)
  return true;

 if(this->m_sign==1 && hOperand.m_sign==-1)
  return true;
 else if(this->m_sign==-1 && hOperand.m_sign==1)
  return false;
 else if(this->m_sign==-1 && hOperand.m_sign==-1)
 {
  HugeInt hTmp1(*this),hTmp2(hOperand);
  hTmp1.m_sign=1;
  hTmp2.m_sign=1;
  return !(hTmp1>=hTmp2);
 }
 else
 {
  if(this->m_len < hOperand.m_len)
   return false;
  else if(this->m_len > hOperand.m_len)
   return true;
  else
  {
   int i;
   for(i=this->m_len;i!=0;i--)
   {
    if (this->m_num[i] > hOperand.m_num[i])
    {
     return true;
    }
    else if(this->m_num[i] < hOperand.m_num[i])
     return false;
   }
   return true;
  }
 }
}

bool HugeInt::operator > (HugeInt &hOperand)
{
 if (this->m_sign==1 && hOperand.m_sign==1)
 {
  if(this->m_len==hOperand.m_len)
  {
   for(int i=this->m_len;i!=0;i--)
    if(this->m_num[i]>hOperand.m_num[i])
     return true;
    else if(this->m_num[i]<hOperand.m_num[i])
     return false;

   return false;
  }
  else
  {
   if(this->m_len > hOperand.m_len)
    return true;
   else
    return false;
  }
 }
 else if (this->m_sign==1 && hOperand.m_sign==-1)
 {
  return true;
 }
 else if(this->m_sign==-1 && hOperand.m_sign==1)
 {
  return false;
 }
 else if (this->m_sign==-1 && hOperand.m_sign==-1)
 {
  HugeInt hTmp1(*this),hTmp2(hOperand);
  return !(hTmp1<hTmp2);
 }
 return false;
}

bool HugeInt::operator >= (const int &iOperand)
{
 HugeInt hTmp(iOperand);
 return *this >= hTmp;
}

bool HugeInt::operator > (const int &iOperand)
{
 HugeInt hTmp(iOperand);
 return *this > hTmp;
}

bool HugeInt::operator == (const int &iOperand)
{
 HugeInt hTmp(iOperand);
 return *this == hTmp;
}

void HugeInt::operator -= (HugeInt &hOperand)
{
 *this=*this - hOperand;
}

void HugeInt::operator -= (const int &iOperand)
{
 HugeInt hTmp(iOperand);
 *this=*this - hTmp;
}

main

#include <iostream>
#include <fstream>
#include <conio.h>
#include "HugeInt.h"
using namespace std;

int main()
{
 ofstream out("result.txt");
 HugeInt result=1;

 HugeInt i=-10,j=2;
 int k=1;
 
 
 cout<<"\n程序名称:HugeInt类\n作用：2000位大数的四则运算\n日期：2007年4月\n北京交通大学  "<<endl;
 cout<<endl<<"开始对HugeInt类进行测试.."<<endl<<endl;
 
 //测试100！(乘法测试)
 result=1;
 for(i=1;i<=100;i++)
  result *= i;
 cout<<"测试乘法：\n100!="<<result<<endl;

 //把100！结果写入到文件result.txt中的测试
 cout<<"测试文件流及重载<<:\n100!的结果已经写入result.txt"<<endl<<endl;
 out<<result;

 //测试除法
 for(i=100;i!=0;i--)
  result/=i;
 cout<<"测试除法：\n100!/100/99/98.../1="<<result<<endl;

 //测试-1+-2+..-100
 result=0;
 for(i=-1;i>=-100;i--)
  result+=i;
 cout<<"测试加法：\n-1 + -2 + -3 + ... + -100="<<result<<endl;
 
 //测试减法
 result=9999;
 result-=99999;
 cout<<"测试减法：\n9999 - 99999="<<result;

 cout<<"按任一键退出。";
 getch();
 return 0;
}

 

 

 

 

您可能也喜欢如下文章:

  1. HugeInt类 大数运算加法、乘法 c++实现
  2. HugeInt类-无限位长度的大数加法 c++实现
  3. 算法－写出组合数的全部可能，c++描述
  4. 图形管理容器--c++描述
  5. 迷宫问题,C++的栈实现

Leave a Reply

Your email address will not be published. Required fields are marked *