大数运算之字符串模拟

? 相信大家被特别大的两个数据做运算折磨过。当两个操作数或者运算结果超过类型的表示范围后会有意想不到的错误，这时候我们的电脑还不如我们高中用过的科学计算器，这是作为一个程序员所不能忍受的。所以我们得找到其他的方式来计算。这就是我们今天要讨论的字符串模拟大数运算。

?我们的运算一般使用int类型来算的，那么首先我们先复习一下各种int类型的数据表示范围：

unsigned?int?0～4294967295???
int???-2147483648～2147483647?
unsigned?long?0～4294967295
long???-2147483648～2147483647
long?long的最大值：9223372036854775807
long?long的最小值：-9223372036854775808
unsigned?long?long的最大值：1844674407370955161
__int64的最大值：9223372036854775807
__int64的最小值：-9223372036854775808
unsigned?__int64的最大值：18446744073709551615

可以看到，在64位操作系统下，long long int表示的最大范围是-9223372036854775808--9223372036854775807所以当我们的两个操作数或者运算结果超过这个范围我们就定义它已经溢出，得用字符串来模拟运算。所以我们得有一个_IsINT64OverFlow()函数，用来判断是否溢出：

bool?BigData::?_IsINT64OverFlow()const
{
	if?(_value?>=?Min_INT64?&&?_value?<=?Max_INT64)
		return?false;
	return?true;
}

? 我们是用字符串来模拟的，用一个类来封装大数运算的加减乘除这些功能，所以先设计一下BigData这个类的基本构架。

#ifndef?BIGDATA1_H
#define?BIGDATA1_H
#include<iostream>
#include<string>
#include<assert.h>
#define?Max_INT64?9223372036854775807
#define?Min_INT64?(-9223372036854775807-1)
//不能直接用-9223372036854775808，当编译器看到9223372036854775808时直接判定
//9223372036854775808>INT64_MAX,直接用unsigned?int64表示。当编译器看到负号时，
//直接对9223372036854775808取反，直接是它本身，编译器存不了那么大的数，报错
#define?INT64?long?long?int
using?namespace?std;

class?BigData
{
public:
	BigData(INT64?data);
	BigData(const?char?*str);
	BigData?operator+(BigData&?d);//加法
	BigData?operator-(BigData&?d);//减法
	BigData?operator*(BigData&?d);//乘法
	BigData?operator/(BigData&?d);//除法
private:
	friend?string?Add(string&?left,?string&?right);
	friend?string?Sub(string&?left,?string&?right);
	friend?string?Mul(string&?left,?string&?right);
	friend?string?Div(string&?left,?string&?right);
	bool?_IsINT64OverFlow()const;//判断数据是否溢出
	friend?ostream&?operator<<(ostream&?_cout,?const?BigData&?d);
	void?_INT64ToString();//将long?long?int数据转换成字符串
private:
	string?_strvalue;
	INT64?_value;
};

#endif

?这里有一个问题就是在用-9223372036854775807表示INT64_MIN时出现了一些问题；

? error C4146: 一元负运算符应用于无符号类型，结果仍为无符号类型。

那时候各种搞不懂，然后就查了一下各位大神的解释，大体意思就是不能直用-9223372036854775808表示。当编译器看到9223372036854775808时直接判定9223372036854775808>INT64_MAX,直接用unsigned int64表示。当编译器看到负号时，直接对9223372036854775808取反，直接是它本身，编译器存不了那么大的数，编译器就报错。详细解释见一元负运算符。

? 现在大体的框架已经搭好了。来看详细的实现过程：

（一）两个构造函数

BigData::BigData(INT64?data)
	:_value(data)
{
	_INT64ToString();
}
BigData::BigData(const?char?*str)
	:?_value(0)
{
	if?(str?==?NULL)
	{
		assert(false);
		return;
	}
	char?symbol;
	if?(str[0]?==?'+')
	{
		symbol?=?'+';
		str++;
	}
	else?if?(str[0]?==?'-')
	{
		symbol?=?'-';
		str++;
	}
	else?if?(str[0]?>=?'0'&&str[0]?<=?'9')
	{
		symbol?=?'+';
	}
	else
	{
		return;
	}
	char*?tmpstr?=?(char*)str;
	while?(*tmpstr?==?'0')//跳过前面的‘0’
		tmpstr++;
	int?i?=?0;//剩下字符串的长度
	while?(*tmpstr?>=?'0'&&?*tmpstr?<=?'9')
	{
		i++;
		_value?=?_value?*?10?+?*tmpstr?-?'0';
		tmpstr++;
	}
	if?(symbol?==?'-')
	{
		_value?=?0?-?_value;
	}
	_strvalue.resize(i?+?1);//相当于给_strvalue开辟空间
	_strvalue[0]?=?symbol;
	int?j?=?1;
	while?(i--)
	{
		_strvalue[j++]?=?*str++;
	}

}
void?BigData::_INT64ToString()
{
	INT64?tmp?=?_value;
	INT64?sym?=?tmp;
	string?str;
	if?(sym?>=?0)
	{
		str.push_back('+');
	}
	else
	{
		str.push_back('-');
		tmp?=?0?-?tmp;
	}
	while?(tmp)
	{
		char?ctmp?=?tmp?%?10?+?'0';
		str.push_back(ctmp);
		tmp?/=?10;
	}
	int?right?=?str.size()-1;
	int?left?=?1;
	while?(left?<?right)
	{
		swap(str[left++],?str[right--]);
	}
	_strvalue?=?str;
}

? 使用字符串构造比较麻烦，我们在构造_strvalue的时候还要把字符串数据转换为long long int类型的_value，方便以后计算，如果字符串表示的数据没有溢出的话直接用内置的long long int来计算。字符串转换为int的重点就是要从字符串的最后一个字符开始转化，每次循环数据乘以10。最后可以算出整个字符串的值，如果是负数，用0-_value即可。

? 还有long long int类型转换为字符串函数。算法不难，只是字符串的第一个字符统一保存数据的符号，方便以后好计算。

（编辑：黄山站长网）

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