hugeint.cpp

此程序用于大整数运算

#include <iomanip>
#include <iostream>
#include <string>
#include "hugeint.h"
#include <vector>
using namespace std;
HugeInt::HugeInt()		
{
	ch=true;
	value.push_back(0);
	return;
}
HugeInt::HugeInt(long b)
{	
	if(b>=0)ch=true;
	else {ch=false;b=-b;}
	while(b>=1){
		value.push_back(b%10000);
		b=b/10000;
	}
	return;
}
HugeInt::HugeInt(char* b)
{
	int count=0,k;
	long x=0;
	string m=b;
	int c=0;
	if(m[0]=='-')c=1;
	for(int i=m.length()-1;i>=c;i--){
		count++;
		k=1;
		for(int j=1;j<=count-1;j++)k*=10;
		x+=(m[i]-'0')*k;
		if(!(count%4)){
			value.push_back(x);
			x=0;
			count=0;
		}
	}
	if(count>0)value.push_back(x);
	if(c)ch=false;
	else ch=true;
	return;
}
HugeInt::HugeInt(HugeInt &b)
{
	ch=b.ch;
	value=b.value;
	return;
}
HugeInt::~HugeInt()
{
}

HugeInt operator +(const HugeInt& a,const HugeInt& b)
{
	HugeInt c;
	if(a.ch!=b.ch){
		if(!(compare(a.value,b.value)||compare(a.value,b.value)))return c=long(0);
		if(compare(a.value,b.value))c.ch=a.ch;
		else c.ch=b.ch;
		c.value=a.value-b.value; 
	}
	else {
		c.ch=a.ch;
		c.value=a.value+b.value;
	}
	return c;

}

HugeInt operator -(const HugeInt& a,const HugeInt& b)
{
	HugeInt c;
	if(a.ch!=b.ch){
		c.ch=a.ch;
		c.value=a.value+b.value;
	}
	else {
		if(!(compare(a.value,b.value)||compare(b.value,a.value)))return c=long(0);
		if(compare(a.value,b.value))c.ch=a.ch;
		else c.ch=!b.ch;
		c.value=a.value-b.value; 
	}
	return c;
}

HugeInt operator *(const HugeInt& a,const HugeInt& b)
{
	HugeInt c;
	if(a.ch==b.ch)c.ch=true;
	else c.ch=false;
	c.value=a.value*b.value;
	return c;
}

HugeInt operator /(const HugeInt& a,const HugeInt& b)
{
	HugeInt c;
	if(a.ch==b.ch)c.ch=true;
	else c.ch=false;
	c.value=a.value/b.value;
	return c;
}

HugeInt operator %(const HugeInt& a,const HugeInt& b)
{
	HugeInt c;
	if(a.ch==b.ch)c.ch=true;
	else c.ch=false;
	c.value=a.value/b.value;
	c.value=a.value-b.value*c.value;
	return c;
}
HugeInt& HugeInt::operator =(const HugeInt& b)
{
	ch=b.ch;
	value.clear();
	value=b.value;
	return *this;
}

bool operator >(const HugeInt& a,const HugeInt& b)
{
	if(a.ch>b.ch)return true;
	if(a.ch<b.ch)return false;
	if(a.ch)return compare(a.value,b.value);
	else return !compare(a.value,b.value);
}
bool operator >=(const HugeInt& a,const HugeInt& b)
{
	return !(a<b);
}
bool operator <(const HugeInt& a,const HugeInt& b)
{	if(a.ch<b.ch)return true;
	if(a.ch>b.ch)return false;
	if(a.ch)return !compare(a.value,b.value);
	else return compare(a.value,b.value);
}
bool operator <=(const HugeInt& a,const HugeInt& b)
{
	return !(a>b);
}
bool operator ==(const HugeInt& a,const HugeInt& b)
{
	if(a.ch!=b.ch)return false;
	if(compare(a.value,b.value)||compare(b.value,a.value))return false;
	return true;
}
bool operator !=(const HugeInt& a,const HugeInt& b)
{
	return !(a==b);
}
istream& operator >>(istream& in,HugeInt& b)
{
	int count=0,k;
	long x=0;
	string m;
	in>>m;
	int c=0;
	if(m[0]=='-')c=1;
	b.value.clear();
	for(int i=m.length()-1;i>=c;i--){
		count++;
		k=1;
		for(int j=1;j<=count;j++)k*=10;
		x+=(m[i]-'0')*k;
		if(!(count%4)){
			b.value.push_back(x);
			x=0;
			count=0;
		}
	}
	if(count>0)b.value.push_back(x);
	if(c)b.ch=false;
	else b.ch=true;
	return in;
}
ostream& operator <<(ostream& out,HugeInt& b)
{
	if(!b.ch)out<<'-';
	int i=b.value.size()-1;
	out<<b.value[i--];
	for(;i>=0;i--)out<<setw(4)<<setfill('0')<<b.value[i];
	
	return out;
}

bool compare(const INT& a,const INT& b)
{
	if(a.size()>b.size())return true;
	if(a.size()<b.size())return false;
	int count=a.size();
	while(count--){
		if(a[count]>b[count])return true;
		if(a[count]<b[count])return false;
	}
	return false;
}

INT operator +(const INT& a,const INT& b)
{
	INT aa,bb;
	if(a.size()>b.size()){aa=a;bb=b;}
	else {aa=b;bb=a;}
	int sza=aa.size(),szb=bb.size();
	long x=0;
	INT c;
	int i=0;
	for(;i<szb;i++){
		x=aa[i]+bb[i]+x/10000;
		c.push_back(x%10000);
	}
	for(;i<sza;i++){
		x=aa[i]+x/10000;
		c.push_back(x%10000);
	}
	x=x/10000;
	if(x>0)c.push_back(x);
	return c;
}

INT operator -(const INT& a,const INT& b)
{
	INT aa,bb;
	if(compare(a,b)){aa=a;bb=b;}
	else {aa=b;bb=a;}
	int sza=aa.size(),szb=bb.size(),count=0;
	long x=0;
	INT c;
	int i=0;
	for(;i<szb;i++){
		if(aa[i]>=bb[i]+count){x=aa[i]-count;count=0;}
		else {x=aa[i]-count+10000;count=1;}
		c.push_back(x-bb[i]);
	}
	for(;i<sza;i++){
		if(aa[i]>=count){x=aa[i];count=0;}
		else {x=aa[i]-count;count=1;}
		c.push_back(x);
	}
	for(i=c.size()-1;i>0;i--){
		if(c[i]==0)c.erase(&c[i]);
		else break;
	}
	return c;
}

INT operator *(const INT& a,const INT& b)
{
	int sza=a.size(),szb=b.size();
	long x=0;
	INT c,store;
	for(int i=0;i<szb;i++){
		int count=i;
		while(count-->0)store.push_back(0);
		for(int j=0;j<sza;j++){
			x=a[j]*b[i]+x/10000;
			store.push_back(x%10000);
		}
		x=x/10000;
		if(x>0)store.push_back(x);
		c=store+c;
		store.clear();
	}
	return c;
}

INT operator /(const INT& a,const INT& b)
{
	INT sum0,sum1,sum10;
	sum0.push_back(0);
	sum1.push_back(1);
	sum10.push_back(10);

	if(!(compare(b,sum0)||compare(sum0,b))){
		cout<<"The divisor can't be 0;";
		throw math_error(1);
	}

	if(compare(b,a))return sum0;
	if(!(compare(b,sum1)||compare(sum1,b)))return a;

	INT c,s,d;
	s=a;
	d=b;
	int i,j,sz;
	for(i=1;;i++){
		if(compare(d*sum10,s))break;
		else d=d*sum10;
	}
	sz=i;
	int *h=new int[sz];
	for(j=0;j<sz;j++)h[j]=0;
	
	for(d=b;!compare(d,s);){		
		for(i=1;;i++){
			if(compare(d*sum10,s))break;
			else d=d*sum10;
		}
		for(j=1;j<10;j++){
			c.clear();
			c.push_back(j+1);
			if(compare(d*c,s))break;		
		}
		h[i-1]=j;
		c.clear();
		c.push_back(j);
		s=s-d*c;
		d=b;

	}
	int count,k;
	long x;
	c.clear();
	for(i=0,x=0,count=0;i<sz;i++){
		count++;
		k=1;
		for(j=1;j<=count-1;j++)k*=10;
		x+=h[i]*k;
		if(!(count%4)){
			c.push_back(x);
			x=0;
			count=0;
		}
	}
	if(count>0)c.push_back(x);
	delete[] h;
	return c;
}