longnumber.h

自己做的一个支持加减乘的大数类

#include <iostream>
#include <deque>
#include <string>
#include <sstream>
#include <iterator>
#include <functional>
#include <algorithm>

using namespace std;

class LongNumber
{
public:
	static const int BASE=10000;
	static const int LOD=4;//Length Of (BASE's Digit-1)
	typedef int DIGIT;
	typedef deque<DIGIT> NumType;

private:
	NumType num;
	bool negtive;
private:
	void shrink()
	{
		while(num.size()>1 && num.back()== 0)
			num.pop_back();
		if (num.size()==0) 
		{
			num.push_back(0);
			negtive=false;
		}
		else if (num.size()==1 && num.front()==0)
		{
			negtive=false;
		}
	}
	static void SimplePlus(const LongNumber& a,const LongNumber& b,LongNumber& c); //simple==ignore negtive
	static LongNumber& SimplePlus(LongNumber& a,const LongNumber& b);//a+=b
	static void SimpleMinus(const LongNumber& a,const LongNumber& b,LongNumber& c);//simple==ignore negtive
	static LongNumber& SimpleMinus(LongNumber& a,const LongNumber& b);//a-=b
	static bool SimpleCompare(const LongNumber& a,const LongNumber& b);//simple==ignore negtive
	static void SimpleMul(LongNumber& a,DIGIT b);//a*=b;
	static LongNumber SimpleMul(const LongNumber& a,DIGIT b);//return a*b;
	static void SimpleMul(const LongNumber& a,const LongNumber& b,LongNumber& c);//c= a*b;
	//static void SimpleMul(LongNumber& a,const LongNumber& b);//a*=b

public:
	//constructors
	LongNumber():negtive(false) //default constructor :0
	{
		num.push_back(0);
	}
	LongNumber(const LongNumber& ln)//copy constructor
		:num(ln.num),negtive(ln.negtive)
	{
	}
	LongNumber(const string& str)//constructor from a string 
		:negtive(false)
	{

		DIGIT n=0;
		string::const_reverse_iterator it=str.rbegin();
		string s;

		while (it!=str.rend() && (*it<'0' || *it>'9')) ++it;//trimleft

		for (;it!=str.rend();++it)
		{
			if (*it<'0' || *it>'9') break;
			s.push_back(*it);
			if (s.length()>=LOD)
			{
				n=0;
				string::reverse_iterator sit;
				for (sit=s.rbegin();sit!=s.rend();++sit)
				{
					n=n*10+*sit-'0';
				}
				num.push_back(n);
				s.clear();
			}
		}
		if (s.length()>=0)
		{
			n=0;
			string::reverse_iterator sit;
			for (sit=s.rbegin();sit!=s.rend();++sit)
			{
				n=n*10+*sit-'0';
			}
			num.push_back(n);
		}
		for (;it!=str.rend();++it)
		{
			if (*it=='-') negtive=!negtive;
		}
		shrink();
	}
	LongNumber(int n) //from a number
	{
		negtive= (n<0);
		n=abs(n);
		do
		{
			num.push_back(n%BASE);
			n/=BASE;
		}
		while(n>0);
	}
public:
	//stream operator
	friend ostream& operator<<(ostream&,const LongNumber&);
	friend void swap(LongNumber& a,LongNumber& b);

	//+-*/ operator
	LongNumber operator+(const LongNumber& right) const
	{
		LongNumber c;
		if (!this->negtive && !right.negtive)
		{
			SimplePlus(*this,right,c);
			c.negtive=false;
		}
		else if (this->negtive && right.negtive)
		{
			SimplePlus(*this,right,c);
			c.negtive=true;
		}
		else if (!this->negtive && right.negtive)
		{
			SimpleMinus(*this,right,c);
			c.negtive=SimpleCompare(*this,right);
		}
		else
		{
			SimpleMinus(*this,right,c);
			c.negtive=!SimpleCompare(*this,right);
		}
		c.shrink();
		return LongNumber(c);

	}
	//operator -
	LongNumber operator-(const LongNumber& right)const
	{
		LongNumber c;
		if (!this->negtive && !right.negtive)
		{
			SimpleMinus(*this,right,c);
			c.negtive=SimpleCompare(*this,right);
		}
		else if (this->negtive && right.negtive)
		{
			SimpleMinus(*this,right,c);
			c.negtive=!SimpleCompare(*this,right);
		}
		else if (!this->negtive && right.negtive)
		{
			SimplePlus(*this,right,c);
			c.negtive=false;
		}
		else
		{
			SimplePlus(*this,right,c);
			c.negtive=true;
		}
		c.shrink();
		return LongNumber(c);
	}
	//operator *
	LongNumber operator*(const LongNumber& b) const
	{
		LongNumber c;
		c.negtive=b.negtive^this->negtive;
		SimpleMul(*this,b,c);
		return c;
	}
	LongNumber operator-()const // unary op
	{
		LongNumber c(*this);
		c.negtive=!c.negtive;
		return LongNumber(c);
	}
	//unary +-*/
	LongNumber& operator+=(const LongNumber& right)
	{
		if (this->negtive==right.negtive)
			SimplePlus(*this,right);
		else
		{
			SimpleMinus(*this,right);
			if (this->negtive==true)
				this->negtive=SimpleCompare(right,*this);
			else
				this->negtive=!SimpleCompare(right,*this);
		}
		shrink();
		return *this;
	}
	//compare operator
	friend bool operator<(const LongNumber& ,const LongNumber &);
	friend bool operator==(const LongNumber& ,const LongNumber &);
	bool operator<=(const LongNumber& b)const
	{
		return *this<b || *this==b;
	}
	bool operator>(const LongNumber& b)const
	{
		return !(*this<b);
	}
	bool operator>=(const LongNumber& b)const 
	{
		return *this>b || *this==b;
	}
	bool operator!=(const LongNumber& b)const
	{
		return !(*this==b);
	}

	//assign operator
	const LongNumber& operator=(const LongNumber& right)
	{
		if (*this==right) return *this;
		this->num.assign(right.num.begin(),right.num.end());
		this->negtive=right.negtive;
		return *this;
	}
};
void LongNumber::SimplePlus(const LongNumber& a,const LongNumber& b,LongNumber& c)
{

	c.num.clear();
	LongNumber::DIGIT count=0,n=0;
	LongNumber::NumType::const_iterator ait,bit;
	for (ait=a.num.begin(),bit=b.num.begin();ait!=a.num.end() && bit!=b.num.end();++ait,++bit)
	{
		n=*ait+*bit+count;
		count=n/LongNumber::BASE;
		n%=LongNumber::BASE;
		c.num.push_back(n);
	}
	for(;ait!=a.num.end();++ait)
	{
		n=*ait+count;
		count=n/LongNumber::BASE;
		n%=LongNumber::BASE;
		c.num.push_back(n);
	}
	for(;bit!=b.num.end();++bit)
	{
		n=*bit+count;
		count=n/LongNumber::BASE;
		n%=LongNumber::BASE;
		c.num.push_back(n);
	}
	if (count>0)
		c.num.push_back(count);
}
LongNumber& LongNumber::SimplePlus(LongNumber& a,const LongNumber& b)
{
	LongNumber::DIGIT count=0,n=0;
	LongNumber::NumType::iterator ait;
	LongNumber::NumType::const_iterator bit;
	for (ait=a.num.begin(),bit=b.num.begin();ait!=a.num.end() && bit!=b.num.end();++ait,++bit)
	{
		n=*ait+*bit+count;
		count=n/LongNumber::BASE;
		n%=LongNumber::BASE;
		*ait=n;
	}
	for(;ait!=a.num.end();++ait)
	{
		n=*ait+count;
		count=n/LongNumber::BASE;
		n%=LongNumber::BASE;
		*ait=n;
	}
	for(;bit!=b.num.end();++bit)
	{
		n=*bit+count;
		count=n/LongNumber::BASE;
		n%=LongNumber::BASE;
		a.num.push_back(n);
	}
	if (count>0)
		a.num.push_back(count);
	return a;
}
void LongNumber::SimpleMinus(const LongNumber& a,const LongNumber& b,LongNumber& c)//c=a-b
{
	if (SimpleCompare(a,b))
		return SimpleMinus(b,a,c);
	LongNumber::DIGIT n,count=0;
	LongNumber::NumType::const_iterator ait(a.num.begin()),bit(b.num.begin());
	c.num.clear();
	for (;bit!=b.num.end();++ait,++bit)
	{
		if (*ait-count<*bit)
		{
			n=*ait-*bit+LongNumber::BASE-count;
			count=1;
		}
		else
		{
			n=*ait-*bit-count;
			count=0;
		}
		c.num.push_back(n);
	}
	for (;ait!=a.num.end();++ait)
	{
		if (*ait-count<0)
		{
			n=*ait+LongNumber::BASE-count;
			count=1;
		}
		else
		{
			n=*ait-count;
			count=0;
		}
		c.num.push_back(n);
	}
	if (count>0)
	{
		n=LongNumber::BASE-count;
		c.num.push_back(n);
	}
}
LongNumber& LongNumber::SimpleMinus(LongNumber& a,const LongNumber& b)
{
	const LongNumber *pa=&a,*pb=&b;
	if (SimpleCompare(a,b))
	{
		pa=&b;
		pb=&a;

	}
	LongNumber::DIGIT n,count=0;
	LongNumber::NumType::const_iterator ait(pa->num.begin());
	LongNumber::NumType::const_iterator bit(pb->num.begin());
	LongNumber::NumType::iterator it(a.num.begin());
	for (;bit!=pb->num.end();++ait,++bit,++it)
	{
		if (*ait-count<*bit)
		{
			n=*ait-*bit+LongNumber::BASE-count;
			count=1;
		}
		else
		{
			n=*ait-*bit-count;
			count=0;
		}
		*it=n;
	}
	for (;ait!=pa->num.end();++ait,++it)
	{
		if (*ait-count<0)
		{
			n=*ait+LongNumber::BASE-count;
			count=1;
		}
		else
		{
			n=*ait-count;
			count=0;
		}
		*it=n;
	}
	if (count>0)
	{
		n=LongNumber::BASE-count;
		a.num.push_back(n);
	}

	return a;
}
bool LongNumber::SimpleCompare(const LongNumber& a,const LongNumber& b)
{
	if (a.num.size()<b.num.size()) return true;
	if (a.num.size()>b.num.size()) return false;
	LongNumber::NumType::const_reverse_iterator ait(a.num.rbegin()),bit(b.num.rbegin());
	for (;ait!=a.num.rend();++ait,++bit)
	{
		int aa=*ait,b=*bit;
		if (*ait<*bit) return true;
		if (*ait>*bit) return false;
	}

	return false;
}
void LongNumber::SimpleMul(LongNumber& a,DIGIT b)
{
	LongNumber::NumType& ad=a.num;
	DIGIT count=0;
	NumType::iterator it;
	for (it=ad.begin();it!=ad.end();++it)
	{
		*it=*it*b+count;
		count=*it/BASE;
		*it=*it%BASE;
	}
	if (count)
		ad.push_back(count);
}
void LongNumber::SimpleMul(const LongNumber& a,const LongNumber& b,LongNumber& c)
{
	if (a.num.size()<b.num.size())
		return SimpleMul(b,a,c);
	c=0;
	if (a==0 || b==0) return ;
	LongNumber temp;
	const NumType& bd=b.num;
	NumType::const_reverse_iterator bit;
	for (bit=bd.rbegin();bit!=bd.rend();++bit)
	{
        temp=SimpleMul(a,*bit);
		c+=temp;
		c.num.push_front(0);
	}
	c.num.pop_front();

}
LongNumber LongNumber::SimpleMul(const LongNumber& a,DIGIT b)
{
	LongNumber result(a);
	SimpleMul(result,b);
	return result;
}
inline bool operator<(const LongNumber& a,const LongNumber& b)
{
	if (a.negtive && !b.negtive) return true;
	if (!a.negtive && b.negtive) return false;
	if (a.negtive && b.negtive)
		return LongNumber::SimpleCompare(b,a);
	return LongNumber::SimpleCompare(a,b);
}
inline bool operator==(const LongNumber& a,const LongNumber& b)
{
	if(a.negtive!=b.negtive || a.num.size()!=b.num.size()) return false;
	return equal(a.num.begin(),a.num.end(),b.num.begin());
}

ostream& operator<<(ostream& os,const LongNumber &ln)
{
	if (ln.negtive) os<<'-';
	LongNumber::NumType::const_reverse_iterator it=ln.num.rbegin();
	os<<*it;
	++it;
	for (;it!=ln.num.rend();++it)
	{
		stringstream ss;
		ss<<*it;
		string str(ss.str());
		while(str.length()<ln.LOD)
		{
			str="0"+str;
		}
		os<<str;
	}
	return os;
}
void swap(LongNumber& a,LongNumber& b)
{
	swap(a.num,b.num);
	swap(a.negtive,b.negtive);
}