定义一个不受计算机字长限制的大整数类BigInt
2014年09月16日
⁄ 综合
⁄ 共 7037字 ⁄ 字号
小 中 大
/**//***********************************************************
定义一个不受计算机字长限制的大整数类BigInt，
要求BigInt之间、 BigInt与int之间能进行+、-、*、/、=等运算。
************************************************************/
#ifndef BIGINT_H_
#define BIGINT_H_
#include <iostream>
using namespace std;
#include <cstring>
class BigInt
...{
static const int MAX = 100;
int arr[MAX];
int length;
public:
BigInt();
BigInt( const char * );
int GetLen()const...{ return length; }
void SetLen(int len)...{ length = len; }
BigInt Add( BigInt & );
BigInt Sub( BigInt & );
BigInt Mul( BigInt & );
//BigInt Div( const BigInt & );
void ChangeEqualLen( int );
bool CompareBig( const BigInt & );
bool Compareequal( const BigInt & );
int CompareBigLen( const BigInt &, const BigInt & );
friend ostream &operator << ( ostream &, const BigInt & );
};
#endif
#include "bigint.h"
BigInt::BigInt()
...{
length = 0;
arr[0] = 0;
}
BigInt::BigInt( const char *p )
...{
length = strlen( p ) + 1;
arr[0] = 0;
for( int i = 1; i < length; i++ )
arr[i] = p[i - 1] - '0' ;
}
BigInt BigInt::Add( BigInt & bigint )
...{
BigInt temp;
int i;
int len = CompareBigLen( *this, bigint );
if( this->GetLen() != len )
this->ChangeEqualLen( len );
else if( bigint.GetLen() != len )
bigint.ChangeEqualLen( len );
for( i = len - 1; i > 0; i-- )
...{
temp.arr[i] = this->arr[i] + bigint.arr[i];
if( temp.arr[i] > 9 && temp.arr[i] < 20 )
...{
temp.arr[i] -= 10;
temp.arr[i - 1] += 1;
}
else if( temp.arr[i] >= 20 )
...{
temp.arr[i] -= 20;
temp.arr[i - 1] += 2;
}
}
temp.SetLen(len);
return temp;
}
BigInt BigInt:: Sub( BigInt & bigint )
...{
BigInt temp;
int j = this->GetLen() - 1;
int len = CompareBigLen( *this, bigint );
if( this->GetLen() != len )
this->ChangeEqualLen( len );
else if( bigint.GetLen() != len )
bigint.ChangeEqualLen( len );
if(this->Compareequal(bigint))
goto A;
else if(this->CompareBig(bigint))
...{
if(len - 1 != len - j)
...{
this->arr[len - 1] += 10;
this->arr[len - j] -= 1;
for( int i = len - j + 1; i < len - 1; i++ )
this->arr[i] += 9;
}
for( int i = len - 1; i > 0; i-- )
...{
temp.arr[i] = this->arr[i] - bigint.arr[i];
if( temp.arr[i] > 9 )
...{
temp.arr[i] -= 10;
this->arr[i - 1] += 1;
}
}
}
else
...{
int j = bigint.GetLen() - 1;
if( j != 1)
...{
bigint.arr[len - 1] += 10;
bigint.arr[len - j] -= 1;
for( int i = len - j + 1; i < len - 1; i++ )
bigint.arr[i] += 9;
}
A: for( int i = len - 1; i > 0; i-- )
...{
temp.arr[i] = bigint.arr[i] - this->arr[i];
if( temp.arr[i] > 9 )
...{
temp.arr[i] -= 10;
bigint.arr[i - 1] += 1;
}
}
for( int i = 0; i< bigint.GetLen(); i++ )
...{
if( temp.arr[i] != 0 )
...{
temp.arr[i] = -temp.arr[i];
break;
}
}
}
temp.SetLen(len);
return temp;
}
BigInt BigInt::Mul( BigInt & bigint )
...{
BigInt temp;
int i,j,m,k,tmpcnt;
temp.SetLen( this->GetLen() + bigint.GetLen() - 2);
for( i = 0; i < temp.GetLen() ; i++ )
temp.arr[i] = 0;
tmpcnt = temp.GetLen() - 1;
for( j = bigint.GetLen() - 1; j > 0 ; j-- )
...{
for( k = tmpcnt,i = this->GetLen() - 1; i > 0; k-- ,i-- )
...{
temp.arr[k] += this->arr[i] * bigint.arr[j];
}
tmpcnt--;
}
for( i = temp.GetLen() - 1; i >= 0 ; i-- )
...{
if( temp.arr[i] > 9 )
...{
temp.arr[i - 1] += temp.arr[i] / 10;
temp.arr[i] %= 10;
}
}
return temp;
}
ostream & operator<<( ostream & os, const BigInt & bigint )
...{
bool flag1 = false,flag2 = true; //flag1 == false表示前几位为0，flag2 == true表示正数。
for( int i = 0; i < bigint.GetLen(); i++ )
...{
if( flag1 == false && bigint.arr[i] == 0)
if( i == bigint.GetLen() - 1 && bigint.arr[i] == 0)
...{
cout << "0" << endl;
break;
}
else
continue;
else
...{
flag1 = true;
if( bigint.arr[i] >= 0 && flag2 == true )
...{
os << bigint.arr[i];
continue;
}
else if( bigint.arr[i] < 0 && flag2 == true)
...{
os << bigint.arr[i];
flag2 = false;
}
else if( bigint.arr[i] < 0 && flag2 == false )
...{
os << abs( bigint.arr[i]);
flag2 = false;
}
else if( bigint.arr[i] >= 0 && flag2 == false )
...{
os << bigint.arr[i];
flag2 = false;
}
}
}
os << endl;
return os;
}
int BigInt::CompareBigLen( const BigInt & temp1, const BigInt & temp2 )
...{
return ((temp1.GetLen() >= temp2.GetLen()) ? temp1.GetLen() : temp2.GetLen());
}
void BigInt::ChangeEqualLen( int n ) //把此大整数数组转换成长度为N的数组。前面添0。
...{
int j = this->GetLen();
for( int i = n - 1; i > n - j - 1; i-- )
...{
this->arr[i] = this->arr[i - ( n - j)];
}
for( int i = 0; i <= n - j - 1; i++ )
this->arr[i] = 0;
this->SetLen(n);
}
bool BigInt::CompareBig( const BigInt & bigint )
...{
int i;
for( i = 0; i< this->GetLen(); i++ )
...{
if(this->arr[i] != bigint.arr[i] )
...{
if( this->arr[i] > bigint.arr[i] )
...{
return true;
break;
}
else if( this->arr[i] < bigint.arr[i])
...{
return false;
break;
}
}
}
}
bool BigInt::Compareequal( const BigInt & bigint )
...{
if( this->GetLen() != bigint.GetLen() )
return false;
else
...{
for( int i = 0; i< this->GetLen(); i++ )
...{
if(this->arr[i] == bigint.arr[i] )
continue;
else if(this->arr[i] != bigint.arr[i] )
return false;
else if(this->arr[i] == bigint.arr[i] && i == bigint.GetLen())
return true;
}
}
}
#include "bigint.h"
int main()
...{
char *p = new char[100];
BigInt add,sub,mul;
cout << "请任意输入一个大整数:";//缺少合法性检查
cin >> p;
BigInt temp1(p);
cout << "请任意输入另外一个大整数:";//缺少合法性检查
cin >> p;
BigInt temp2(p);
BigInt temp3,temp4,temp5, temp6;
temp3 = temp5 = temp1;
temp4 = temp6 =temp2;
add = temp1.Add( temp2 );
cout <<" a + b ＝ " << add;
sub = temp1.Sub( temp2 );
cout <<" a - b ＝ " << sub;
mul = temp3.Mul( temp4 );
cout <<" a * b ＝ " << mul;
//mul = temp5.Mul( temp6 );
//cout <<" a / b ＝ " << mul;
delete[] p;
return 0;
}