大数运算之字符串模拟

（二）加法

BigData?BigData::operator+(?BigData&?d)
{

	if?(!_IsINT64OverFlow()?&&?!d._IsINT64OverFlow()?
		&&?(_value?+?d._value)?<=?Max_INT64?&&?(_value?+?d._value)?>=?Min_INT64)
	{
		_value?+=?d._value;
	}
	else
	{
		OverflowFlag?=?true;
		_strvalue?=?Add(_strvalue,?d._strvalue);
	}
	return?*this;
}
string?Add(string&?left,?string&?right)
{
	if?(left[0]?!=?right[0])//符号不等
	{
		if?(left[0]?==?'+')
		{
			right[0]?=?'+';
			return?Sub(left,?right);
		}
		else
		{
			left[0]?=?'+';
			return?Sub(right,?left);
		}
	}
	else
	{
		int?lsize?=?left.size();
		int?rsize?=?right.size();
		if?(lsize?==?rsize)
		{
			int?carry?=?0;
			while?(--lsize?&&?--rsize)
			{
				char?tmp?=?left[lsize];
				left[lsize]?=?(left[lsize]?-?'0'?+?right[rsize]?-?'0')?%?10?+?carry?+?'0';
				carry?=?(tmp?-?'0'?+?right[rsize]?-?'0')?/?10;
			}
			if?(carry?==?1)
			{
				left.insert(1,?"1");
			}
			return?left;
		}
		else
		{
			if?(lsize?>?rsize)
			{
				int?carry?=?0;//进位
				while?(--lsize?&&?--rsize)//不能为--rsize&&-lsize
				{
					char?tmp?=?left[lsize];
					left[lsize]?=?(left[lsize]?-?'0'?+?right[rsize]?-?'0')?%?10?+?carry?+?'0';
					carry?=?(tmp?-?'0'?+?right[rsize]?-?'0')?/?10;
				}
				while?(carry?==?1)
				{
					left[lsize]?=?left[lsize]?+?carry;
					carry?=?(left[lsize]?-?'0'?+?carry)?/?10;
					lsize--;
				}
				
				return?left;
			}
			else
			{
				int?carry?=?0;
				while?(--rsize?&&?--lsize)//注意不能为--lsize&&--rsize，
					//当lsize为1时不执行--lsize直接跳出
				{
					char?tmp?=?right[rsize];
					right[rsize]?=?(left[lsize]?-?'0'?+?right[rsize]?-?'0')?%?10?
						+?'0'?+?carry;
					carry?=?(tmp?-?'0'?+?left[lsize]?-?'0')?/?10;
				}
				while?(carry?==?1)//当进位为1就一直往前加进位
				{
					right[rsize]?=?right[rsize]?+?carry;
					carry?=?(right[rsize]?-?'0'?+?carry)?/?10;
					rsize--;
				}
				return?right;
			}
			
		}
	}
}

? 加减乘除法都是用+-*/的重载来实现，实现时自己写的ADD，SUB，MUL，DIV。+调用ADD，-调用SUB，*调用MUL，/调用DIV。以后+-*/的重载函数我就不贴出来了，换个调用函数就行。这样的话方便以后的相互调用，只需要修改一下符号位。因为乘法是用加法模拟的，除法使用减法模拟的，减法用加法模拟的，按理来说我们使用加法就可以实现所有的运算。但是那个效率真的是惨不忍睹。

?在这里，ADD的算法核心就是要保存低位向高位的进位。和我们手算是一样的。从两个字符串的最后一位开始往前相加，直到有一个字符串遇到_strvalue[0]的字符位为止，最后还要记得把最后的进位加上。在这里要考虑被加数加上进位以后还有进位的情况，所以在这我们使用了while来循环加。不用担心字符串的空间不够，因为两个位数一样的数相加，最多进位为1.

（三）减法

string?Sub(string&?left,?string&?right)
{
	if?(left[0]?!=?right[0])
	{
		if?(left[0]?==?'+')
		{
			right[0]?=?'+';
			return?Add(left,?right);
		}
		else
		{
			right[0]?=?'-';
			return?Add(left,?right);
		}
	}
	else
	{
		int?lsize?=?left.size();
		int?rsize?=?right.size();
		if?(lsize?==?rsize)
		{
			int?borrow?=0;
			while?(--lsize?&&?--rsize)
			{
				
				if?(left[lsize]?<?right[rsize])
				{
					left[lsize]?=?left[lsize]?+?10?-?right[rsize]?-?borrow?+?'0';
					borrow?=?1;
				}
				else
				{
					left[lsize]?=?left[lsize]?-?right[rsize]?-?borrow?+?'0';
					borrow?=?0;
				}
			}
			return?left;
		}
		else?if?(lsize?>?rsize)
		{
			int?borrow?=?0;
			while?(--lsize?&&?--rsize)
			{
				if?(left[lsize]?<?right[rsize])
				{
					left[lsize]?=?left[lsize]?+?10?-?right[rsize]?-?borrow?+?'0';
					borrow?=?1;
				}
				else
				{
					left[lsize]?=?left[lsize]?-?right[rsize]?-?borrow?+?'0';
					borrow?=?0;
				}
			}
			while?(?borrow==1?)
			{
				if?(left[lsize]?==?'0')
				{
					left[lsize]?=?left[lsize]?-?'0'?+?10?-?borrow?+?'0';//若借位为0，
					//向更高位借位,eg:1000-10
					lsize--;
				}
				else
				{
					left[lsize]?=?left[lsize]?-?'0'?-?borrow?+?'0';
					borrow?=?0;
				}

			}
			
			return?left;
		}
		else
		{
			int?borrow?=?0;
			while?(--rsize?&&?--lsize)
				//得先让rsize--，若--lsize为0；将不会执行--rsize;
			{
				if?(right[rsize]?<?left[lsize])
				{
					right[rsize]?=?right[rsize]?+?10?-?left[lsize]?-?borrow?+?'0';
					borrow?=?1;
				}
				else
				{
					right[rsize]?=?right[rsize]?-?left[lsize]?-?borrow?+?'0';
					borrow?=?0;
				}
			}
			while?(borrow?==?1)
			{
				if?(right[rsize]?==?'0')
				{
					right[rsize]?=?right[rsize]?-?'0'?+?10?-?borrow?+?'0';//若借位为0，
					//向更高位借位,eg:1000-10
					rsize--;
				}
				else
				{
					right[rsize]?=?right[rsize]?-?'0'?-?borrow?+?'0';
					borrow?=?0;
				}

			}
			return?right;
		}
	}
}

? 减法的算法核心和加法差不多，每次从两个字符串的最后一位开始计算。要定义一个借位，低位向高位的借位。只要借位borrow为1就一直循环借位。

加法和减法之间可以相互调用，当一个正数加一个负数时就可以调用减法，会很方便，而且易懂。这里就体现了我们封装ADD,SUB,MUL,DIV的好处。

?还有要注意的就是要用最大的字符串（最长的字符串)来减小的字符串。这样可以保证结果用最长的字符串就可以保存，不用考虑空间的问题。

（编辑：晋中站长网）

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