實現大數四則運算

        由于編程語言提供的基本數值數據類型表示的數值范圍有限，不能滿足較大規模的高精度數值計算，因此需要利用其他方法實現高精度數值的計算，于是產生了大數運算。大數運算主要有加、減、乘三種方法。那么大數到底如何進行運算呢，學習過數據結構的都知道線性表，將大數拆分然后存儲在線性表中，不失為一個很好的辦法，下面通過字符串實現大數的構造及四則運算。

頭文件如下：

#ifndef BIG_DATA_H
#define BIG_DATA_H

#include<iostream>
using namespace std;
#include<assert.h>
#include<string>
 
#define UN_INTT 0xCCCCCCCCCCCCCCCC
#define MAX_INT64 0x7FFFFFFFFFFFFFFF
#define MIN_INT64 0x8000000000000000

typedef long long INT64;

//內置類型
class BigData
{
public:
    BigData(INT64 value);
	BigData(const char* pData);//對大數進行處理，優化
	friend std::ostream& (operator<<(std::ostream& _cout, const BigData& bigdata));//輸出大數
public:
	//大數的四則運算
	BigData operator+(const BigData& bigdata);//返回值不能傳引用
	BigData operator-(const BigData& bigdata);
	BigData operator*(const BigData& bigdata);
	BigData operator/(const BigData& bigdata);
	std::string Add(std::string left, std::string right);
	std::string Sub(std::string left, std::string right);
	std::string Mul(std::string left, std::string right);
	std::string Div(std::string left, std::string right);
private:
	bool IsINT64OverFlow()const;//判斷大數是否溢出
	void INT64ToString();//由于值在_value中，需將_value轉化成string類型
	char SubLoop(char* pLeft, int Lsize, const char* pRight, int Rsize);//循環相減
	bool IsLeftstrBig(const char* pLeft, int Lsize, const char* pRight, int Rsize);//判斷是否left大于right
private:
	std::string _strData;
	INT64 _value;
};

#endif

大數運算的構造函數，下面對類似以下情況進行處理：

"     ","+123456","00001234","12345xyz","123456789"

具體實現如下：

BigData::BigData(INT64 value)
      :_value(value)
{
	INT64ToString();//在構造函數時將數字轉化成字符串
}

BigData::BigData(const char* pData)//對大數進行處理，優化
{
	//幾種情況："     ","+123456","00001234","12345xyz","123456789";
	if (NULL == pData)
	{
		assert(false);
		return;
	}
	char* pStr = (char*)pData;
	char cSymbol = pData[0];//標志符號位
	if ('+' == cSymbol || '-' == cSymbol)
	{
		pStr++;
	}
	else if (cSymbol >= '0' && cSymbol <= '9')
	{
		cSymbol = '+';
	}
	else return;
	//"00001234"
	while ('0' == *pStr)
	{
		pStr++;
	}
	//"12345xyz"
	_strData.resize(strlen(pData) + 1);//string中resize()函數改變本字符串的大小
	_strData[0] = cSymbol;//第一位存放符號位
	_value = 0;
	int icount = 1;
	while (*pStr >= '0' && *pStr <= '9')
	{
		_value = 10 * _value + *pStr - '0';
		_strData[icount++] = *pStr;
		pStr++;
	}
	_strData.resize(icount);//將本字符串的大小調到icount
	if ('-' == cSymbol)
	{
		_value = 0 - _value;//負值
	}
}

bool BigData::IsINT64OverFlow()const//判斷大數是否溢出
{//64位中數字范圍為：[-Ox8FFFFFFF FFFFFFFF，Ox7FFFFFFF FFFFFFFF]
	std::string temp = "+9223372036854775807";
	if ('-' == _strData[0])
	{
		temp = "-9223372036854775808";
	}
	//比較該大數與邊界的size，相等時進行字符串直接比較
	if (_strData.size() < temp.size() || _strData.size() == temp.size() && _strData <= temp)
		return true;
	else
		return false;
}
void BigData::INT64ToString()//將_value轉化成string類型
{//append()在字符串的末尾添加num個字符ch-----basic_string &(append(size_t num,char ch))
	char cSymbol = '+';
	if (_value < 0)
	{
		cSymbol = '-';
	}
	//12345->"54321"
	INT64 temp = _value;
	_strData.append(1, cSymbol);
	if (cSymbol == '-')//負數轉變成正數再模除
	{
		temp = 0 - temp;
	}
	while (temp)
	{
		_strData.append(1, temp % 10 + '0');
		temp /= 10;
	}
	//"54321"->"12345"
	char* pLeft = (char*)_strData.c_str() + 1;
	char* pRight = pLeft + _strData.size() - 2;//包含符號位，故減2
	while (pLeft < pRight)
	{
		char tmp = *pLeft;
		*pLeft = *pRight;
		*pRight = tmp;
		pLeft++;
		pRight--;
	}
}

自主實現大數的輸出，代碼如下：

td::ostream& (operator<<(std::ostream& _cout, const BigData& bigdata))//輸出大數
{//判斷是否溢出，'+'不需要輸出
	if (bigdata.IsINT64OverFlow())//沒有溢出
	{
		_cout << bigdata._value << std::endl;
	}
	else
	{//c_str()函數返回一個指向正規C字符串的指針, 內容與本字符串相同
		char* pData = (char*)bigdata._strData.c_str();
		if ('+' == pData[0])
			pData++;
		_cout << pData << std::endl;
	}
	return _cout;
}

大數的加法運算：

BigData BigData::operator+(const BigData& bigdata)
{
	//兩個數都沒溢出，結果也沒溢出，直接進行相加
	if (IsINT64OverFlow() && bigdata.IsINT64OverFlow())
	{
		//兩個數一正一負
		if (_strData[0] != bigdata._strData[0])
		{
			return _value + bigdata._value;
		}
		else
		{//兩個數同號，沒溢出的情況：如果邊界是10，則10-3=7>=6 8,-10-(-3)=-7=<-6 -8
			if ((_value >= 0 && (MAX_INT64 - _value >= bigdata._value)) ||
				(_value < 0 && (MIN_INT64 - _value <= bigdata._value)))
			{
				return _value + bigdata._value;
			}
			else
			{
				return BigData(Add(_strData, bigdata._strData).c_str());
			}
		}
	}
	//兩個數至少一個溢出，結果溢出
	//同號
	if (_strData[0] == bigdata._strData[0])
	{
		return BigData(Add(_strData, bigdata._strData).c_str());//c._str(),size()
	}
	//異號
	else
	{//兩個數異號a,b；b為正數需要換負號，b為負數需要換正號
		string _StrData = bigdata._strData;//注意在此處定義字符串，不是BigData
		if (_StrData[0] == '+')
		{
			_StrData[0] = '-';
		}
		else
		{
			_StrData[0] = '+';
		}
		return BigData(Sub(_strData, _StrData).c_str());
	}
	return BigData(INT64(0));
}
std::string BigData::Add(std::string left, std::string right)
{
	int iLsize = left.size();
	int iRsize = right.size();
	if (iLsize < iRsize)//只需要左邊為長度長的即可
	{
		std::swap(left, right);
		std::swap(iLsize, iRsize);
	}
	std::string sRet;
	sRet.resize(iLsize + 1);//相加不會超過較大數的size+1
	sRet[0] = left[0];
	char Step = 0;//進位
	//通過模除得到每位的數字及進位Step
	for (int iIdx = 1; iIdx < iLsize;iIdx++)
	{
		int cRet = left[iLsize - iIdx] + Step - '0';
		if (iIdx < iRsize)
		{
			cRet += right[iRsize - iIdx] - '0';//cRet轉為數字，-‘0’
		}
		sRet[iLsize - iIdx + 1] = cRet % 10 + '0';//sRet比iLsize多一位,存放字符，故+‘0’
		Step = cRet / 10;
	}
	sRet[1] = Step + '0';
	return sRet;
}

大數的減法運算：

BigData BigData::operator-(const BigData& bigdata)
{
	//兩個數都沒溢出，結果也沒溢出，直接進行相加
	if (IsINT64OverFlow() && bigdata.IsINT64OverFlow())
	{
		if (_strData[0] == bigdata._strData[0])
		{
			return _value + bigdata._value;
		}
		else
		{
			//兩個數異號，相減沒溢出
			//-10 + 3 = -7 <= -6(減式：3-(-6))；10+（-3）= 7 >= 6(減式：-3-(6))
			if (_value >= 0 && (MIN_INT64 + _value <= bigdata._value) ||
				_value < 0 && (MAX_INT64 + _value >= bigdata._value))
			{
				return _value + bigdata._value;
			}
			else
			{//不用使bigdata._strData[0]設為'-',Add符號隨左邊數字即被減數(-9999-1 = -10000)
				BigData(Add(_strData, bigdata._strData).c_str());
			}
		}
	}
	//兩個數至少一個溢出，
	//同號調用減法
	if (_strData[0] == bigdata._strData[0])
	{
		return BigData(Sub(_strData, bigdata._strData).c_str());
	}
	else
	{
		return BigData(Add(_strData, bigdata._strData).c_str());
	}
	return BigData(INT64(0));
}
std::string BigData::Sub(std::string left, std::string right)
{
	int iLsize = left.size();
	int iRsize = right.size();
	char cSymbol = left[0];//保存所得差的符號位
	if (iLsize < iRsize || (iLsize==iRsize && left < right))//左邊小于右邊都進行交換
	{//-12-(-21)=9,21-34=-13發現兩數的差與減數的相反
		std::swap(left,right);
		std::swap(iLsize, iRsize);
		if (cSymbol == '-')
		{
			cSymbol = '+';
		}
		else
		{
			cSymbol = '-';
		}
	}
	std::string sRet;
	sRet.resize(iLsize);
	sRet[0] = cSymbol;//保存符號位
	for (int iIdx = 1; iIdx < iLsize; iIdx++)//結束標志為iLsize-1,不是iLsize
	{
		//從低到高，取left每一位；
		char cRet = left[iLsize - iIdx] - '0';
		//在right范圍內從低到高，取right每一位，然后相減；
		if (iIdx < iRsize)
		{
			cRet -= right[iRsize - iIdx] - '0';
		}
		//判斷是否借位
		if (cRet < 0)
		{
			left[iLsize - iIdx - 1] -= 1;
			cRet += 10;
		}
		sRet[iLsize - iIdx] = cRet + '0';
	}
	return sRet;
}

大數的乘法運算：

BigData BigData::operator*(const BigData& bigdata)
{
	if (IsINT64OverFlow() && bigdata.IsINT64OverFlow())
	{
		if (_strData[0] == bigdata._strData[0])
		{
		    //例如:邊界是10，10 / 2 = 5 > 4; 10 / -2 = -5 < -4;
			if (_value > 0 && MAX_INT64 / _value >= bigdata._value ||
				_value < 0 && MAX_INT64 / _value <= bigdata._value)
			{
				return _value*bigdata._value;
			}
		}
		else
		{
			//例如:邊界是-10，-10 / 2 = -5 < -4; -10 / -2 = 5 > 4;
			if (_value>0 && MIN_INT64 / _value <= bigdata._value ||
				_value < 0 && MIN_INT64 / _value >= bigdata._value)
			{
				return _value*bigdata._value;
			}
		}
	}
	//兩數至少有一個溢出
	if (_value != 0 && bigdata._value != 0)
	{
		return BigData(Mul(_strData, bigdata._strData).c_str());
	}
	return BigData(INT64(0));
}
std::string BigData::Mul(std::string left, std::string right)
{
	int iLsize = left.size();
	int iRsize = right.size();
	char cSymbol = '+';//確認符號位
	if (left[0] != right[0])
	{
		cSymbol = '-';
	}
	if (iLsize > iRsize)//使較小的數為left，提高效率。eg:99*12345678
	{
		swap(left, right);
		swap(iLsize, iRsize);
	}
	std::string sRet;
	//兩個數相乘最大位數為兩個數位數的和，left和right中有符號位故減1
	sRet.assign(iLsize + iRsize - 1, '0');//assign()為字符串賦新值'0'
	sRet[0] = cSymbol;
	int iDataLen = iLsize + iRsize - 1;
	int ioffset = 0;//移位
	//先取左邊一位和右邊相乘；再考慮移位可得到左邊每位與右邊相乘的結果
	for (int iLdx = 1; iLdx < iLsize; iLdx++)
	{
		char cLeft = left[iLsize - iLdx] - '0';
		if (cLeft == 0)//如果left中含有0，偏移量加1
		{
			ioffset++;
			continue;
		}
		char Step = 0;
		//99*999=89910+8991;
		for (int iRdx = 1; iRdx < iRsize; iRdx++)
		{
			char cRet = cLeft * (right[iRsize - iRdx] - '0') + Step;
			cRet += sRet[iDataLen - iRdx - ioffset] - '0';//cRet存放當前位最終乘加的結果
			sRet[iDataLen - iRdx - ioffset] = cRet % 10 + '0';//存放字符+'0'
			Step = cRet / 10;
		}
		sRet[iDataLen - iRsize - ioffset] += Step;
		ioffset++;
	}
	return sRet;
}

大數的除法運算：

BigData BigData::operator/(const BigData& bigdata)
{
	//1、除數為0
	if (bigdata._strData[1] == '0')
	{
		assert(false);
	}
	//2、兩個數沒溢出
	if (IsINT64OverFlow() && bigdata.IsINT64OverFlow())
	{
		return _value / bigdata._value;
	}
	//3、除數為1或-1
	if (bigdata._value == 1 || bigdata._value == -1)
	{
		return _value;
	}
	//4、除數和被除數相等
	//if (strcmp(_strData.data() + 1, bigdata._strData.data() + 1) == 0)
	//data()返回內容的字符數組形式
	if (strcmp(_strData.c_str() + 1, bigdata._strData.c_str() + 1) == 0)
	{
		if (_strData[0] != bigdata._strData[0])
		{
			return BigData(INT64(-1));
		}
		return BigData(INT64(1));
	}
	if (_strData.size() < bigdata._strData.size() ||
		_strData.size() == bigdata._strData.size() &&
		strcmp(_strData.c_str() + 1, bigdata._strData.c_str() + 1) < 0)
	{
		return BigData(INT64(0));
	}
	return BigData(Div(_strData, bigdata._strData).c_str());
}
std::string BigData::Div(std::string left, std::string right)
{//此處用append()對字符串依次賦值
	std::string sRet;
	sRet.append(1, '+');
	if (left[0] != right[0])
	{
		sRet[0] = '-';
	}
	char* pLeft = (char*)left.c_str() + 1;
	char* pRight = (char*)right.c_str() + 1;
	int DataLen = right.size() - 1;//標記相除的除數位數
	int Lsize = left.size() - 1;
	int Rsize = right.size() - 1;
	//eg:222222/33首先取到22和33比較大小，如果大就直接相除，否則DataLen++；
	for (int iIdx = 0; iIdx < Lsize;)
	{
		if (!(IsLeftstrBig(pLeft, DataLen, pRight, Rsize)))//如果取到的數小于除數時，結果商0，向后再取一位
		{
			sRet.append(1, '0');
			DataLen++;
		}
		else
		{
			sRet.append(1, SubLoop(pLeft, DataLen, pRight, Rsize));//循環相減得到該位的商
			//判斷pLeft中進行循環相減后依次去掉0，
			while (*pLeft == '0' && DataLen > 0)
			{
				pLeft++;
				DataLen--;
				iIdx++;
			}
			DataLen++;
		}
		if (DataLen > Rsize + 1)//pLeft比pRight大一位結果為0，則pLeft中含有0
		{
			pLeft++;
			DataLen--;
			iIdx++;
		}
		if (DataLen + iIdx > Lsize)//判斷是否除法結束
			break;
	}
	return sRet;
} 
char BigData::SubLoop(char* pLeft, int Lsize, const char* pRight, int Rsize)
{
	assert(pLeft && pRight);
	char cRet = 0;
	while (IsLeftstrBig(pLeft, Lsize, pRight, Rsize))//直到被減數小于減數停止運算
	{
		for (int iIdx = 0; iIdx < Rsize; iIdx++)//進行減運算
		{
			char ret = pLeft[Lsize - iIdx - 1] - '0';
			ret -= pRight[Rsize - iIdx - 1] - '0';
			if (ret < 0)
			{
				pLeft[Lsize - iIdx - 2] -= 1;
				ret += 10;
			}
			pLeft[Lsize - iIdx - 1] = ret + '0';
		}
		while (*pLeft == '0'&&Lsize>0)
		{
			pLeft++;
			Lsize--;
		}
		cRet++;
	}
	return cRet + '0';
}
bool BigData::IsLeftstrBig(const char* pLeft, int Lsize, const char* pRight, int Rsize)//判斷是否left大于right
{
	assert(pLeft && pRight);
	char* pleft = (char*)pLeft;
	char* pright = (char*)pRight;
	if (Lsize > Rsize && *pleft > '0')//eg:112和33
	{
		return true;
	}
	else if (Lsize == Rsize)//eg:57和33
	{
		while (pright)
		{
			if (*pleft > *pright)
			{
				return true;
			}
			else if (*pleft == *pright)
			{
				pleft++;
				pright++;
			}
			else
				return false;
		}
	}
	return false;
}