📄 usuperint.cpp
字号:
// USuperInt.cpp: implementation of the CUSuperInt class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "USuperInt.h"
#include "math.h"
#pragma warning(disable:4035)
/*
无符号大整数类
作者：缪元虎,四川绵阳供电局
myh9999@vip.sina.com
QQ:3977993
最后修改时间：2003-8-10
*/
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
//默认的最小长度（以双字为单位)
const DefaultLen = 1;
//设置能处理的最大整数长度（以双字为单位)
//即最大的整数为（下面是以指数形式表示的）
// 32*MaxLen
// 2 -1
// 2
//如果表示成10进制数，最大的数长度为
//MaxLen * 32 * log(2) / log(10) + 1;
//考虑到一个win32程序可用的内存空间名义上有4G，实际除了操作系统和一些额外开销，不足2G，
//一个DWORD占4字节，所有2G/4= 0x20000000;
//加上要运算，肯定有多个数，考虑MaxLen为0x1000000比较合适
//大约表示成十进制数有1.6亿位，已经非常大了。
const MaxLen = 0x1000000;
//自定义的memcpy函数，用纯汇编编写，big.asm
//如果你只想用系统提供的函数，则请将下面的语句作为注释，再将再下面的语句注释符号取消
//这段代码作为使用汇编混合编程的演示（因为还有一些代码也可如此做，只是作者时间有限）
//big.asm用masm6.11编译生成了big.obj,在程序设置Link选项中Object/Libary Modules中加入big.obj
//编译使用的命令行是：ML /c /coff big.asm
extern "C" void MemCpy(DWORD* dst, DWORD* src, DWORD n);
//系统的memcpy函数
//#define MemCpy(dst, src, n) memcpy(dst, src, n<<2)
//内联汇编编写的memcpy函数
/*
void MemCpy(DWORD* dst, DWORD* src, DWORD n)
{
__asm
{
mov ecx, n;
jecxz to_end;
//保存方向标志
pushf;
mov edi,dst;
mov esi, src;
cmp edi, esi;
jbe to_up; //dst <= src;
mov eax, ecx;
shl eax, 2;
add eax, esi;
cmp edi, eax;
jae to_up; //dst >= src+4n
mov eax, ecx;
dec eax;
shl eax, 2;
add edi, eax;
add esi, eax;
std;
jmp to_mov;
to_up:
cld;
to_mov:
rep movsd;
popf;
to_end:
}
}
*/
CUSuperInt::CUSuperInt()
{
pValue = new DWORD[len = DefaultLen];
*pValue = 0;
last = 1;
}
CUSuperInt::~CUSuperInt()
{
delete [] pValue;
}
CUSuperInt::CUSuperInt(CUSuperInt &x)
{
pValue = new DWORD[ len = x.len];
MemCpy(pValue, x.pValue, last = x.last);
}
CUSuperInt::CUSuperInt(DWORD dwValue)
{
pValue = new DWORD[ len = DefaultLen];
*pValue = dwValue;
last = 1;
}
CUSuperInt::CUSuperInt(char* pszVal)
{
len = DefaultLen;
pValue = new DWORD[len];
operator = (pszVal);
}
void CUSuperInt::Expand(DWORD n)
{
if (n > MaxLen)
{
CMyException* exception = new CMyException("超过规定能处理的最大整数", My_ErrorNo_OverFlow);
throw exception;
}
if (n > len)
{
DWORD* pTemp = new DWORD [len = n];
MemCpy(pTemp, pValue, last);
delete [] pValue;
pValue = pTemp;
}
}
CUSuperInt& CUSuperInt::operator = (CUSuperInt& x)
{
if (this != &x)
{
if (len < x.last)
{
Expand(LeastOver(x.last));
}
MemCpy(pValue, x.pValue, last = x.last);
}
return *this;
}
CUSuperInt& CUSuperInt::operator = (DWORD dwValue)
{
*pValue = dwValue;
last = 1;
return *this;
}
CUSuperInt& CUSuperInt::operator *= (DWORD dwValue)
{
if (dwValue == 0)
{
*pValue = 0;
last = 1;
}
else if (dwValue != 1)
{
DWORD times;
__asm
{
bsr ebx, dwValue;
bsf ecx, dwValue;
cmp ebx, ecx;
jne M0; //如果是2的n次方，则使用移位的乘法
mov times, ebx;
}
return Double(times);
M0:
DWORD dwFull;
__asm
{
mov ebx, this;
mov esi, [ebx]this.pValue;
mov ecx, [ebx]this.last;
mov ebx, dwValue; //乘数
xor edi, edi; //作临时存贮器,保存高位
L1:
mov eax, [esi];
mul ebx;
add eax, edi;
mov [esi], eax;
adc edx, 0;
mov edi, edx;
add esi, 4;
loop L1;
cmp edi, 0;
je L2;
mov dwFull, edi;
}
if (last == len)
{
Expand(LeastOver(last+1));
}
pValue[last++] = dwFull;
}
L2:
return *this;
}
CUSuperInt& CUSuperInt::operator *= (CUSuperInt& x)
{
CUSuperInt a(*this);
CUSuperInt b;
CUSuperInt result;
a.Expand(LeastOver(x.last + last));
result.Expand(LeastOver(x.last + last)); //不用this保存结果是因为可能x＝this
b.Expand(LeastOver(x.last + last));
for (DWORD i=0; i<x.last; i++)
{
b = a;
result.operator += (b *= x.pValue[i]);
a.Double(32);
}
return *this = result;
}
CUSuperInt CUSuperInt::operator * (CUSuperInt& x)
{
CUSuperInt a(*this);
return a *= x;
}
CUSuperInt CUSuperInt::operator * (DWORD dwValue)
{
CUSuperInt a(*this);
return a *= dwValue;
}
CUSuperInt& CUSuperInt::operator += (DWORD dwValue)
{
__asm
{
mov ebx, this;
mov edi, [ebx]this.pValue;
mov ecx, [ebx]this.last;
mov eax, dwValue;
add [edi], eax;
jnc L3;
mov edx, 1;
jmp L2;
L1:
add dword ptr[edi][edx*4], 1;
jnc L3;
inc edx;
L2:
loop L1;
}
if (last == len)
{
Expand(LeastOver(len+1));
}
pValue[last++] = 1;
L3:
return *this;
}
CUSuperInt& CUSuperInt::operator += (CUSuperInt& x)
{
Expand(x.len);
last = max(last, x.last);
__asm
{
mov ebx, this;
mov edi, [ebx]this.pValue;
mov edx, x;
mov esi, [edx]x.pValue;
mov ecx, [edx]x.last;
xor edx, edx;
clc;
L1:
mov eax, [esi][edx*4];
adc [edi][edx*4], eax;
inc edx;
loop L1;
jnc L4;
mov ecx, [ebx]this.last; //如果this的有效位更长，则加进位
mov ebx, x;
sub ecx, [ebx]x.last;
jz L3;
L2:
add [edi][edx*4], 1;
jnc L4;
inc edx;
loop L2;
}
L3:
if (last == len)
{
Expand(LeastOver(len+1));
}
pValue[last++] = 1;
L4:
return *this;
}
CUSuperInt CUSuperInt::operator + (DWORD dwValue)
{
CUSuperInt a(*this);
return a += dwValue;
}
CUSuperInt CUSuperInt::operator + (CUSuperInt& x)
{
CUSuperInt a(*this);
return a += x;
}
CUSuperInt& CUSuperInt::Double(DWORD dwTimes /*= 1*/)
{
if (dwTimes % 32 != 0)
{
DWORD dwFull = 0;
__asm
{
mov ebx, this;
mov edi, [ebx]this.pValue;
mov ebx, [ebx]this.last;
xor eax, eax;
mov ecx, dwTimes;
L1:
mov edx, [edi];
shld [edi], eax, cl;
mov eax, edx;
add edi, 4;
dec ebx;
jnz L1;
neg cl;
shr edx, cl;
jz L2;
mov dwFull, edx;
}
if (len == last)
{
Expand(LeastOver(last+1));
}
pValue[last++] = dwFull;
}
L2:
DWORD dwStep = dwTimes >> 5; //除以32
if (dwStep > 0)
{
Expand(LeastOver(last+dwStep));
MemCpy(&pValue[dwStep], pValue, last);
last += dwStep;
}
return *this;
}
void CUSuperInt::Compress()
{
DWORD n = LeastOver(last);
if (n < len)
{
DWORD *pTemp = new DWORD [len=n];
MemCpy(pTemp, pValue, last);
delete [] pValue;
pValue = pTemp;
}
}
CUSuperInt CUSuperInt::operator ++(int) //a++
{
CUSuperInt a(*this);
operator += (1);
return a;
}
CUSuperInt CUSuperInt::operator ++() //++a
{
return operator += (1);
}
inline DWORD CUSuperInt::LeastOver(DWORD n)
{
__asm
{
bsr ebx, n;
bsf ecx, n;
cmp ebx, ecx;
je to_set;
inc ebx;
to_set:
xor eax, eax;
bts eax, ebx;
}
}
void CUSuperInt::Debug()
{
TRACE3("\r\nlen= %d,last= %d \r\nHex=%s\r\n",
len, last, ToHexStr());
TRACE1("Dec=%s\r\n",ToDecStr());
}
//////////////////////////////////////////////////////////////////////
// CMyException Class
//////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CMyException::CMyException(char* msg, UINT uErrorNo)
{
m_szMsg = msg;
m_uErrorNo = uErrorNo;
}
CMyException::~CMyException()
{
}
CUSuperInt& CUSuperInt::Half(DWORD dwTimes /*= 1*/)
{
DWORD dwStep = dwTimes / 32;
if (dwStep >= last)
{
*pValue = 0;
last = 1;
return *this;
}
else if (dwStep > 0)
{
MemCpy(pValue, &pValue[dwStep], last-=dwStep);
}
if (dwTimes % 32 != 0)
{
__asm
{
mov ebx, this;
mov edi, [ebx]this.pValue;
mov ebx, [ebx]this.last;
dec ebx;
mov ecx, dwTimes;
xor edx, edx;
L1:
cmp ebx, edx;
je L2;
mov eax, 4[edi][edx*4];
shrd [edi][edx*4], eax, cl;
inc edx;
jmp L1;
L2:
xor eax, eax;
shrd [edi][edx*4], eax, cl;
}
if (last > 1 && pValue[last-1] == 0)
{
last --;
}
}
return *this;
}
CUSuperInt CUSuperInt::operator /= (CUSuperInt& x)//返回余数
{
if (x == 0) //除数为0
{
CMyException* exception = new CMyException("除数为0", My_ErrorNo_ZeroByDiv);
throw exception;
}
if (*this == 0 || x == 1)//被除数为0或除数为1
{
return *this;
}
if (x.last == 1) //除数为DWORD时
{
return operator /= (x.pValue[0]);
}
//商数
CUSuperInt r;
r.Expand(LeastOver(last-x.last+1));
r.last = last- x.last + 1;
memset(r.pValue, 0, 4*r.len);
//减数数组，分别为x*2^i, （i从0到31），暂时为空，如需要再分配
CUSuperInt* xx[32];
xx[0] = new CUSuperInt(x);
for (int i=1; i<32; i++)
{
xx[i] = NULL;
}
//除数高位第一个1的位置(二进制）
DWORD bit_x = x.pValue[x.last-1];
__asm
{
bsr eax, bit_x;
mov bit_x, eax
}
int nXX; //减数在减数数组中的编号
while (*this >= *xx[0])
{
__asm
{
//计算出高DWORD中二进制位1的位置差
mov ebx, this;
mov esi, [ebx]this.pValue;
mov ecx, [ebx]this.last;
bsr eax, [esi][4*ecx-4];
sub eax, bit_x;
add eax, 32;
and eax, 0x1f;
mov nXX, eax;
//如果减数指针为空，则新分配
mov eax, type xx;
mul nXX;
cmp xx[eax], 0;
jne to_cmp;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -