numberoperate.cpp

大数运算,效率非常高,很有收藏价值,值得你下载!

// NumberOperate.cpp: implementation of the CNumberOperate class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "NumberOperate.h"

//*********************************************************************
//本类可实现位操作(与、或、非、异或、(循环)左移位、(循环)右移位),四则运算(均不限制位数)
//考虑到系统资源问题,请不要输入过大的数
//提供三个四则运算重载函数,用于不同场合及对速度不同要求时使用
//但要求速度的同时,对输入参数的合法性要求也不同,速度最慢,合法性要求最低
//相应,速度最快的函数,对参数的合法性要求最高
//在进行数的位操作时,结果返回的为二进制(最前面的零会自动去除),进行四则运算时,结果返回的为十进制
//作者:裴泽良
//时间:20051215
//********************************************************************

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CNumberOperate::CNumberOperate()
{

}

CNumberOperate::~CNumberOperate()
{

}

CString CNumberOperate::NumberAdd(CString number1, CString number2)
{	//完成两个数number1,number2的加法运算的整理工作,结果以CString型返回,此函数不对数据在十进制内是否合法作检测
	//仅接受十进制的数number1,number2
	if(number1=="" || number2=="")
		return "";
	while(number1!="" && number1.GetAt(0)=='0')
		number1.Delete(0,1);
	while(number2!="" && number2.GetAt(0)=='0')
		number2.Delete(0,1);
	if(number1=="")
		number1="0";
	if(number2=="")
		number2="0";
	int i=number1.GetLength(),j=number2.GetLength();
	int n=max(i,j);	//m为本次两个数相加后的进位,c为相加结果
	CString s="";	//s为结果
	char*buffers=s.GetBufferSetLength(n+1);//(任何两个数相加,其结果数字的数目必<=(两数字中大者的数目+1))
	n=Add(number1.GetBuffer(i),number2.GetBuffer(j),buffers);
	if(n!=-1)	//将n位之前的位去掉
		s.Delete(0,n+1);
	return s;
}

CString CNumberOperate::NumberSub(CString number1, CString number2)
{	//完成两个数number1,number2的减法运算的整理工作,结果以CString型返回,此函数不对数据在十进制内是否合法作检测
	//仅接受十进制的数number1,number2
	if(number1=="" || number2=="")
		return "";
	while(number1!="" && number1.GetAt(0)=='0')
		number1.Delete(0,1);
	while(number2!="" && number2.GetAt(0)=='0')
		number2.Delete(0,1);
	if(number1=="")
		number1="0";
	if(number2=="")
		number2="0";
	int i=number1.GetLength(),j=number2.GetLength(),m=0,c=0;	//m为本次两个数相减后的进位,c为相减结果

	int b=0;	//表number1大于number2,为1表number1小于number2
	if(i<j)
	{	//将number1与number2互换,使得number1大于number2
		int temp=i;
		i=j,j=temp;
		CString numbertemp=number1;
		number1=number2,number2=numbertemp;
		b=1;
	}
	else if(i==j)
	{
		for(int a=0;a<i;a++)
		{
			if(number1.GetAt(a)!=number2.GetAt(a))
			{
				if(number1.GetAt(a)<number2.GetAt(a))
				{
					CString numbertemp=number1;
					number1=number2,number2=numbertemp;
					b=1;
				}
				break;
			}
		}
	}
	CString s="";
	char*buffer1=number1.GetBuffer(i),*buffer2=number2.GetBuffer(j);
	char*buffers=s.GetBufferSetLength(i);
	int n=Sub(buffer1,buffer2,buffers);
	if(n!=-1)	//将n位之前的位去掉
		s.Delete(0,n+1);
	while(s!="" && s.GetAt(0)=='0')
		s.Delete(0,1);
	if(b==1)
		s="-"+s;
	if(s=="")
		s="0";
	return s;
}

CString CNumberOperate::NumberMulti(CString number1, CString number2)
{	//对number1,number2两个数进行相乘,结果以CString型返回(当两操作数达万位以上时,效率便不很理想)
	//此函数不对数据在十进制内是否合法作检测,且仅接受十进制的数number1,number2
	if(number1=="" || number2=="")
		return "";
	while(number1!="" && number1.GetAt(0)=='0')
		number1.Delete(0,1);
	while(number2!="" && number2.GetAt(0)=='0')
		number2.Delete(0,1);
	if(number1=="" || number2=="")
		return "0";
	CString s;
	int i=number1.GetLength(),j=number2.GetLength();
	char*buffers=s.GetBufferSetLength(i+j);	//存放结果(任何两个数相乘,其结果数字的数目必<=两相乘数数字数目之和)
	int n=Multi(number1.GetBuffer(i),number2.GetBuffer(j),buffers);
	if(n>1)	//将n位之前的位去掉
		s.Delete(0,n-1);
	while(s!="" && s.GetAt(0)=='0')
		s.Delete(0,1);	//去掉最前面的零
	return s;
}

BOOL CNumberOperate::NumberDiv(CString number1, CString number2, CString &resultint,CString &resultelse)
{	//结果形式为整数部分(resultint)+余数部分(resultelse),如果错误,返回FALSE,正常(但不一定正确,例:输入abcd)时返回TRUE
	//此函数不对数据在十进制内是否合法作检测,且仅接受十进制的数number1,number2
	resultint="";
	resultelse="";
	while(number1!="" && number1.GetAt(0)=='0')
		number1.Delete(0,1);	//被除数去前零
	while(number2!="" && number2.GetAt(0)=='0')
		number2.Delete(0,1);	//除数去前零
	if(number2=="")
		return FALSE;	//除数为零,错误
	if(number1=="")
	{	//被除数为零,直接返回零
		resultint="0";
		return TRUE;
	}
	int i=number1.GetLength(),j=number2.GetLength();
	char*buffer1=number1.GetBuffer(i),*buffer2=number2.GetBuffer(j);

	if(i<j)
	{	//结果无整数部分,仅小数
		resultint="0";
		resultelse=number1;
		return TRUE;
	}
	else if(i==j)
	{
		for(int a=0;a<i;a++)
		{
			if(buffer1[a]!=buffer2[a])
			{
				if(buffer1[a]<buffer2[a])
				{	//结果无整数部分,仅小数
					resultint="0";
					resultelse=number1;
					return TRUE;
				}
				break;
			}
		}
	}
	int intcount=0;
	char*buffers=resultint.GetBufferSetLength(i-j+1);	//结果数据(任何两个数相除,其结果数字的长度必<=(被除数及除数长度之差+1))
	resultelse=Div(buffer1,buffer2,buffers,intcount);
	resultint.Delete(intcount,i-j+1-intcount);
	while(resultint!="" && resultint.GetAt(0)=='0')
		resultint.Delete(0,1);
	while(resultelse!="" && resultelse.GetAt(0)=='0')
		resultelse.Delete(0,1);
	return TRUE;
}

int CNumberOperate::Add(char*buffer1, char*buffer2, char*buffers)
{	//对buffer1与buffer2中的数进行相加,结果放入buffers中,buffers的长度至少为max(buffer1,buffer2)+1
	//此函数不对数据或缓冲区空间是否足够作任何检测,旨在提高效率,速度
	int length1=strlen(buffer1),length2=strlen(buffer2);
	int m=0,c=0,n=max(length1,length2);	//m为本次两个数相加后的进位,c为相加结果
	while(length1>0 || length2>0)
	{
		if(length1==0)	//第一个数已取完
		{
			c=buffer2[length2-1]-0x30+m;
			length2--;
		}
		else
		{
			if(length2==0)	//第二个数已取完
			{
				c=buffer1[length1-1]-0x30+m;
				length1--;
			}
			else	//两个数均未取完
			{
				c=buffer1[length1-1]+buffer2[length2-1]-0x30-0x30+m;
				length1--,length2--;
			}
		}
		buffers[n]=c%10+0x30;
		n--;
		m=c/10;
	}
	if(m==1)
	{	//最后一次,最前一位相加,有进位
		buffers[n]='1';
		n--;
	}
	return n;
}

int CNumberOperate::Sub(char *buffer1, char *buffer2, char *buffers)
{	//对数buffer1与buffer2进行相减,但buffer1必须大于buffer2,且buffers的长度至少为buffer1-1;
	//此函数不对数据或缓冲区空间是否足够作任何检测,旨在提高效率,速度
	int i=strlen(buffer1),j=strlen(buffer2),m=0,c=0;	//m为本次两个数相减后的进位,c为相减结果
	int n=i-1;	//指示结果数据当前的位置
	while(i>0 || j>0)
	{
		if(j==0)	//第二个数已取完
		{
			c=buffer1[i-1]-0x30+m;
			i--;
		}
		else	//两个数均未取完
		{
			c=buffer1[i-1]-buffer2[j-1]+m;
			i--,j--;
		}
		if(c<0)
		{
			c+=10;
			m=-1;
		}
		else
			m=0;
		buffers[n]=c%10+0x30;
		n--;
	}
	return n;
}

int CNumberOperate::Multi(char*buffer1, char*buffer2, char*buffers)
{	//将buffer1,buffer2处的数据相乘,结果放在buffers中但从后至前,返回buffers最前面还有多少未用
	//buffers必须有buffer1+buffer2的长度再加1的空间
	//此函数不对数据或缓冲区空间是否足够作任何检测,旨在提高效率,速度
	int i=strlen(buffer1),j=strlen(buffer2),ii=i,m=0,n=i+j,nn=n+1,c=0,b=0;	//m为相乘时的进位,n为s的位置,nn为n的备份
	FillMemory(buffers,n,'0');		//初始化空间
	for(;j>0;j--,i=ii,m=0)
	{
		n=--nn;
		b=buffer2[j-1]-0x30;
		if(b==0)		//如果b的数等于零,则此趟不必计算
			continue;
		for(;i>0;i--,n--)
		{
			c=(buffer1[i-1]-0x30)*b+m;
			m=c/10+(c%10+buffers[n-1]-0x30)/10;	//求得本次的进位(为本次相乘的进位加上末位与已有结果相加的进位)
			buffers[n-1]=(c%10+buffers[n-1]-0x30)%10+0x30;	//保存结果
		}
		if(m!=0)	//如果进位不为零,则加入进位
			buffers[n-1]=m+0x30;
	}
	return n;
}

char* CNumberOperate::Div(char *buffer1, char *buffer2, char *bufferint, int &intcount)
{	//做buffer1除以buffer2操作(buffer1大于buffer2),结果整数放在bufferint中,返回余数,bufferint的长度至少为buffer1-buffer2+1
	//此函数不对数据合法性或数据或缓冲区空间是否足够作任何检测,旨在提高效率,速度
	intcount=0;		//intcount为整数部分的数量
	int i=strlen(buffer1),j=strlen(buffer2),a[2],b[4],temp[3];//a[0]:buffer1下一数据的位置,b[0]:除数的特征数据,b[1]:特征数据长度
	if(i<j)							//b[2]:指向上次运算数中参加运算时最后一位,即与被除数应该对齐时的位置
		return buffer1;				//b[3]:总是指向当前运算数中参加运算最后一位
	char*bufferss=NULL,*buffersconfirm=NULL,*buffertemp=NULL,*bufferb;

	b[1]=(j>4?4:j);	//提取除数的特征数据(前四位)
	bufferb=new char[b[1]+1];	//bufferb:除数的特征数据(<=4位)字符串形式
	bufferb[b[1]]='\0';
	CopyMemory(bufferb,buffer2,b[1]);
	b[0]=atoi(bufferb);	//除数的特征数据(<=4位) 数形式
	delete bufferb;

	bufferss=new char[j+2];	//从被除数中提取的将要处理的数据
	bufferss[j+1]='\0';
	buffersconfirm=new char[j+2];	//从被除数中提取的数据与m[0]相乘后的数据
	buffersconfirm[j+1]='\0';
	buffertemp=new char[b[1]+2];	//从被除数中提取的数据
	buffertemp[b[1]+1]='\0';
	char m[2];
	m[1]='\0';		//被除数除以除数一次所得的结果
	a[0]=0,a[1]=j;//a[1]:下次应从被除数中从a[0]所取数据的数目
	b[2]=a[1]-1,b[3]=a[1]-1;

	FillMemory(bufferss,j+1,'0');
	FillMemory(buffersconfirm,j+1,'0');
	FillMemory(buffertemp,b[1]+1,'0');

	while((a[0]+a[1])<=i)
	{
		for(;(a[0]+a[1])<=i;)
		{
			temp[1]=b[3]-b[2];
			if(temp[1]>0)
			{	//两对齐指针不在同一位置,对结果进行补零
				FillMemory(bufferint,temp[1],'0');
				bufferint+=temp[1];
				intcount+=temp[1];
				b[2]=b[3];
			}
			bufferss[0]='0';
			bufferss[j]='\0';
			CopyMemory(bufferss,buffer1+a[0],a[1]);
			temp[0]=NumberCompare(bufferss,buffer2);
			if(temp[0]>0)
			{	//从被除数中提取的数据大于除数,此时应求得大多少倍,即结果
				//本程序采用取两个数的前四位(可提高一次命中率),相除,取此数为结果,多位数时再验证一次
				buffertemp[0]='0';
				buffertemp[b[1]]='\0';
				CopyMemory(buffertemp,bufferss,b[1]+a[1]-j);	//从被除数提取数据放入buffertemp处
				m[0]=atoi(buffertemp)/b[0]+0x30;		//求出一次相除结果,此次有可能不正确,所以需下一次再验证
				buffersconfirm[0]='0';
				buffersconfirm[j]='\0';
				Multi(buffer2,m,buffersconfirm);
				if(j>4)
				{	//在多位数时,有必要再验证一次(最多一次)
					temp[0]=NumberCompare(bufferss,buffersconfirm);
					if(temp[0]<0)
					{
						m[0]--;		//m[0]大了,至多减1后,m[0]值肯定成立(可由数学方法证出)
						Multi(buffer2,m,buffersconfirm);	//重新计算buffersconfirm值
					}
				}
				*bufferint++=m[0];
				intcount++;
				temp[1]=0,temp[2]=0;
				while(bufferss[temp[1]]=='0')
					temp[1]++;	//把bufferss最前面的0去掉(若有,则最可能为一位)
				while(buffersconfirm[temp[2]]=='0')
					temp[2]++;	//把buffersconfirm最前面的0去掉(若有,则最可能为一位)
				Sub(bufferss+temp[1],buffersconfirm+temp[2],buffer1+a[0]+temp[1]);	//将减得的结果回加到被除数中
				while(buffer1[a[0]]=='0' && a[0]<=i)
					a[0]++;		//若最前一位为零,表明已约去,则去除掉
				a[1]=j;
				b[2]++,b[3]=a[0]+a[1]-1;	//两对齐指针做相应变化	
				break;
			}
			else if(temp[0]<0)	//当被除数小于除数时,被除数多加一位,即可
			{
				if(a[1]==j)
					a[1]=j+1;
				else
					a[0]++;	//若多加一位还除不掉(表明a[0]位为零),则舍弃a[0]位,再取j+1位
				b[3]=a[0]+a[1]-1;
			}
			else
			{	//当被除数等于除数时
				*bufferint++='1';
				intcount++;
				FillMemory(buffer1+a[0],a[1],'0');	//被除数相应位置零
				a[0]+=a[1],a[1]=j;
				b[2]++,b[3]=a[0]+a[1]-1;
				break;
			}
		}
	}
	temp[1]=b[3]-b[2];
	if(temp[1]>0 && b[3]<=i)
	{	//两对齐指针不在同一位置且b[3]指针合法,对结果进行补零
		FillMemory(bufferint,temp[1],'0');
		bufferint+=temp[1];
		intcount+=temp[1];
		b[2]+=temp[1];
	}
	bufferss[j]='0';
	buffertemp[b[1]]='0';
	buffersconfirm[j]='0';
	delete bufferss;
	delete buffersconfirm;
	delete buffertemp;
	return buffer1+a[0];
}

int CNumberOperate::NumberCompare(CString number1, CString number2)
{	//比较两数大小,number1大于number2返回1,相等返回0,小于返回-1
	int length1=number1.GetLength(),length2=number2.GetLength();
	char*buffer1=number1.GetBuffer(length1),*buffer2=number2.GetBuffer(length2);
	return NumberCompare(buffer1,buffer2);
}

int CNumberOperate::NumberCompare(char*buffer1, char*buffer2)
{	//比较两数大小,number1大于number2返回1,相等返回0,小于返回-1
	while(buffer1[0]=='0')
		buffer1++;	//若buffer1开始处为零,buffer1指针右移
	while(buffer2[0]=='0')
		buffer2++;
	int i=strlen(buffer1),j=strlen(buffer2);//,m=0,n=0;
	if(i>j)
		return 1;
	else if(i<j)
		return -1;
	else if(i==j)
	{
		for(int a=0;a<i;a++)
		{
			if(buffer1[a]!=buffer2[a])
			{
				if(buffer1[a]<buffer2[a])
					return -1;
				else
					return 1;
				break;
			}
		}
	}
	return 0;
}