64位大整数四则运算(+-除).cpp

大整数四则运算的例子和算法介绍

//64位大整数四则运算(+,-,/)
#include<iostream>
#include<string>

using namespace std;

//判断一个字符串所表示的数是否为0；用于判断除数是否为0；
bool String_Zero(string s);			
//两个字符串所代表大整数的比较，返回值为字符'>','<','='
char compare(string s1,string s2);		

class CLint		
{
	//unsigned short 2字节/16位；num[4]用于存放64位大整数
	unsigned short Num_Lint[4];		
	//以字符串形式存放大整数中(10进制)
	string String_Algorithm;		
public:
	//B是自A中去掉开头为零的元素，B_len为B的长度
	void Arr_qu0(unsigned short A[4],unsigned short B[4],int A_Len,int &len);
	//数组A与B相比较，大于等于为false，小于为true；
	bool A_Less_B(unsigned short A[4],unsigned short B[4],int A_Len,int B_Len);
	
	//10000进制数组变换为字符串
	string Arr10ToStr(unsigned arr[6]);	
	//字符串-->65536进制的无符号短整型数组
	void StrToL65536(string Str,unsigned short num[4]);	
	//65536进制的无符号短整型数组-->字符串
	string L65536ToStr(unsigned short Num[4]);

	CLint(){};	//构造函数重载
	CLint(string S);

	~CLint(){};

	CLint operator +(CLint L2);
	CLint operator -(CLint L2);
//	CLint operator *(CLint L2);
	CLint operator /(CLint L2);
//	CLint operator %(CLint L2);

	void Out_Algo();//输出结果

};

//判断一个字符串所表示的数是否为0；用于判断除数是否为0；
bool String_Zero(string s)			
{
	bool Is_0=true;

	//判断每个元素是否为0
	//循环停止条件：字符串结束或存在非零值
	for (int i=0;(s[i]&&Is_0);i++)		
	{
		if (s[i]!='0') Is_0=false;      
	}

	return Is_0;
}

//两个字符串所代表大整数的比较，返回值为字符'>','<','='
char compare(string s1,string s2)		
{
	char comp;
	if (s1.length()<s2.length())  
		comp='<';	//位数小的数<位数大的数
	else 
		if (s1.length()==s2.length()) //位数相等
			{
				if (s1<s2) comp='<';
				else 
					if (s1>s2) comp='>'	;
					else comp='=';		
			}

		else  comp='>';	//s1>s2
	return comp;
}

//B是自A中去掉开头为零的元素，B_len为B的长度
void CLint::Arr_qu0(unsigned short A[4],unsigned short B[4],int A_Len,int &B_Len)  
{
	int	i=0;	
	B_Len=0;
	//寻找不为0的元素
	while ((i<4)&&(A[i]==0)) i++;
    
	//拷贝A中从非零元素以后的所有元素
	for (;i<A_Len;i++)					
	{	B[B_Len]=A[i];
		B_Len++;	
	}

	//数组B中B[len-1]...B[4]元素赋值为0
    for (i=B_Len;i<4;i++)
	{B[i]=0;} 
}


//数组A与B相比较，大于等于为false，小于为true；
bool CLint::A_Less_B(unsigned short A[4],unsigned short B[4],int A_Len,int B_Len)
{
	bool b,OK;
	int i=0;
			
	if (A_Len<B_Len) b=true;
	else if (A_Len>B_Len) b=false;
		else
		{	OK=false;
			while ((!OK)&&(i<A_Len)) //元素相等时循环判断
			{
				if (A[i]>B[i]) {b=false;OK=true;}
				if (A[i]<B[i]) {b=true;OK=true;}
				i++;
			}			
			if (OK==false) b=false;
		}
	return b;
}


 //10000进制数组变换为字符串
string CLint::Arr10ToStr(unsigned arr[6]) 
{
	string s1,s2;
	unsigned Quotient,residue;
	//寻找不为零的arr[i]
	for(int i=0;!arr[i]&&i>=0;i++);

	if(i>5) return string("0");

	//从arr[5]到不为零的arr[i]，转换每个元素为字符
	for (int j=5;j>=i;j--)    
	{		
		Quotient=arr[j];		//取数组一元素

		for(int k=0;k<4;k++)
		{
			residue=Quotient%10;	//取数组元素的末位数字
			Quotient=Quotient/10;	//在数组元素中去掉末位数字所剩下的数字
			s2=(residue+48);		//末位数字转换为字符
			s1=s2+s1;				//存入字符串s1，注意是s2+s1
		}
	}
	return s1;
}

//字符串-->65536进制的无符号短整型数组
void CLint::StrToL65536(string Str,unsigned short Num[4]) 
{
	int i,j;
	unsigned l;	//unsigned int 4字节/32位

	//数组Num初始化为0
	for(i=0;i<4;i++) Num[i]=0;	
	
	//10进制转换为65536(=2^16)进制
	for(i=0;Str[i];i++)			
	{	
		//从低位到高位分别乘10并进位
		for(j=3,l=0;j>=0;j--)	
		{
			//l>>16相当于l整除65536取得的商
			l=Num[j]*10+(l>>16);
			//数组Num每一位=其本身乘以10并加上其低一位的进位值
			Num[j]=l;
		}

		//字符0的ASCII码值为48,s[i]-48实现字符到数字的转换
		for(j=3,l=(Str[i]-48)<<16;j>=0;j--)
		{
			//数组最低位加上s[i]-48，依次判断是否需要进位。
			l=Num[j]+(l>>16);	
			Num[j]=l;
		}
	}   
}

//65536进制的无符号短整型数组-->字符串
string CLint::L65536ToStr(unsigned short Num[4])
{
	unsigned short t[4];//unsigned short   2字节
	short i,j;			//short int 2字节
	//unsigned int 4字节，数组r的每一位存放10进制数的4位
	unsigned r[6];		
	string s;

	//数组num赋值给临时数组t
	for(j=0;j<4;j++) t[j]=Num[j];  

	for(i=5;i>=0;i--)		//
		for(j=0,r[i]=0;j<4;j++)  //求r[i]
		{
			r[i]=(r[i]<<16)+t[j];   //<<相当于*65536
			t[j]=r[i]/10000;
			r[i]=r[i]%10000;
		}

	s=Arr10ToStr(r);
	return s;
}

//构造函数重载
CLint::CLint(string S)   
{
	String_Algorithm=S;
	StrToL65536(S,Num_Lint);   
}

//加法运算
CLint CLint::operator +(CLint L2)
{	
	int j;
	string ss;
	unsigned l;
	unsigned short Num_L[4];

	//从最低位开始加; j不能为unsigned,因为unsigned永远大于0
	for(j=3,l=0;j>=0;j--)  
	{
		//各位相加并加上低一位的进位。l存放进位的数
		l=Num_Lint[j]+L2.Num_Lint[j]+(l>>16);
		//unsigned赋值给unsigned short，仅传送低16位。相当于num[j]=l%65536
		Num_L[j]=l;			
	}

	//转换65536进制的数为字符串
	ss=L65536ToStr(Num_L);
	//以字符串构造一个临时对象
	return CLint(ss);		
}

//减法运算
CLint CLint::operator -(CLint L2)  
{
	int j,j_ls;
	string ss;
	int l;	//不能为unsigned，因为两数相减之后可能为负值。
	unsigned short Num_L[4];

	//从最低位开始; 这里j不能为unsigned,因为unsigned永远大于0
	for(j=3,l=0;j>=0;j--)	
	{
		l=Num_Lint[j]-L2.Num_Lint[j];//各位相减	
        if (l<0) //借位
			{
				l+=65536;
				//循环借位：当出现连续几位都需要借位时
				j_ls=j;  //j_ls临时代替j，用作循环变量，若用j则改变了j，会产生错误
				while ((j_ls>=1)&&(Num_Lint[j_ls-1]==0)) 
				{
					//从上一位借1，Num_Lint[j_ls-1]＝65536，然后Num_Lint[j_ls]借1
					Num_Lint[j_ls-1]+=65535;  
					j_ls--;
				}
				Num_Lint[j_ls-1]--;

			}
		//unsigned赋值给unsigned short，仅传送低16位。
		Num_L[j]=l;	
	}

	//转换65536进制的数为字符串
	ss=L65536ToStr(Num_L); 
	//以字符串构造一个临时对象
	return CLint(ss);

}

//整除运算
CLint	CLint::operator /(CLint L2)
{
	unsigned short Op1[4];
	unsigned short Op2[4];
	unsigned short Quotient[4];//商

	//数组Op1的一部分，用于存储除法中的被减数
	unsigned short PartOfOp1[4];	
	unsigned short Ls[4];

	//商的位置
	int Posi_Quo=0;

	int Op1_Len,Op2_Len,PartOfOp1_Len,Ls_Len,i,j,k,m,i_ls;
	bool Op1_Less_Op2=true;

	string Quotient_Str;

	for (i=0;i<4;i++)
	{
		Quotient[i]=0;
	}

	//1.数组去掉开头的零元素，确定有效长度；得到数组Op1、Op2；

	//Op1[4]为L1.Num_Lint去掉零元素后的数组，Op1_Len为其长度。
	Arr_qu0(Num_Lint,Op1,4,Op1_Len);
	Arr_qu0(L2.Num_Lint, Op2,4,Op2_Len);
	
	//2.确定商的初始位置： 数组Num_Lint的第一个非零元素位置+数组Op2的有效长度-1；
	while ((Posi_Quo<4)&&(Num_Lint[Posi_Quo]==0)) Posi_Quo++;	//寻找不为0的元素
	Posi_Quo+=Op2_Len-1;			

	//3.循环求商

	//k为Op1中与Op2相减的最末一个元素的下标；
	k=Op2_Len-1;
	
	//PartOfOp1[4]初始化为：非零元素为Op1的前Op2_Len个元素。在相除时用作与Op2相减的数组；
	PartOfOp1_Len=Op2_Len;
	for (i=0;i<Op2_Len;i++)			
	{
		PartOfOp1[i]=Op1[i];
	}
	for (i=Op2_Len;i<4;i++)
	{
		PartOfOp1[i]=0;
	}

	Op1_Less_Op2=A_Less_B(PartOfOp1,Op2,PartOfOp1_Len,Op2_Len);   //PartOfOp1与Op2相比较
   
	//除法运算。被除数：Op1，除数：Op2，商为Quotient。其中PartOfOp1用作与Op2相减的数组
	while (!((k==(Op1_Len-1))&&Op1_Less_Op2))
	{
		//If PartOfOp1<Op2，则PartOfOp1再加一位；(通过k+1来实现)
		if (Op1_Less_Op2)				
		{
			k++;
			Posi_Quo++;
			PartOfOp1_Len++;
			PartOfOp1[PartOfOp1_Len-1]=Op1[k];
		}
		
		//2.1循环相减，直到PartOfOp1<Op2，每减1次Quotient[Posi_Quo]加1

		//PartOfOp1与Op2相比较
		Op1_Less_Op2=A_Less_B(PartOfOp1,Op2,PartOfOp1_Len,Op2_Len);   

		while (!Op1_Less_Op2)  //被减数大于减数时循环相减
		{
			//两数从末位开始相减
			for(i=(PartOfOp1_Len-1),j=Op2_Len-1;i>=0;i--,j--)
			{
				//大于等于则相减，j>=0表示减法未进行完
				if ((j>=0)&&(PartOfOp1[i]>=Op2[j])) 
					PartOfOp1[i]=PartOfOp1[i]-Op2[j];   
				else 
					//小于则从前一位借位
					if ((j>=0)&&(PartOfOp1[i]<Op2[j]))
						{
							PartOfOp1[i]=65536+PartOfOp1[i]-Op2[j];
							//循环借位：当出现连续几位都需要借位时
							i_ls=i;   //i_ls临时代替i用作循环变量，若用i则会出现错误
							while ((i_ls>=1)&&(PartOfOp1[i_ls-1]==0)) 
							{
								//从上一位借1，PartOfOp1[i_ls-1]＝65536，然后PartOfOp1[i_ls]借1
								PartOfOp1[i_ls-1]+=65535;  
								i_ls--;
							}							
							PartOfOp1[i_ls-1]--;//退位情况处理
						}
			}			

			Quotient[Posi_Quo]+=1;		//商加1
			for (m=Posi_Quo;m>0;m--)	//判断是否需要进位
				{
				if (Quotient[m]>65535) 
						{
							Quotient[m]-=65535;
							Quotient[m-1]+=1;
						}
				}

			//对PartOfOp1去零处理，避免出现如下情况：
			//长度比Op2大，但数组元素为0，比较结果却是PartOfOp1大于Op2
			if (PartOfOp1[0]==0)
			{
				Arr_qu0(PartOfOp1,Ls,PartOfOp1_Len,Ls_Len); 
				//临时数组赋值给PartOfOp1
				for (m=3;m>=0;m--) {PartOfOp1[m]=Ls[m];}	
				PartOfOp1_Len=Ls_Len;
			}
			//PartOfOp1与Op2相比较
			Op1_Less_Op2=A_Less_B(PartOfOp1,Op2,PartOfOp1_Len,Op2_Len);   
		}

	//重新设定PartOfOp1[4]
	//从被除数Op1中取元素；
	//循环停止条件：被减数组PartOfOp1的长度等于减数组Op2的长度或被除数Op1最低位已处理过
	while ((PartOfOp1_Len<Op2_Len)&&(k<(Op1_Len-1)))     
	{
		k++;		//被除数Op1再向低位移一位
		Posi_Quo++;	//商的位置也向低位移一位
		PartOfOp1[PartOfOp1_Len]=Op1[k];	
		PartOfOp1_Len++;
	}
	//Op1的前k个元素组成的数组与Op2相比较
	Op1_Less_Op2=A_Less_B(PartOfOp1,Op2,PartOfOp1_Len,Op2_Len);   

	}
	//输出商
	Quotient_Str=L65536ToStr(Quotient);   
	return CLint(Quotient_Str);
}

//结果输出
void CLint::Out_Algo()
{
	int pos=0;
	string String_Algo_No0;
	
	while (String_Algorithm[pos]=='0') 
	{
		pos++;   //移到被找到元素的下一个位置		
	}
	
	String_Algo_No0=String_Algorithm.substr(pos);
	cout<<String_Algo_No0<<endl;
}

//主函数
void main()
{
	string s1,s2;		//用于输入两个64bit大整数
	bool zero;			//判断除数为0
	char Str_Comp;		//用于存放字符串比较结果：>，<，=
	string stad("18446744073709551615");


	cout<<"The result need to be less than 18446/74407/37095/51615"<<endl;
	cout<<"Input the first number:    ";
	cin>>s1;			//输入第一个大整数
	Str_Comp=compare(s1,stad);
	while ((Str_Comp=='>')||(Str_Comp=='='))
	{
		cout<<"数据溢出,请重输：  ";
		cin>>s1;
		Str_Comp=compare(s1,stad);
	}

	cout<<"Input the second number:   ";
	cin>>s2;			//输入第二个大整数
	Str_Comp=compare(s2,stad);
	while ((Str_Comp=='>')||(Str_Comp=='='))
	{
		cout<<"数据溢出,请重输：  ";
		cin>>s2;
		Str_Comp=compare(s2,stad);
	}

	CLint CL1(s1);		//用s1初始化对象CL1
	CLint CL2(s2);
	CLint Result_CL;	//用于存放运算结果
	
	//加
	Result_CL=CL1+CL2;
	cout<<s1<<"+"<<s2<<"=";
	Result_CL.Out_Algo();    //输出结果

	Str_Comp=compare(s1,s2); //比较s1,s2

	//减
	if(Str_Comp=='>')
		{	
			Result_CL=CL1-CL2; 
			cout<<s1<<"-"<<s2<<"=";
			Result_CL.Out_Algo();
		}  
	else if(Str_Comp=='<') 
			{
				Result_CL=CL2-CL1;
				cout<<s1<<"-"<<s2<<"="<<"-";
				Result_CL.Out_Algo();
			}
	else {cout<<s1<<"-"<<s2<<"="<<"0"<<endl;}

	//除：CL11/CL22
	
	//用s1初始化对象CL11；重新初始化是因为减法中可能改变操作数
	CLint CL11(s1);			
	CLint CL22(s2);

	zero=String_Zero(s2);
	if (zero)
		//除数为0
		cout<<"Wrong! The right operand is zero."<<endl;		
	else
		//s1<s2,则s1/s2=s1
		if (Str_Comp=='<') cout<<s1<<"/"<<s2<<"="<<"0"<<endl;	
		else 
			//s1==s2，则s1/s2=1
			if (Str_Comp=='=') cout<<s1<<"/"<<s2<<"="<<"1"<<endl;	
			else
			{
				Result_CL=CL11/CL22;
				cout<<s1<<"/"<<s2<<"=";
				Result_CL.Out_Algo();//输出结果			
			}
}