?? dicorder.cpp
字號:
#include <fstream>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <iostream>
#include "time.h"
#include "windows.h"
using namespace std;
int minlast,maxlast;
#ifndef BIG_INT
#define BIG_INT
#include "math.h"
#include <string>
#pragma warning(disable:4035)
typedef unsigned long DWORD;
typedef unsigned int UINT;
typedef unsigned char BYTE;
const DefaultLen = 1;
const MaxLen = 0x0100000;
class CBigInt
{
public:
//構造及析構函數
CBigInt();
CBigInt(DWORD dwValue);
CBigInt(char* pszVal);
CBigInt(const CBigInt& x);
/*virtual*/ ~CBigInt();
public:
//以下定義的是運算
//重載的賦值運算符
CBigInt& operator = (const CBigInt& x);
CBigInt& operator = (char* pszVal);
CBigInt& operator = (DWORD dwValue);
//重載的加法運算符
CBigInt& operator += (CBigInt& x);
CBigInt& operator += (DWORD dwValue);
CBigInt operator + (CBigInt& x);
CBigInt operator + (DWORD dwValue);
CBigInt operator ++(); //++a
CBigInt operator ++(int); //a++
//重載的減法運算符,因為是無符號數，所以結果為大數減小數得到的差
CBigInt& operator -= (CBigInt& x);
CBigInt& operator -= (DWORD dwValue);
CBigInt operator - (CBigInt& x);
CBigInt operator - (DWORD dwValue);
CBigInt& operator --(); //--a
CBigInt operator --(int); //a--
//重載的乘法運算符
CBigInt& operator *= (DWORD dwValue);
CBigInt& operator *= (CBigInt& x);
CBigInt operator * (DWORD dwValue);
CBigInt operator * (CBigInt& x);
//重載的除法運算符
DWORD operator /= (DWORD dwValue); //返回余數
CBigInt operator /= (CBigInt& x);//返回余數
CBigInt operator / (DWORD dwValue); //返回商
CBigInt operator / (CBigInt& x);//返回商
CBigInt operator % (CBigInt& x);
DWORD operator % (DWORD dwValue);
//重載的比較運算符
bool operator == (const CBigInt& x);
bool operator == (DWORD dwValue);
bool operator != (const CBigInt& x);
bool operator != (DWORD dwValue);
bool operator > (const CBigInt& x);
bool operator > (DWORD dwValue);
bool operator >= (const CBigInt& x);
bool operator >= (DWORD dwValue);
bool operator < (const CBigInt& x);
bool operator < (DWORD dwValue);
bool operator <= (CBigInt& x);
bool operator <= (DWORD dwValue);
//乘2運算，即 // a = a * 2^dwTimes; 相當于左移一位二進制，低位補0
CBigInt& Double(DWORD dwTimes = 1);
//除2運算; 相當于右移一位二進制，高位邊補0,低位舍棄
CBigInt& Half(DWORD dwTimes = 1);
public:
//以下定義的是常用的操作
//重新分配內存空間,用于增加數據長度，n為新長度
void Expand(DWORD n);
//壓縮數據，以節省空間。指去掉高位多余的0。
void Compress();
//轉換在十六進制數字符串
void ToHexStr(std::string& s);
std::string ToHexStr();
//轉換成十進制數字符串
void ToDecStr(std::string& s);
std::string ToDecStr();
unsigned long size(){return (this->ToDecStr()).size();}
protected:
//輔助函數
inline DWORD LeastOver(DWORD n) ;//查找一個比n大，且為2^x次方的數
protected:
DWORD *pValue; //指向一個DWORD數組，用于存放數值
DWORD len; //DWORD數組的長度
DWORD last; //數組中的有效長度
};
const My_ErrorNo_OverFlow = 0;
const My_ErrorNo_ZeroByDiv = 1;
class CMyException
{
public:
CMyException(char* msg, UINT uErrorNo);
/*virtual*/ ~CMyException();
char* m_szMsg;
UINT m_uErrorNo;
protected:
CMyException(){}
};
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:
}
}
CBigInt::CBigInt()
{
pValue = new DWORD[len = DefaultLen];
*pValue = 0;
last = 1;
}
CBigInt::~CBigInt()
{
delete [] pValue;
}
CBigInt::CBigInt(const CBigInt &x)
{
pValue = new DWORD[ len = x.len];
memset(&pValue[x.last],0,(len-x.last)*4);
MemCpy(pValue, x.pValue, last = x.last);
}
CBigInt::CBigInt(DWORD dwValue)
{
pValue = new DWORD[ len = DefaultLen];
*pValue = dwValue;
last = 1;
}
CBigInt::CBigInt(char* pszVal)
{
len = DefaultLen;
pValue = new DWORD[len];
operator = (pszVal);
}
void CBigInt::Expand(DWORD n)
{
if (n > MaxLen)
{
CMyException* exception = new
CMyException("超過規定能處理的最大整數", My_ErrorNo_OverFlow);
throw exception;
}
if (n > len)
{
DWORD* pTemp = new DWORD [len = n];
memset(&pTemp[last], 0, (n-last)*4);
len = n;
MemCpy(pTemp, pValue, last);
delete [] pValue;
pValue = pTemp;
}
}
CBigInt& CBigInt::operator = (const CBigInt& x)
{
if (this != &x)
{
if (len < x.last)
{
Expand(LeastOver(x.last));
}
MemCpy(pValue, x.pValue, last = x.last);
}
return *this;
}
CBigInt& CBigInt::operator = (DWORD dwValue)
{
*pValue = dwValue;
last = 1;
return *this;
}
CBigInt& CBigInt::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;
}
CBigInt& CBigInt::operator *= (CBigInt& x)
{
CBigInt a(*this);
CBigInt result;
a.Expand(LeastOver(x.last + last));
result.Expand(LeastOver(x.last + last));
//不用this保存結果是因為考慮到x可能等于*this
for (DWORD i=0; i<x.last; i++)
{
result.operator += (a * x.pValue[i]);
a.Double(16);
a.Double(16);
}
return *this = result;
}
CBigInt CBigInt::operator * (CBigInt& x)
{
CBigInt a(*this);
return a *= x;
}
CBigInt CBigInt::operator * (DWORD dwValue)
{
CBigInt a(*this);
return a *= dwValue;
}
CBigInt& CBigInt::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;
}
CBigInt& CBigInt::operator += (CBigInt& x)
{
Expand(x.len);
if(last<x.last)
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;
}
CBigInt CBigInt::operator + (DWORD dwValue)
{
CBigInt a(*this);
return a += dwValue;
}
CBigInt CBigInt::operator + (CBigInt& x)
{
CBigInt a(*this);
return a += x;
}
CBigInt& CBigInt::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
while (dwStep > 0)
{
Expand(LeastOver(last+dwStep));
MemCpy(&pValue[dwStep], pValue, last);
last += dwStep;
dwStep--;
}
return *this;
}
void CBigInt::Compress()
{
DWORD n = LeastOver(last);
if (n < len)
{
DWORD *pTemp = new DWORD [len=n];
MemCpy(pTemp, pValue, last);
delete [] pValue;
pValue = pTemp;
}
}
CBigInt CBigInt::operator ++(int) //a++
{
CBigInt a(*this);
operator += (1);
return a;
}
CBigInt CBigInt::operator ++() //++a
{
return operator += (1);
}
inline DWORD CBigInt::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;
}
}
//////////////////////////////////////////////////////////////////////
// CMyException Class
//////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CMyException::CMyException(char* msg, UINT uErrorNo)
{
m_szMsg = msg;
m_uErrorNo = uErrorNo;
}
CMyException::~CMyException()
{
}
CBigInt& CBigInt::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;
}
CBigInt CBigInt::operator /= (CBigInt& 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]);
}
//商數
CBigInt 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），暫時為空，如需要再分配
CBigInt* xx[32];
xx[0] = new CBigInt(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;
}
xx[nXX] = new CBigInt(x);
xx[nXX]->Double(nXX);
__asm
{
to_cmp:
//比較
mov eax, type xx;
mul nXX;
mov ebx, xx[eax];
mov esi, [ebx]xx.pValue;
mov ecx, [ebx]xx.last;
mov eax, ecx;
dec eax;
shl eax, 2;
add esi, eax;
mov edx, this;
mov edi, [edx]this.pValue;
mov eax, [edx]this.last;
dec eax;
shl eax, 2;
add edi, eax;
repe cmpsd;
jbe to_sub;
//減數變為前一個
//如果減數指針為空，則新分配
add nXX, 31;
and nXX, 0x1f;
mov eax, type xx;
mul nXX;
cmp xx[eax], 0;
jne to_sub;
}
xx[nXX] = new CBigInt(x);
xx[nXX]->Double(nXX);
__asm
{
to_sub:
mov eax, type xx;
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -