www.pudn.com > BigNumberCalculater.rar > 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(i1) //将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(i0 || 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(i4?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