📄 bint.cpp
字号:
/****************************************************************/
//大数运算库源文件：Bint.cpp
//作者：afanty@vip.sina.com
//版本：1.0 (2003.4.26)
//说明：适用于MFC
/****************************************************************/
#include "Bint.h"
//初始化类成员变量
void CBint::InitData()
{ m_Sign=1;
m_Length=1;
m_InSystem=AUTO_SYSTEM;
m_OutSystem=DEC_SYSTEM;
ZeroMemory(m_Value,BI_MAXLEN*sizeof(unsigned long));
}
//初始化大数为0
CBint::CBint()
{
InitData();
}
CBint::CBint(const /*unsigned*/ __int64 Value)
{
InitData();
SetValue(Value);
}
//重载的构造函数,初始化字符串
CBint::CBint(LPCSTR Value)
{
InitData();
SetValue(CString(Value));
}
//重载的构造函数,初始化字符串类
CBint::CBint(const CString& Value)
{
InitData();
SetValue(Value);
}
//重载的构造函数,初始化CBint类
CBint::CBint(const CBint& Value)
{
InitData();
SetValue((CBint&)Value);
}
//采用缺省的解构函数
CBint::~CBint()
{
}
//大数比较
//调用形式 N.Compare(B) 返回N>B 如果大数N位数比大数B多，当然N>B
//如果位数相同，则从高位开始比较，直到分出大小
// N > B 返回 1
// N == B 返回 0
// N < B 返回 -1
int CBint::Compare(const CBint& B) const
{ if(m_Sign!=B.m_Sign)
{ if(m_Sign)
return 1;
else
return -1;
}
if(m_Length>B.m_Length) // 1
return (m_Sign==1?1:-1);
if(m_Length<B.m_Length) // -1
return (m_Sign==1?-1:1);
for(int i=m_Length-1;i>=0;i--)
{
if(m_Value[i]>B.m_Value[i])
return (m_Sign==1?1:-1);
if(m_Value[i]<B.m_Value[i])
return (m_Sign==1?-1:1);
}
return 0;
}
int CBint::Compare(long B) const
{ int Sign=B>=0?1:0;
if(m_Sign!=Sign)
{ if(m_Sign)
return 1;
else
return -1;
}
if(m_Length>1)
return (m_Sign==1?1:-1);
if(m_Value[0]>(unsigned long)B)
return (m_Sign==1?1:-1);
if(m_Value[0]<(unsigned long)B)
return (m_Sign==1?-1:1);
return 0;
}
int CBint::CompareAbs(const CBint& B) const
{
if(m_Length>B.m_Length) // 1
return 1;
if(m_Length<B.m_Length) // -1
return -1;
for(int i=m_Length-1;i>=0;i--)
{
if(m_Value[i]>B.m_Value[i])
return 1;
if(m_Value[i]<B.m_Value[i])
return -1;
}
return 0;
}
int CBint::CompareAbs(unsigned long B) const
{ if(m_Length>1)
return 1;
if(m_Value[0]>B)
return 1;
if(m_Value[0]<B)
return -1;
return 0;
}
//照搬参数的各属性
CBint& CBint::SetValue(const CBint& Src)
{ m_Length=Src.m_Length;
m_Sign=Src.m_Sign;
m_InSystem=((CBint &)Src).InSystem();
m_OutSystem=((CBint&)Src).OutSystem();
CopyMemory(m_Value,Src.m_Value,BI_MAXLEN*sizeof(unsigned long));
return *this;
}
CBint& CBint::SetValue(const /*unsigned*/ __int64 intSrc)
{ __int64 tmp=intSrc;
if(tmp<0) tmp=-tmp;
ZeroMemory(m_Value,BI_MAXLEN*sizeof(unsigned long));
//m_Sign=1;
m_Sign=(intSrc<0?0:1);
m_Length=1;
m_Value[0]=(unsigned long)tmp;
if(intSrc>0xffffffff)
{ m_Length=2;
m_Value[1]=(unsigned long)(intSrc>>32);
}
return *this;
}
CBint& CBint::SetValue(const CString& szSrc)
{ int system=m_InSystem,len=szSrc.GetLength();
register int Index=0,k=0;
SetValue(0);
if(len>0)
{
if(system==AUTO_SYSTEM)
{ system=DEC_SYSTEM;
CString x(szSrc.Left(2));
x.MakeLower();
if(x =="0x" || x=="&h")
{
system=HEX_SYSTEM;
Index=2;
}
else if(x=="&o")
{
system=OCT_SYSTEM;
Index=2;
}
else if(x=="&b")
{
system=BIN_SYSTEM;
Index=2;
}
else if(x=="&o")
{
system=OCT_SYSTEM;
Index=2;
}
else
{ for(k=0;k<len;k++)
{
if((szSrc[k]>='A' && szSrc[k]<='F') || (szSrc[k]>='a' && szSrc[k]<='f'))
{ system=HEX_SYSTEM;
break;
}
}
}
switch(szSrc[len-1]) //通过后缀确定输入字符的进制
{ case 'o': //8进制输入
case 'O':
system=OCT_SYSTEM;
break;
case 'h': //16进制输入
case 'H':
system=HEX_SYSTEM;
break;
}
}
if(len>0 && szSrc[0]=='-')
{ Index=1;
m_Sign=0;
}
for(; Index<len; Index++)
{ k=szSrc[Index];
switch(system)
{ case BIN_SYSTEM:
if(k!='0' && k!='1')
continue;
k-='0';
break;
case OCT_SYSTEM:
if(k<'0' || k>'7')
continue;
k-='0';
break;
case DEC_SYSTEM:
if(k<'0' || k>'9')
continue;
k-='0';
break;
case HEX_SYSTEM:
if(k>='0' && k<='9')
k-='0';
else if(k>='A' && k<='F')
k-='A'-10;
else if(k>='a' && k<='f')
k-='a'-10;
else
continue;
break;
default:
continue;
}
//SetValue(Mul(system));
//SetValue(Add(k));
*this=Mul(system).Add(k);
}
}
if(m_Length==1 && m_Value[0]==0)
m_Sign=1;
return *this;
}
//重载=操作符
CBint& CBint::operator = (const /*unsigned*/ __int64 intSrc)
{
return SetValue(intSrc);
}
CBint& CBint::operator =(const CString& szSrc)
{
return SetValue(szSrc);
}
CBint& CBint::operator = (LPCSTR lpSrc)
{
return SetValue(CString(lpSrc));
}
CBint::operator CString() const
{ CString str("");
char ch,Mask[]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
CBint X(*this);
while(X.m_Value[X.m_Length-1]>0)
{ ch=Mask[X.ModAbs(m_OutSystem)];
str.Insert(0,ch);
X.SetValue(X.Div(m_OutSystem));
}
if(!m_Sign)
{
str.Insert (0,"-");
}
if(str.GetLength()==0)
str.Insert(0,"0");
return str;
}
unsigned long CBint::operator[](int nIndex) const
{ if(nIndex<0 || nIndex>m_Length-1) nIndex=0;
return m_Value[m_Length-nIndex-1];
}
//大数相加
//调用形式: N.Add(B) 返回 N+B
// 若两大数符号相等,其值相加,否则,改变被加数符号,再调用N-B,即 N+(-B)
/******************************************************************/
/*
例如：
A B C
+ D E
--------------
= S F G H
其中，若C+E<=0xffffffff，则H=C+E，carry(进位标志)=0
若C+E>0xffffffff，则H=C+E-0x100000000，carry=1
若B+D+carry<=0xfffffff，则G=B+D，carry=0
若B+D+carry>0xfffffff，则G=B+D+carry-0x10000000，carry=1
若carry=0，则F=A，S=0
若carry=1，A<0xfffffff，则F=A+1，S=0
若carry=1，A=0xfffffff，则F=0，S=1
/*****************************************************************/
CBint CBint::Add(const CBint& B) const
{ CBint N(B);
register unsigned int carry=0;
unsigned __int64 sum=0;
if(m_Sign==N.m_Sign)
{ if(N.m_Length<m_Length)
N.m_Length=m_Length;
for(register int i=0;i<N.m_Length;i++)
{
sum=(unsigned __int64)N.m_Value[i]+m_Value[i]+carry;
N.m_Value[i]=(unsigned long)sum;
carry=sum>0xFFFFFFFF?1:0;
}
if(N.m_Length<BI_MAXLEN)
{ N.m_Value[N.m_Length]=carry;
N.m_Length+=carry;
}
}
else
{ N.m_Sign=m_Sign;
//return ((CBint*)this)->Sub(N);
int cmp=CompareAbs(B);
if(cmp)
{ int len;
unsigned long *Small,*Bigger;
if(cmp>0)
{
Bigger=(unsigned long*)m_Value;
Small=(unsigned long*)B.m_Value;
len=m_Length;
}
if(cmp<0)
{
Bigger=(unsigned long*)B.m_Value;
Small=(unsigned long*)m_Value;
len=B.m_Length;
N.m_Sign=1-N.m_Sign;
}
for(register int i=0;i<len;i++)
{ if((Bigger[i]-carry)>=Small[i])
{
N.m_Value[i]=Bigger[i]-carry-Small[i];
carry=0;
}
else
{
sum=0x100000000+Bigger[i];
N.m_Value[i]=(unsigned long)(sum-carry-Small[i]);
carry=1;
}
}
while(N.m_Value[len-1]==0)
len--;
N.m_Length=len;
}
else
N.SetValue(0);
}
return N;
}
CBint CBint::Add(long B) const
{ CBint N(*this);
if(B==0)
return N;
if((m_Sign*B)>=0)
{ unsigned __int64 sum;
sum=(unsigned __int64)B+N.m_Value[0];
N.m_Value[0]=(unsigned long)sum;
if(sum>0xffffffff)
{ register int i=1;
while(i<BI_MAXLEN && N.m_Value[i]==0xffffffff)
{ N.m_Value[i]=0;
i++;
}
N.m_Value[i]++;
if(i<BI_MAXLEN)
N.m_Length=i+1;
}
return N;
}
else
return N.Sub(-B);
}
//大数相减
//调用形式：N.Sub(B)，返回值：N-B
//若两大数符号相同，其值相减，否则改变参数符号再调用大数相加函数
/******************************************************************/
/*
例如：
A B C
- D E
--------------
= F G H
其中，若C>=E，则H=C-E，carry(借位标志)=0
若C<E，则H=C-E+0x100000000，carry=1
若B-carry>=D，则G=B-carry-D，carry=0
若B-carry<D，则G=B-carry-D+0x10000000，carry=1
若carry=0，则F=A
若carry=1，A>1，则F=A-1
若carry=1，A=1，则F=0
/*****************************************************************/
CBint CBint::Sub(const CBint& B) const
{ CBint N(*this);
if(m_Sign==B.m_Sign)
{ int cmp=N.CompareAbs(B);
if(cmp)
{ int len,carry=0;
unsigned __int64 num;
unsigned long *Bigger,*Small;
if(cmp>0)
{
Bigger=(unsigned long*)N.m_Value;
Small=(unsigned long*)B.m_Value;
len=N.m_Length;
}
if(cmp<0)
{
Bigger=(unsigned long*)B.m_Value;
Small=(unsigned long*)N.m_Value;
len=B.m_Length;
N.m_Sign=1-N.m_Sign;
}
for(register int i=0;i<len;i++)
{ if((Bigger[i]-carry)>=Small[i])
{
N.m_Value[i]=Bigger[i]-carry-Small[i];
carry=0;
}
else
{
num=0x100000000+Bigger[i];
N.m_Value[i]=(unsigned long)(num-carry-Small[i]);
carry=1;
}
}
while(len>1 && N.m_Value[len-1]==0)
len--;
N.m_Length=len;
}
else
N.SetValue(0);
return N;
}
else
{ int cmp=N.CompareAbs(B);
if(cmp)
{ if(N.m_Length<B.m_Length)
N.m_Length=B.m_Length;
unsigned __int64 sum;
int carry=0;
for(register int i=0;i<N.m_Length;i++)
{
sum=(unsigned __int64)N.m_Value[i]+B.m_Value[i]+carry;
N.m_Value[i]=(unsigned long)sum;
carry=sum>0xFFFFFFFF?1:0;
}
if(N.m_Length<BI_MAXLEN)
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -