淺析《大數(shù)據(jù)運算》-加減乘除以及模除運算

WAY?

為什么會有大數(shù)據(jù)運算？緣由？

在c++中常用的數(shù)據(jù)類型有 char:1 bit,short 2 bit，int 4 bit，long long 8 bit等等，以上數(shù)據(jù)類型標識的數(shù)據(jù)大小非常有限，如果遇到大于他們能表示的范圍時，計算結(jié)果就會有誤，日常生活中的計算器也是如此，我國計算兩個比較大的數(shù)的運算，也會出現(xiàn)錯誤，或者不能正常顯示，

例如計算123456789123456789*987654321987654321

計算結(jié)果如下：

具體區(qū)別如下：

分析：

在數(shù)據(jù)運算中會出現(xiàn)兩種情況：一種是數(shù)據(jù)、且小計算結(jié)果不會溢出；另一種是數(shù)據(jù)溢出或者計算結(jié)果會溢出；

所以為了計算便捷，也為了節(jié)省運算量，我設(shè)置了如下兩種儲存數(shù)據(jù)方式，并且在計算也分情況不同而選擇不同方法，形式如下：

做了什么？

為了解決上述問題，我寫了一個計算大數(shù)據(jù)四則運算以及求模的小項目，實現(xiàn)的功能有 + - * / %；

主要的接口以及實現(xiàn)代碼如下：

程序頭文件以及接口如下：

/*
*
*  項目名稱：大數(shù)據(jù)運算
*  接口名稱：BigData.h
*  作    者: 鄒明
*  完成時間：2016.04.12
*
*/

#ifndef __BIG_DATA_H__
#define __BIG_DATA_H__

#include<iostream>
using namespace std;
#include<string.h>
#include<assert.h>

#define MAX_INT64 0x7FFFFFFFFFFFFFFF  //小數(shù)據(jù)能表示的最大值
#define MIN_INT64 0x8000000000000000   //小數(shù)據(jù)能表示的最小值

#define INIT 0xcccccccccccccccc

typedef long long INT64;
class BigData
{
public:
	BigData(INT64 value= INIT);
	BigData(const char*ptrData);

	//運算符重載
	BigData operator+(const BigData& bigdata);
	BigData operator-(const BigData& bigdata);
	BigData operator*(const BigData& bigdata);
	BigData operator/(const BigData& bigdata);
	BigData operator%(const BigData& bigdata);


private:
	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);
	std::string Mod(std::string left, std::string right);  //求模


	bool IsINT64OverFlow() const;  //判斷是否越界
	void INT64ToString();  //數(shù)據(jù)轉(zhuǎn)化為字符串
	bool IsLeftStrBig(const char *pLeft, int LSise, const char *pRight, int RSise);  //比較左操作數(shù)是否大于有操作數(shù)
	char SubLoop(char *pLeft, int LSise, const char *pRight, int RSise);   //除法時每次求商運算

	friend std::ostream&operator<<(std::ostream & cout, const BigData& bigdata);   //輸出運算符重載

private:
	INT64 _value;  //×××數(shù)據(jù)形式
	string _strData;  //字符串數(shù)據(jù)形式
};

#endif

實現(xiàn)代碼，文件名稱BigData.cpp，下面文件暈包含于此內(nèi)

構(gòu)造函數(shù)，轉(zhuǎn)化字符串，判斷越界，輸出運算符重載等函數(shù)

#include"BigData.h"

BigData::BigData(INT64 value)  //小數(shù)據(jù)構(gòu)造函數(shù)
	:_value(value)
{
	INT64ToString();
}

BigData::BigData(const char*ptrData)//大數(shù)據(jù)構(gòu)造函數(shù)
{
	//123456   //+1223356  //122334qwer   //qwee123   //0000qwer
	assert(ptrData);

	char *pstr = (char*)ptrData;
	char cSymbol = '+';
	if (('+' == *pstr) || ('-' == *pstr))
	{
		cSymbol = *pstr;
		pstr++;
	}
	else if (('0' <= *pstr)&&('9' >= *pstr))
	{
		cSymbol = '+';
	}
	else if (*pstr == ' ')
	{
		while (*pstr == ' ')
		{
			pstr++;
		}
		if (('+' == *pstr) || ('-' == *pstr))
		{
			cSymbol = *pstr;
			pstr++;
		}
		else if (('0' <= *pstr) && ('9' >= *pstr))
		{
			cSymbol = '+';
		}
	}
	else
	{
		return;
	}

	while (' ' == *pstr)
		pstr++;
	while ('0' == *pstr)
			pstr++;
	_strData.resize(strlen(ptrData)+1);
	_strData[0] = cSymbol;

	_value = 0;
	int iCount = 1;
	while ((*pstr >= '0') && (*pstr <= '9'))
	{
		_value = _value * 10 + (*pstr - '0');
		_strData[iCount] = *pstr;

		pstr++;
		iCount++;
	}
	_strData.resize(iCount);


	if (cSymbol == '-')
	{
		_value = 0 - _value;
	}

}

void BigData::INT64ToString()  //將數(shù)據(jù)的數(shù)值填充至字符串部分
{
	char cSymbl = '+';
	if (_value < 0)
	{
		cSymbl = '-';
	}
	//1234567
	//7654321
	_strData.append(1, cSymbl);
	INT64 temp = _value;
	if (temp < 0)
	{
		temp = 0 - temp;
	}
	while (temp)
	{
		_strData.append(1, temp % 10 + '0');
		temp /= 10;
	}
	char *pleft = (char*)_strData.c_str() + 1;
	char *pright = pleft + _strData.size() - 2;

	while (pleft < pright)
	{
		char tem = *pleft;
		*pleft = *pright;
		*pright = tem;
		pleft++;
		pright--;
	}

}

bool BigData::IsINT64OverFlow()const  //判斷是否越界
{
	std::string temp("+9223372036854775807");
	if ('-' == _strData[0])
	{
		temp = "-9223372036854775808";
	}
	if (_strData.size() < temp.size())
	{
		return true;
	}
	else if ((_strData.size() == temp.size()) && (_strData <= temp))
	{
		return true;
	}
	return false;
}

//求商
char BigData::SubLoop(char *pLeft, int LSize, const char *pRight, int RSize)
{
	assert(pLeft);
	assert(pRight);
	char cRet = '0';
	while (true)
	{
		while ((*pLeft == '0')&&LSize>0)
		{
			pLeft++;
			LSize--;
		}
		if (!IsLeftStrBig(pLeft, LSize, pRight, RSize))
		{
			break;
		}
		for (int i = 1;i<=LSize; i++)
		{
			if ((LSize > RSize) && (i  == LSize))
			{
				break;
			}
			char ret = pLeft[LSize - i];
			ret -= pRight[RSize - i];
			if (ret < 0)
			{
				pLeft[LSize - i - 1] -= 1;
				ret += 10;
			}
			pLeft[LSize - i] = ret+'0';

		}
		cRet++;
	}
	return cRet;
}

//判斷左操作數(shù)是否大于右操作數(shù)
bool BigData::IsLeftStrBig(const char *pLeft, int LSise, const char *pRight, int RSise)
{
	if (LSise > RSise ||
		((LSise == RSise) && (strcmp(pLeft, pRight) >= 0)))
	{
		return true;
	}
	return false;
}

//輸出運算符重載
std::ostream&operator<<(std::ostream & _cout, const BigData& bigdata)
{
	if (bigdata.IsINT64OverFlow())
	{
		_cout << bigdata._value;
	}
	else
	{
		char *pData = (char*)bigdata._strData.c_str();
		if ('+' == pData[0])
		{
			pData++;
		}
		_cout << pData;
	}
	return _cout;
}

加運算

BigData BigData::operator+(const  BigData& bigdata)  //+ 加法運算符重載
{
	if (IsINT64OverFlow() && bigdata.IsINT64OverFlow())
	{
		if (_strData[0] != bigdata._strData[0])
		{
			return BigData(_value + bigdata._value);
		}
		else
		{
			INT64 temp_max = MAX_INT64 - _value;
			INT64 temp_min = MIN_INT64 - _value;

			//10 -3 =7  5
			//(-10)-(-3)=-7  -5
			if (((_value >= 0) && (temp_max >= bigdata._value)) ||
				((_value < 0) && (temp_min <= bigdata._value)))
			{
				return BigData(_value + bigdata._value);
			}
		}
	}

	if (_strData[0] == bigdata._strData[0])
	{
		return BigData(Add(_strData, bigdata._strData).c_str());
	}
	else
	{
		if(_strData[0] == '+')
		{
			string ptr(bigdata._strData);
			ptr[0] = '+';
			return Sub(_strData, ptr).c_str();
		}
		else
		{
			string ptr(_strData);
			ptr[0] = '+';
			return Sub(bigdata._strData, ptr).c_str();
		}
	}
}

std::string BigData::Add(std::string left, std::string right)
{
	int iLsize = left.size();
	int iRsize = right.size();
	char cSymbol = left[0]; //取得符號位
	if (iLsize < iRsize)
	{
		std::swap(left, right);
		std::swap(iLsize, iRsize);
	}

	std::string sRet;
	sRet.resize(iLsize + 1);
  
	char Step = 0;
	for (int i = 1; i < iLsize; i++)
	{
		char cRet = left[iLsize - i] - '0' + Step;
		if (i < iRsize)
		{
			cRet += (right[iRsize - i] - '0');
		}
		sRet[iLsize - i + 1] = cRet % 10 + '0';
		Step = cRet / 10;
	}
	sRet[1] = Step + '0';
	sRet[0]=cSymbol;
	return sRet;
}

減運算：

BigData BigData::operator-(const BigData& bigdata)  //- 減法運算符重載
{
	if (IsINT64OverFlow() && bigdata.IsINT64OverFlow())
	{
		if (_strData[0] == bigdata._strData[0])
		{
			return BigData(_value - bigdata._value);
		}
		else
		{
			INT64 temp_max = _value - MAX_INT64;
			INT64 temp_min = _value - MIN_INT64;

			//10 -3 =7  5
			//(-10)-(-3)=-7  -5
			if (((_value >= 0) && (temp_max <= bigdata._value)) ||
				((_value < 0) && (temp_min >= bigdata._value)))
			{
				return BigData(_value - bigdata._value);
			}
		}
	}
	if (_strData[0] == bigdata._strData[0])
	{
		return BigData(Sub(_strData, bigdata._strData).c_str());
	}
	else
	{
		string ptr(bigdata._strData);
		ptr[0] = _strData[0];
		return Add(_strData, ptr).c_str();
	}

}

std::string BigData::Sub(std::string left, std::string right)
{
	int iLsize = left.size();
	int iRsize = right.size();
	int Max_size = iLsize;
	std::string sRet;
	char cSymbol = left[0];   //取符號位

	if (iLsize <= iRsize)
	{	
		if ((iLsize == iRsize) && (strcmp(left.c_str() ,right.c_str())<0) && (left[0] == right[0]))
		{
			if ('+' == right[0])
			{
				cSymbol = '-';
			}
			else
			{
				cSymbol = '+';
			}
			Max_size = iRsize;
			std::swap(left, right);
			std::swap(iLsize, iRsize);
		}
	}
	else
	{
		cSymbol = left[0];
		Max_size = iLsize;
	}


	char Step = 0;
	sRet.assign(Max_size, 48);
	for (int i = 1; i < Max_size; i++)
	{
		char cRet = 0;
		if (0<(iLsize - i))
		{
			cRet = left[iLsize - i] - '0' + Step;
		}
		if (i < iRsize)
		{
			if (cRet < right[iRsize - i] - '0')
			{
				cRet += 10;
			}
			Step = 0 - (cRet-Step) / 10;
			cRet -= (right[iRsize - i] - '0');
		}

		sRet[Max_size - i ] = cRet + '0';
	}

	sRet[0] = cSymbol;
	return sRet;
}

乘運算：

BigData BigData::operator*(const BigData& bigdata)
{
	if ((0 == _value)||(0==bigdata._value))
	{
		return BigData(INT64(0));
	}
	if (IsINT64OverFlow() && bigdata.IsINT64OverFlow())
	{
		if (_strData[0] == bigdata._strData[0])
		{
			if (((_value > 0) && ((long long)MAX_INT64 / _value >= bigdata._value)) ||
				((_value < 0) && ((long long)MAX_INT64 / _value <= bigdata._value)))   //同號相乘 結(jié)果為正
			{
				return BigData(_value*bigdata._value);
			}
		}
		else
		{
			if (((_value > 0) && ((long long)MIN_INT64 / _value <= bigdata._value)) ||
				((_value < 0) && ((long long)MIN_INT64 / _value >= bigdata._value)))      //異號相乘 結(jié)果為負
			{
				return BigData(_value*bigdata._value);
			}
		}
	}
	
	return BigData(Mul(_strData, bigdata._strData).c_str());
}

std::string BigData::Mul(std::string left, std::string right)
{
	char cSymbol = '+'; //設(shè)置符號位
	int iLsize = left.size();
	int iRsize = right.size();
	if (left[0] == right[0])
		cSymbol = '+';
	else
		cSymbol = '-';
	if (iLsize > iRsize)
	{
		std::swap(left, right);
		std::swap(iLsize, iRsize);
	}
	std::string sRet;
	int t = 1;
	if (((left[1] - '0')*(right[1] - '0') +(left[1] - '0')*(right[1] - '0')%10)<10)
	{
		t = 2;
	}
	else
		t = 1;
	//sRet.resize(iLsize + iRsize - t);
	sRet.assign(iLsize + iRsize - t,'0');
	int sizeRet = iLsize + iRsize - 1;
	sRet[0] = cSymbol;

	int i = 1, j = 1;
	for (i = 1, j = 1; i < iLsize; i++)
	{
		char step = 0;
		char cleft = left[iLsize - i] - '0';
		for (int j = 1; j < iRsize; j++)
		{
			char cRet = cleft*(right[iRsize - j] - '0') + step + (sRet[sizeRet - i - j + 1] - '0');
			step = cRet / 10;
			sRet[sizeRet - i - j + 1] = cRet%10 + '0';
			if ((j+1)==iRsize)
				sRet[sizeRet - i - j] = step+'0';
		}

	}
	return sRet;
}

除運算：

BigData BigData::operator/(const BigData& bigdata)
{
	if (bigdata._strData[1] == '0')
	{
		cout << "除數(shù)為 0 " << endl;
		assert(0);
	}
	if (_strData[1] == 0)
		return INT64(0);
	if ((IsINT64OverFlow()) && bigdata.IsINT64OverFlow())
	{
		return _value / bigdata._value;
	}
	if (_strData.size() < bigdata._strData.size())
	{
		return INT64(0);
	}
	else if (_strData.size() == bigdata._strData.size())
	{
		if (strcmp(_strData.c_str() + 1, bigdata._strData.c_str() + 1) < 0)
			return INT64(0);
		if (strcmp(_strData.c_str() + 1, bigdata._strData.c_str() + 1) == 0)
		{
			if (_strData[0] == bigdata._strData[0])
				return INT64(1);
			else
				return INT64(-1);
		}
	}
	return BigData(Div(_strData, bigdata._strData).c_str());
}

std::string BigData::Div(std::string left, std::string right)
{
	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;
	for (int i = 0; i < Lsize; i++)
	{
		if (!IsLeftStrBig(pLeft, DataLen, pRight, right.size()-1))
		{
			sRet.append(1, '0');
			DataLen++;
		}
		else
		{
			sRet.append(1, SubLoop(pLeft, DataLen, pRight, right.size() - 1));
		}

		if (DataLen + i>Lsize)
		{
			break;
		}

		if (*pLeft == '0')
		{
			pLeft++;
		}
		else
		{
			DataLen = right.size();
		}

	}		
	return sRet;
}

摸除運算：

BigData BigData:: operator%(const BigData& bigdata)
{
	if (bigdata._strData[1] == '0')
	{
		cout << "除數(shù)為 0 或?qū)?求模" << endl;
		assert(0);
	}
	if (_strData[1] == 0)
		return INT64(0);
	if ((IsINT64OverFlow()) && bigdata.IsINT64OverFlow())
	{
		return _value % bigdata._value;
	}
	if (_strData.size() < bigdata._strData.size())
	{
		return BigData(_strData.c_str());
	}
	else if (_strData.size() == bigdata._strData.size())
	{
		if (strcmp(_strData.c_str() + 1, bigdata._strData.c_str() + 1) < 0)
			return INT64(0);
		if (strcmp(_strData.c_str() + 1, bigdata._strData.c_str() + 1) == 0)
		{
				return INT64(0);
		}
	}
	return BigData(Mod(_strData, bigdata._strData).c_str());
}

std::string BigData::Mod(std::string left, std::string right)
{

	char cSymbol = left[0];
	BigData n1(left.c_str() + 1);
	BigData n2(right.c_str() + 1);
	BigData n3 = n1 / n2;
	BigData n4 = n3*n2;
	BigData sRet(n1 - n4);
	sRet._strData[0] = cSymbol;
	return sRet._strData;
}

測試用例，文件名test.cpp

#include"BigData.h"

void Test1()
{
	BigData n1(123456);

	BigData b2("12346678");
	BigData b3("+12346678");
	BigData b4("-123466");
	BigData b5("+");
	BigData b6("    ");
	BigData b7("12346aaaa");
	BigData b8("+asd12346678");
	BigData b9("000012346678");

	cout << "n1:" << n1 << endl;
	cout << "b2:" << b2 << endl;
	cout << "b3:" << b3 << endl;
	cout << "b4:" << b4 << endl;
	cout << "b5:" << b5 << endl;
	cout << "b6:" << b6 << endl;
	cout << "b7:" << b7 << endl;
	cout << "b8:" << b8 << endl;
	cout << "b9:" << b9 << endl;
}
void testAdd()
{
	BigData b1("-45353");
	BigData b2("37353753");
	BigData b3("-   9223372036854775808");
	BigData b4("     9223372036854775800");
	BigData b5("    -9223372036854775810");
	BigData b6("9223372036854775900");

	//1、都在INT64范圍內(nèi)
	cout << (b1 + b1) << endl;
	cout << (b2 + b2) << endl;
	cout << (b1 + b2) << endl;
	cout << "b4:" << b4 << endl;
	cout << (b1 + b4) << endl;

	cout << b3 << endl;
	cout << (b1 + b3) << endl;
	cout << (b2 + b4) << endl;

	//2、都不在INT64范圍內(nèi)
	cout << (b2 + b5) << endl;
	cout << (b1 + b6) << endl;
	cout << (b6 + b1) << endl;

}

void testSub()
{
	BigData b1("-45353");
	BigData b2("37353753");
	BigData b3("-9223372036854775808");
	BigData b4("9223372036854775800");
	BigData b5("-9223372036854775810");
	BigData b6("9223372036854775900");
	//1、都在INT64范圍內(nèi)
	cout << (b1 - b2) << endl;
	cout << (b2 - b1) << endl;
	cout << (b3 - b1) << endl;
	cout << (b1 - b4) << endl;
	cout << (b3 - b2) << endl;
	cout << (b4 - b1) << endl;
	cout << (b1 - b3) << endl;
	cout << (b2 - b4) << endl;
	cout << endl;

	//2、一個在一個不在<運算后在范圍內(nèi)，運算后不在范圍內(nèi)>

	cout << (b5 - b1) << endl;
	cout << (b1 - b5) << endl;
	cout << endl;
	cout << (b6 - b2) << endl;
	cout << (b2 - b6) << endl;
	cout << endl;
	cout << (b6 - b5) << endl;
	cout << (b5 - b6) << endl;
	cout << (b2 - b5) << endl;
	cout << (b1 - b6) << endl;
	cout << (b6 - b1) << endl;
}


void testMul()
{
	BigData b1("-45353");
	BigData b2("37353753");
	BigData b3("-9223372036854775808");
	BigData b4(" 9223372036854775800");
	BigData b5("-9223372036854775810");
	BigData b6(" 9223372036854775900");
	//1、都在INT64范圍內(nèi)
	cout << (BigData("999") * BigData("22222222222222222222222222222")) << endl;

	cout << (b2 * b1) << endl;
	cout << (b1 * b2) << endl;
	cout << (b1 * BigData("0")) << endl;
	cout << (BigData("0") * b2) << endl;
	cout << endl;
	cout << (b3 * b1) << endl;
	cout << (b1 * b3) << endl;
	cout << (b1 * b4) << endl;
	cout << (b4 * b1) << endl;
	cout << (b3 * b2) << endl;
	cout << (b2 * b4) << endl;
	cout << endl;

	//2、一個在一個不在<運算后在范圍內(nèi)，運算后不在范圍內(nèi)>

	cout << (BigData("0") * b6) << endl;
	cout << (b5 * BigData("0")) << endl;
	cout << (b5 * b1) << endl;
	cout << (b1* b5) << endl;
	cout << endl;
	cout << (b6 * b2) << endl;
	cout << (b2 * b6) << endl;
	cout << endl;
	cout << (b6 * b5) << endl;
	cout << (b5 * b6) << endl;
	cout << (b2 * b5) << endl;
	cout << endl;
	cout << (b1 * b6) << endl;
	cout << (b6 * b1) << endl;
}

void testDiv()
{
	BigData b1("-45353");
	BigData b2("37353753");
	BigData b3("-9223372036854775808");
	BigData b4(" 9223372036854775800");
	BigData b5("-9223372036854775810");
	BigData b6(" 9223372036854775900");
	BigData b7("-1231123203367738338252");


	//1、排除除數(shù)為0
	cout << (b1 / BigData(0)) << endl;

	//2、在范圍內(nèi)

	cout << (b1 / b2) << endl;
	cout << (b2 / b1) << endl;


	//3、不在范圍內(nèi)<左（被除數(shù)）比右（除數(shù)）小為0，左比右大>
	cout << (b2 / b5) << endl;
	cout << (b2 / b6) << endl;

	cout << (b5 / b2) << endl;
	cout << (b6 / b2) << endl;
	cout << (b6 / b1) << endl;
	cout << (b5 / b1) << endl;

	cout << b7 / b1 << endl;
}

void testMod()
{
	BigData b1("-45353");
	BigData b2("37353753");
	BigData b3("-9223372036854775808");
	BigData b4(" 9223372036854775800");
	BigData b5("-9223372036854775810");
	BigData b6(" 9223372036854775900");
	BigData b7("-1231123203367738338252");

	//1、排除除數(shù)為0
	cout << (b1 / BigData(0)) << endl;

	//2、在范圍內(nèi)

	cout << (b1 % b2) << endl;
	cout << (b2 % b1) << endl;


	//3、不在范圍內(nèi)
	cout << (b2 % b5) << endl;
	cout << (b2 % b6) << endl;

	cout << (b5 % b2) << endl;

	cout << (b6 % b2) << endl;
	cout << (b6 % b1) << endl;
	cout << (b5 % b1) << endl;

	cout << b7 % b1 << endl;
}


int main()
{
	//testAdd();  //測試+
	//testSub();   //測試-
	//testMul();   //測試 *
	//testDiv();   //測試 /
	testMod();     //測試%

	system("pause");
	return 0;
}

運行結(jié)果：

加運算：

減運算：

乘運算：

除運算：

模除運算：

以上代碼均為原創(chuàng)，實現(xiàn)了與小數(shù)據(jù)運算同樣的功能，如果發(fā)現(xiàn)錯誤，歡迎各位讀者批評指正，謝謝