大数类

虽然好多人写过了，但有段时间实在没事干，想着把以前写过基于string一个个bit计算的给改改。

基本功能都有，有一些简单测试，但不保证无bug

h文件:

#pragma once
#include <exception>
#include <string>
using namespace std;

class BiException : public std::exception
{
public:
	BiException(const char* msg)
		: exception(msg)
	{

	}

};

class BigInteger
{
	int m_bit[200];
	bool m_sig;
	int m_high;
	int m_base;
	int m_low;
	const static int max_number = 10000;
	friend struct SigTemp;
private:
	struct SigTemp 
	{
		SigTemp(const BigInteger& bi);
		~SigTemp();
		BigInteger* p;
	};
private:
	void set(__int64 n);
	bool set(const string& str);

	BigInteger abs_add(const BigInteger& bi) const;
	BigInteger abs_sub(const BigInteger& bi) const;

	BigInteger add(const BigInteger& bi) const;
	BigInteger sub(const BigInteger& bi) const;

	BigInteger& shift(int i);
	BigInteger mul(int n) const;
	BigInteger mul(const BigInteger& bi) const;

	int trydiv(const BigInteger& bi);
	BigInteger _div(const BigInteger& bi,bool mod,bool print = false) const;
	BigInteger div(const BigInteger& bi,bool print = false) const;

	BigInteger mod(const BigInteger& bi,bool print = false) const;

	int compare(const BigInteger& rhs) const;
	int abs_compare(const BigInteger& rhs) const;
public:
	int length() const { return m_high - m_low; }

public:
	BigInteger(__int64 n = 0);
	BigInteger(const string& str);

	BigInteger& operator = (__int64 n);
	BigInteger& operator = (const string& str);

	string tostring() const;
	BigInteger set_sig(bool minus = true) ;


	BigInteger& operator += (const BigInteger& rhs);
	BigInteger& operator -= (const BigInteger& rhs);
	BigInteger& operator *= (const BigInteger& rhs);
	BigInteger& operator /= (const BigInteger& rhs);
	BigInteger& operator %= (const BigInteger& rhs);
	BigInteger& operator -();

#define MARCO_OP(ret,op) friend ret operator op (const BigInteger& lhs,const BigInteger& rhs)

	MARCO_OP(BigInteger,+);
	MARCO_OP(BigInteger,-);
	MARCO_OP(BigInteger,*);
	MARCO_OP(BigInteger,/);
	MARCO_OP(BigInteger,%);

	MARCO_OP(bool,<);
	MARCO_OP(bool,<=);
	MARCO_OP(bool,>);
	MARCO_OP(bool,>=);
	MARCO_OP(bool,==);
	MARCO_OP(bool,!=);

#undef MARCO_OP

	
	friend ostream& operator <<(ostream& o,const BigInteger& bi);

	friend void test_biginteger();
};
inline BigInteger operator + (const BigInteger& lhs,const BigInteger& rhs)
{
	return lhs.add(rhs);
}
inline BigInteger operator - (const BigInteger& lhs,const BigInteger& rhs)
{
	return lhs.sub(rhs);
}
inline BigInteger operator * (const BigInteger& lhs,const BigInteger& rhs)
{
	return lhs.mul(rhs);
}
inline BigInteger operator / (const BigInteger& lhs,const BigInteger& rhs)
{
	return lhs.div(rhs);
}
inline BigInteger operator % (const BigInteger& lhs,const BigInteger& rhs)
{
	return lhs.mod(rhs);
}
inline ostream& operator <<(ostream& o,const BigInteger& bi)
{
	o<<bi.tostring();
	return o;
}
inline bool operator < (const BigInteger& lhs,const BigInteger& rhs)
{
	return lhs.compare(rhs) < 0;
}
inline bool operator <= (const BigInteger& lhs,const BigInteger& rhs)
{
	return lhs.compare(rhs) <= 0;
}
inline bool operator > (const BigInteger& lhs,const BigInteger& rhs)
{
	return lhs.compare(rhs) > 0;
}
inline bool operator >= (const BigInteger& lhs,const BigInteger& rhs)
{
	return lhs.compare(rhs) >= 0;
}
inline bool operator == (const BigInteger& lhs,const BigInteger& rhs)
{
	return lhs.compare(rhs) == 0;
}
inline bool operator != (const BigInteger& lhs,const BigInteger& rhs)
{
	return lhs.compare(rhs) != 0;
}
inline BigInteger makeint64(const BigInteger& high,const BigInteger& low)
{
	return (high * (BigInteger((__int64)1 << 32))) + low;
}

void test_biginteger();

cpp文件

#include "StdAfx.h"
#include "BigInteger.h"
#include <assert.h>

//////////////////////////////////////////////////////////////////////////

BigInteger::SigTemp::SigTemp(const BigInteger& bi)
	: p(NULL)
{
	if(bi.m_sig) return;

	p = const_cast<BigInteger*>(&bi);
	p->set_sig(false);
}
BigInteger::SigTemp::~SigTemp()
{
	if(p) p->set_sig(true);
}


//////////////////////////////////////////////////////////////////////////
BigInteger::BigInteger(__int64 n)
{			
	set(n);
}
BigInteger::BigInteger(const string& str)
{			
	set(str);
}
BigInteger& BigInteger::operator = (__int64 n)
{
	set(n);
	return *this;
}
BigInteger& BigInteger::operator = (const string& str)
{
	set(str);
	return *this;
}
string BigInteger::tostring() const
{
	string ret = m_sig ? "" : "-";
	char buf[8];
	for(int i = m_high - 1 ; i >= m_low ; -- i)
	{
		sprintf(buf,(i == m_high - 1)? "%d" : "%04d",m_bit[i]);
		ret += buf;
	}
	return ret.empty() ? "0" : ret;
}
BigInteger BigInteger::set_sig(bool minus) 
{ 
	m_sig = !minus;
	return *this;
}

BigInteger& BigInteger::operator += (const BigInteger& rhs)
{
	return (*this = add(rhs));
}

BigInteger& BigInteger::operator -= (const BigInteger& rhs)
{
	return (*this = sub(rhs));
}

BigInteger& BigInteger::operator *= (const BigInteger& rhs)
{
	return (*this = mul(rhs));
}

BigInteger& BigInteger::operator /= (const BigInteger& rhs)
{
	return (*this = div(rhs));
}

BigInteger& BigInteger::operator %= (const BigInteger& rhs)
{
	return (*this = mod(rhs));
}

BigInteger& BigInteger::operator -()
{
	m_sig = !m_sig;
	return *this;
}

void BigInteger::set(__int64 n)
{
	memset(this,sizeof(BigInteger));

	m_sig = n >= 0;

	m_low = m_high = m_base = 100;

	__int64 carry = n < 0 ? -n : n;
	int i = m_base;
	for( ; carry ; ++ i)
	{
		m_bit[i] = carry % (__int64)max_number;
		carry /= (__int64)max_number;
	}
	if(i > m_high) m_high = i;
}
bool BigInteger::set(const string& str)
{
	int len = str.length();
	if(len == 0) return false;

	memset(this,sizeof(BigInteger));
	m_low = m_high = m_base = 100;
	m_sig = (str[0] != '-');
	
	int low = m_sig ? 0 : 1,tmp = 0,bit = 1,i = m_base,j = len - 1;
	for( ; ; -- j)
	{
		if(!isdigit(str[j])) return false;

		tmp += bit * (str[j] - '0');
		bit *= 10;
		if(j == low) 
		{
			m_bit[i++] = tmp;
			break;
		}
		if(tmp > max_number / 10)
		{
			m_bit[i++] = tmp;
			bit = 1;
			tmp = 0;
		}
	}
	if(i > m_high) m_high = i;

	return true;
}
BigInteger BigInteger::abs_add(const BigInteger& bi) const
{
	if(bi.length() == 0) return *this;

	BigInteger result(*this);
	int i = result.m_low,j = bi.m_low,carry = 0,tmp = 0;
	do
	{
		tmp = carry + result.m_bit[i] + bi.m_bit[j];
		result.m_bit[i] = tmp % max_number;
		carry = tmp / max_number;

		++i,++j;
	}while(i < result.m_high || j < bi.m_high || carry);

	if(i > result.m_high) result.m_high = i;

	return result;
}
BigInteger BigInteger::abs_sub(const BigInteger& bi) const
{
	if(bi.length() == 0) return *this;

	BigInteger result(*this);

	int i = result.m_low,zerobit = result.m_low,nonzerobit = result.m_low;
	do
	{
		tmp = carry + result.m_bit[i] - bi.m_bit[j];
		carry = 0;
		if(tmp == 0)
		{
			zerobit = i;
		}
		else
		{
			nonzerobit = i;
			if(tmp < 0) 
			{
				tmp += max_number;
				carry = -1;
			}
		}
		result.m_bit[i] = tmp;
		++i,++j;
	}while((i < result.m_high && j < bi.m_high) || carry);

	if(i == result.m_high && zerobit > nonzerobit) 
		result.m_high = nonzerobit + 1;
	return result;
}
BigInteger BigInteger::add(const BigInteger& bi) const
{
	if(bi.length() == 0) return *this;

	if(m_sig != bi.m_sig)
	{
		BigInteger result;

		int ret = abs_compare(bi);
		if(ret == 0) return result;
		if(ret == -1) 
		{
			result = bi.sub(*this);
			if(m_sig) result.m_sig = false;

		}
		else
		{
			result = sub(bi);
			if(!m_sig) result.m_sig = false;
		}
		return result; 
	}
	return abs_add(bi);
}
BigInteger BigInteger::sub(const BigInteger& bi) const
{
	if(bi.length() == 0) return *this;

	if(m_sig) // +
	{
		// -
		if(!bi.m_sig) return abs_add(bi);

		// +
		int ret = abs_compare(bi);
		if(ret < 0) return bi.abs_sub(*this).set_sig();
		if(ret == 0) return 0;
		return abs_sub(bi);
	}

	// -
	// +
	if(bi.m_sig) return abs_add(bi);

	// -
	int ret = abs_compare(bi);
	if(ret < 0) return bi.abs_sub(*this).set_sig(false);
	if(ret == 0) return 0;
	return abs_sub(bi);
}
BigInteger& BigInteger::shift(int i)
{
	if(length() == 0) return *this;
	m_low -= i;
	return *this;
}
BigInteger BigInteger::mul(int n) const
{
	if(n == 0) return BigInteger(0);

	BigInteger result(*this);
	int i = result.m_base,tmp = 0;
	while((tmp = result.m_bit[i] * n + carry) || i < result.m_high) 
	{
		result.m_bit[i] = tmp % max_number;	
		carry = tmp / max_number;

		++i;
	}

	if(i > result.m_high) result.m_high = i;

	return result;
}
BigInteger BigInteger::mul(const BigInteger& bi) const
{
	BigInteger result;
	if(bi.m_high - bi.m_low == 0) return result;

	bool sig = !(m_sig ^ bi.m_sig);
	SigTemp o(bi);
	for(int i = bi.m_base ; i < bi.m_high ; ++ i)
	{
		result += (mul(bi.m_bit[i]).shift(i - bi.m_base));
	}
	result.m_sig = sig;
	return result;
}
int BigInteger::trydiv(const BigInteger& bi)
{
	assert(abs_compare(bi) >= 0);

	int l = 1,h = 9999,c = h - l + 1,comp = 0;
	while(c)
	{
		int c2 = c / 2;
		int mid = l + c2;
		comp = abs_compare(bi.mul(mid));
		if(comp < 0)
		{
			c = c2;
		}
		else if(comp > 0)
		{
			l = mid + 1;
			c = c2 - 1;
		}
		else
			return mid;
	}
	BigInteger tmp = bi.mul(l);
	int ret = abs_compare(tmp);
	if(ret > 0)
	{
		while(abs_compare(tmp += bi) >= 0 && ++ l);

		return l;
	}
	else
	{
		while(-- l && abs_compare(tmp -= bi) <= 0);

		return l;
	}
	return l;
}
BigInteger BigInteger::_div(const BigInteger& bi,bool print) const
{
	if(bi.abs_compare(0) == 0) throw BiException("Div by zero!");
	if(abs_compare(0) == 0) return BigInteger(0);

	int ret = abs_compare(bi);
	if(ret < 0) return BigInteger(0);
	if(ret == 0) return BigInteger(!(m_sig ^ bi.m_sig));

	bool sig = !(m_sig ^ bi.m_sig);
	SigTemp o(bi);

	BigInteger tmp,result;
	for(int i = m_high - 1 ; i >= m_base ; -- i)
	{
		tmp.shift(1) += m_bit[i];
		int ret = tmp.abs_compare(bi);
		if(ret == -1)
		{
			if(i != m_high - 1)
			{
				result.shift(1);
			}
			continue;
		}
		if(ret == 0)
		{
			result = result.shift(1).add(1);
			tmp.set(0);
		}
		else
		{
			int trydiv = tmp.trydiv(bi);
			if(print)
			{
				printf("%s trydiv %s,商 = %d",tmp.tostring().c_str(),bi.tostring().c_str(),trydiv);
			}
			result = result.shift(1).add(trydiv);
			tmp -= bi.mul(trydiv);
			if(print)
				printf("余数 = %sn",tmp.tostring().c_str());
		}
	}
	if(!mod)
		result.m_sig = sig;

	return mod ? tmp : result;
}
BigInteger BigInteger::div(const BigInteger& bi,bool print) const
{
	return _div(bi,false,print);
}

BigInteger BigInteger::mod(const BigInteger& bi,true,print);
}

int BigInteger::compare(const BigInteger& rhs) const
{
	if(m_sig != rhs.m_sig) return (int)m_sig - (int)rhs.m_sig;

	return abs_compare(rhs);
}
int BigInteger::abs_compare(const BigInteger& rhs) const
{
	int l1 = length(),l2 = rhs.length();
	if(l1 != l2) return l1 < l2 ? -1 : 1;

	for(int i = m_high - 1,j = rhs.m_high - 1 ; i >= m_low ; -- i,-- j)
	{
		if(m_bit[i] != rhs.m_bit[j]) 
			return m_bit[i] < rhs.m_bit[j] ? -1 : 1;
	}
	return 0;
}

//test
//////////////////////////////////////////////////////////////////////////
#define MAKE_INT64(h,l) (__int64)((l) | ((__int64)h << 32))

#include <iostream>
#include <time.h>
#include <windows.h>
using namespace std;

void test_biginteger()
{

#if 0
	BigInteger b1(-32889549839),b2(-9839);
	cout<<b2-b1<<endl;
	return;
#endif
	srand((unsigned int)time(0));
	BigInteger bi1,bi2,bi3,bi4;
	DWORD t = GetTickCount();
	for(int i = 0 ; i < 100000 ; ++ i)
	{			
		int l = rand(),h = rand();
		__int64 x = MAKE_INT64(h,l);

		bi1 = l,bi2 = h;
		bi3 = makeint64(h,l);

		if(!(bi3.compare(x) == 0))
			printf("errorn");

		l = rand(),h = rand();
		__int64 y = (__int64)l * (__int64)h;

		bi1 = l,bi2 = h;
		bi4 = bi1 * bi2;

		if(!(bi4.compare(y) == 0))
			printf("errorn");

		if(rand() & 1)
		{
			bi4.set_sig();
			y = -y;
		}
		if(rand() & 1)
		{
			bi3.set_sig();
			x = -x;
		}
		int t = 2;//rand() % 3;
		switch(t)
		{
		case 0:
			{
				if((bi4 + bi3).compare(x + y) != 0)
					printf("errorn");
			}
			break;
		case 1:
			{

				if((bi4 - bi3).compare(y - x) != 0)
					printf("errorn");

			}
			break;
		case 2:
			{
				if(bi4.compare(bi3) > 0)
				{
					if(x == 0) continue;
					if((bi4 / bi3).compare(y / x) != 0)
					{
						printf("errorn");
						bi4.div(bi3,true);
						cout<<bi4<<" / "<<bi3<<" : ";
						cout<<"shoule be "<< y/x<<",infact = "<<(bi4/bi3).tostring()<<endl;
						int a = 1;
					}
				}
				else
				{
					if(y == 0) continue;
					if((bi3 / bi4).compare(x / y) != 0)
					{
						printf("errorn");
						bi3.div(bi4,true);
						cout<<bi3<<" / "<<bi4<<" : ";
						cout<<"shoule be "<< x/y<<",infact = "<<(bi3/bi4).tostring()<<endl;
						int a = 1;
					}
				}
			}
			break;
		default:
			break;
		}

	}
	cout<<__FUNCTION__<<" cost "<<GetTickCount() - t<<" ms.n";
}