大整数.cpp

大整数计算

#include <iostream.h> 
//#include <stdafx.h>
#define MAX_LEN 100 

class MEGA_INTEGER{ 
private: 
int x1[MAX_LEN],x2[MAX_LEN],x3[MAX_LEN],x4[MAX_LEN]; 
int n1,n2,n3,n4; 

void hadd(int *xx1,int *xx2,int *xx3,int xn1,int xn2,int &xn3) 
{ 
int i,j,k=0; 

if(xn1>xn2){ 
xn3=xn1; 
for(i=0;i<xn1-xn2;i++)xx2[MAX_LEN-xn3+i]=0; 
} 
else { 
xn3=xn2; 
for(i=0;i<xn2-xn1;i++)xx1[MAX_LEN-xn3+i]=0; 
} 

for(i=0;i<xn3;i++){ 
j=xx1[MAX_LEN-1-i]+xx2[MAX_LEN-1-i]+k; 
k=j/10; 
xx3[MAX_LEN-1-i]=j%10; 
} 
if(k&&(MAX_LEN-xn3>=1)){ 
xx3[MAX_LEN-1-xn3]=k; 
xn3++; 
} 
} 

void hsub(int *xx1,int *xx2,int *xx3,int xn1,int xn2,int &xn3) 
{ 
int i,j,k=0; 

xn3=xn1; 
for(i=0;i<xn1-xn2;i++)xx2[MAX_LEN-xn3+i]=0; 

for(i=0;i<xn3;i++){ 
j=xx1[MAX_LEN-1-i]-xx2[MAX_LEN-1-i]-k; 
if(j>=0){ 
k=0; 
xx3[MAX_LEN-1-i]=j; 
} 
else{ 
k=1; 
xx3[MAX_LEN-1-i]=j+10; 
} 
} 
for(i=0;i<xn3-1&&xx3[MAX_LEN-xn3+i]==0;i++); 
xn3-=i; 
} 

int hdiv(int *xx1,int *xx2,int *xx3,int xn1,int xn2,int &xn3) 
{ 
int i,k; 

if(xn1>xn2)k=0; 
else if(xn1==xn2){ 
for(i=0,k=2;i<xn1;i++){ 
if(xx1[MAX_LEN-xn1+i]>xx2[MAX_LEN-xn1+i]){k=0;break;} 
else if(xx1[MAX_LEN-xn1+i]<xx2[MAX_LEN-xn1+i]){k=1;break;} 
} 
} 
else k=1; 
if(k==1){ 
for(i=0;i<xn1;i++)xx3[MAX_LEN-1-i]=xx1[MAX_LEN-1-i]; 
xn3=xn1; 
} 
if(k==2){xx3[MAX_LEN-1]=0;xn3=1;} 
if(k==0)hsub(xx1,xx2,xx3,xn1,xn2,xn3); 
return k; 
} 

void hmul(int *xx1,int *xx2,int xn1,int &xn2,int xn) 
{ 
int i,j,k=0; 

for(i=0;i<xn1;i++){ 
j=xx1[MAX_LEN-1-i]*xn+k; 
k=j/10; 
xx2[MAX_LEN-1-i]=j%10; 
} 

xn2=xn1; 
if(k&&(MAX_LEN-xn2>=1)){ 
xx2[MAX_LEN-1-xn2]=k; 
xn2++; 
} 
for(i=0;i<xn2-1&&xx2[MAX_LEN-xn2+i]==0;i++); 
xn2-=i; 
} 

public: 
MEGA_INTEGER(char *,char *); 
void my_add(void); 
void my_sub(void); 
void my_mul(void); 
int my_div(void); 
void display(int); 
}; 

MEGA_INTEGER::MEGA_INTEGER(char *y1="0",char *y2="0") 
{ 
int i; 

for(n1=0;n1<MAX_LEN&&y1[n1]>='0'&&y1[n1]<='9';n1++); 
for(i=0;i<n1;i++)x1[MAX_LEN-n1+i]=*(y1+i)-48; 
for(i=0;i<n1-1&&x1[MAX_LEN-n1+i]==0;i++); 
n1-=i; 
for(n2=0;n2<MAX_LEN&&y2[n2]>='0'&&y2[n2]<='9';n2++); 
for(i=0;i<n2;i++)x2[MAX_LEN-n2+i]=*(y2+i)-48; 
for(i=0;i<n2-1&&x2[MAX_LEN-n2+i]==0;i++); 
n2-=i; 
} 

void MEGA_INTEGER::my_add(void) 
{ 
hadd(x1,x2,x3,n1,n2,n3); 
} 

void MEGA_INTEGER::my_sub(void) 
{ 
hsub(x1,x2,x3,n1,n2,n3); 
} 

void MEGA_INTEGER::my_mul(void) 
{ 
int i,j,k,x[MAX_LEN],xn,y[MAX_LEN],yn=0; 

for(i=0;i<n2;i++){ 
hmul(x1,x,n1,xn,x2[MAX_LEN-1-i]); 
for(j=0;j<i&&(MAX_LEN-xn>=1);j++){ 
for(k=0;k<xn;k++)x[MAX_LEN-1-xn+k]=x[MAX_LEN-xn+k]; 
x[MAX_LEN-1]=0; 
xn++; 
} 
hadd(x,y,x3,xn,yn,n3); 
for(j=0;j<n3;j++)y[MAX_LEN-1-j]=x3[MAX_LEN-1-j]; 
yn=n3; 
} 
for(i=0;i<n3-1&&x3[MAX_LEN-n3+i]==0;i++); 
n3-=i; 
} 

int MEGA_INTEGER::my_div(void) 
{ 
int x[MAX_LEN],xn=0,i,j,k,n; 

if(n2==0||(n2==1&&x2[MAX_LEN-1]==0)){ 
cout<<"\n错误！"; 
return 1; 
} 

for(i=0,n3=n1;i<n1;i++){ 
for(j=0;j<xn;j++)x[MAX_LEN-1-xn+j]=x[MAX_LEN-xn+j]; 
x[MAX_LEN-1]=x1[MAX_LEN-n1+i]; 
xn++; 
k=hdiv(x,x2,x4,xn,n2,n4); 
if(k==2)x3[MAX_LEN-n1+i]=1; 
else if(k==1)x3[MAX_LEN-n1+i]=0; 
else { 
for(n=1;;n++){ 
for(j=0;j<n4;j++)x[MAX_LEN-1-j]=x4[MAX_LEN-1-j]; 
xn=n4; 
k=hdiv(x,x2,x4,xn,n2,n4); 
if(k==1)break; 
} 
x3[MAX_LEN-n1+i]=n; 
} 
for(j=0;j<n4;j++)x[MAX_LEN-1-j]=x4[MAX_LEN-1-j]; 
xn=n4; 
} 
for(i=0;i<n3-1&&x3[MAX_LEN-n3+i]==0;i++); 
n3-=i; 
for(i=0;i<n4-1&&x4[MAX_LEN-n4+i]==0;i++); 
n4-=i; 
return 0; 
} 

void MEGA_INTEGER::display(int k) 
{ 
int i; 

for(i=0;i<n3;i++)cout<<x3[MAX_LEN-n3+i]; 
if(k){ 
cout<<"\n"; 
for(i=0;i<n4;i++)cout<<x4[MAX_LEN-n4+i]; 
} 
} 

void main(void) 
{ 
char s1[MAX_LEN],s2[MAX_LEN]; 
int k; 

cout<<"\n\n输入2个整数：\n"; 
cin>>s1>>s2; 
MEGA_INTEGER xx(s1,s2); 
cout<<"\n加法运算：\n"; 
xx.my_add(); 
xx.display(0); 
cout<<"\n减法运算：\n"; 
xx.my_sub(); 
xx.display(0); 
cout<<"\n乘法运算：\n"; 
xx.my_mul(); 
xx.display(0); 
cout<<"\n除法运算：\n"; 
k=xx.my_div(); 
if(!k)xx.display(1); 
}