实现大数四则运算

副标题#e#

? ? ? ? 由于编程语言提供的基本数值数据类型表示的数值范围有限，不能满足较大规模的高精度数值计算，因此需要利用其他方法实现高精度数值的计算，于是产生了大数运算。大数运算主要有加、减、乘三种方法。那么大数到底如何进行运算呢，学习过数据结构的都知道线性表，将大数拆分然后存储在线性表中，不失为一个很好的办法，下面通过字符串实现大数的构造及四则运算。

头文件如下：

#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?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)//对大数进行处理，优化
{
	//几种情况："?????","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;
}

#p#副标题#e##p#分页标题#e#

大数的减法运算：

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;
}

#p#副标题#e##p#分页标题#e#

大数的除法运算：

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,?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?Rsize)
{
	assert(pLeft?&&?pRight);
	char?cRet?=?0;
	while?(IsLeftstrBig(pLeft,?Lsize,?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?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;
}