实现大数四则运算

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

头文件如下：

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

（编辑：大连站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!