bignumber.cpp

二分法求大整数相乘

#include "BigNumber.h"
#include <iostream.h>
#include <algorithm>

BigNumber::BigNumber(int max)
{
	nMaxLen = max;
	pNum = new char[max];
	nLength = 0;
}

BigNumber::BigNumber(const BigNumber& bn)
{
	nMaxLen = bn.nMaxLen;
	pNum = new char[nMaxLen];
	nLength = bn.nLength;

	int i = 0;
	while(i < nLength)
	{
		pNum[i] = bn.pNum[i];
		++i;
	}
}

BigNumber BigNumber::operator= (const BigNumber& bn)
{
	if(nMaxLen != bn.nMaxLen)
	{
		delete []pNum;
		nMaxLen = bn.nMaxLen;
		pNum = new char[nMaxLen];
	}
	nLength = bn.nLength;

	int i = 0;
	while(i < nLength)
	{
		pNum[i] = bn.pNum[i];
		++i;
	}

	return *this;
}

BigNumber BigNumber::operator<<(int n)
{
	BigNumber bn(nMaxLen);
	int i = 0;
	while(i < n)
	{
		bn.pNum[i] = '0';
		++i;
	}

	int j = 0;
	while(j < nLength)
	{
		bn.pNum[i] = pNum[j];
		++j;
		++i;
	}
	bn.nLength = nLength + n;
	return bn;
}

BigNumber BigNumber::operator>>(int n)
{
	BigNumber bn(nMaxLen);
	if(n > nLength)
	{	
		bn.nLength = 1;
		bn.pNum[0] = '0';
	}
	else
	{
		bn.nLength = nLength - n;
		int i,j;
		i = n,j = 0;
		while(i < nLength)
		{
			bn.pNum[j] = pNum[i];
			++i;
			++j;
		}
	}

	return bn;
}

char BigNumber::operator[](int n) const
{
	if(n >= nLength)
		return '0';
	else
		return pNum[n];
}

BigNumber BigNumber::operator+(const BigNumber& bn)
{
	BigNumber res(nMaxLen);
	int len = bn.nLength > nLength ? bn.nLength : nLength;
	int i,tmp,carry;
	carry = 0;
	for(i = 0;i < len;++i)
	{
		tmp = int((*this)[i] - '0' + bn[i] - '0') + carry;
		if(tmp >= 10)
		{
			tmp %= 10;
			carry = 1;
		}
		else
			carry = 0;
		res.pNum[res.nLength++] = char(tmp + '0');
	}
	if(carry == 1)
		res.pNum[res.nLength++] = '1';

	return res;
}

BigNumber BigNumber::operator-(const BigNumber& bn)
{
	BigNumber res(bn.nMaxLen);
	int len = (nLength > bn.nLength ? nLength : bn.nLength);
	
	int i,tmp,carry;
	carry = 0;
	for(i = 0;i < len;++i)
	{
		tmp = int((*this)[i] - bn[i] - carry);
		if(tmp < 0)
		{
			tmp += 10;
			carry = 1;
		}
		else
			carry = 0;
		res.pNum[res.nLength++] = char(tmp + '0');
	}
	if(res.IsZero())
		res.nLength = 1;
	else 
		res.RemoveZero();
	return res;
}

BigNumber BigNumber::operator*(BigNumber bn)
{
	BigNumber res(2*nMaxLen);
	int len = (nLength > bn.nLength ? nLength : bn.nLength);
	int rlen = 1;
	while(rlen < len)
		rlen <<= 1;
	len = rlen;

	if(len == 1)
	{
		if(IsZero()|| bn.IsZero())
		{
			res.pNum[0] = '0';
			res.nLength = 1;
		}
		else
		{
			int tmp = (pNum[0] - '0')*(bn[0] - '0');
			int low = tmp % 10;
			int high = tmp / 10;
			if(high != 0)
			{
				res.pNum[0] = char(low + '0');
				res.pNum[1] = char(high + '0');
				res.nLength = 2;
			}
			else
			{
				res.pNum[0] = char(low + '0');
				res.nLength = 1;
			}
		}
	}
	else
	{
		BigNumber a1 = (*this)>>(len>>1);
		BigNumber b1 = (*this) - (a1<<(len>>1));
		BigNumber a2 = bn>>(len>>1);
		BigNumber b2 = bn - (a2<<(len>>1));

		BigNumber a1a2 = a1 * a2;
		BigNumber b1b2 = b1 * b2;
		BigNumber abcd = (a1 + b1)*(a2 + b2) - a1a2 - b1b2;
		
		res = (a1a2<<len) + (((a1 + b1)*(a2 + b2) - a1a2 - b1b2)<<(len>>1)) + b1b2;
	}
	return res;
}
bool BigNumber::IsZero()
{
	int i = 0;
	while(i < nLength)
	{
		if(pNum[i] != '0')
			return false;
		++i;
	}
	return true;
}

void BigNumber::RemoveZero()
{
	while(pNum[nLength - 1] == '0')
			--nLength;
}

ostream& operator<< (ostream& out,BigNumber& bn)
{
	if(bn.IsZero())
	{
		bn.pNum[0] = '0';
		bn.nLength = 1;
	}
	else
		bn.RemoveZero();
	bn.pNum[bn.nLength] = '\0';
	std::reverse(bn.pNum,bn.pNum + bn.nLength);
	out << bn.pNum;
	std::reverse(bn.pNum,bn.pNum + bn.nLength);
	return out;
}

istream& operator>> (istream& in,BigNumber& bn)
{
	in >> bn.pNum;
	bn.nLength = strlen(bn.pNum);
	std::reverse(bn.pNum,bn.pNum + bn.nLength);
	return in;
}