项目背景：
创新互联建站为您提适合企业的网站设计 让您的网站在搜索引擎具有高度排名，让您的网站具备超强的网络竞争力！结合企业自身，进行网站设计及把握，最后结合企业文化和具体宗旨等，才能创作出一份性化解决方案。从网站策划到网站建设、成都网站制作， 我们的网页设计师为您提供的解决方案。
大数运算，顾名思义，就是很大的数值的数进行一系列的运算。
我们知道，在数学中，数值的大小是没有上限的，但是在计算机中，由于字长的限制，计算机所能表示的范围是有限的，当我们对比较小的数进行运算时，如：1234+5678，这样的数值并没有超出计算机的表示范围，所以可以运算。但是当我们在实际的应用中进行大量的数据处理时，会发现参与运算的数往往超过计算机的基本数据类型的表示范围，比如说，在天文学上，如果一个星球距离我们为100万光年，那么我们将其化简为公里，或者是米的时候，我们会发现这是一个很大的数。这样计算机将无法对其进行直接计算。
可能我们认为实际应用中的大数也不过就是几百位而已，实际上，在某些领域里，甚至可能出现几百万位的数据进行运算，这是我们很难想象的。如果没有计算机，那么计算效率可想而知。
由于编程语言提供的基本数值数据类型表示的数值范围有限，不能满足较大规模的高精度数值计算，因此需要利用其他方法实现高精度数值的计算，于是产生了大数运算。本项目实现了大数运算主要的加、减、乘除四种方法。
BigData.h
#ifndef BIG_DATA_H
#define BIG_DATA_H
#include
#define MAX_INT64 (INT64)0x7FFFFFFFFFFFFFFF
#define MIN_INT64 (INT64)0x8000000000000000 //如果不强转，系统会定义为unsigned INT64类型
#define UN_INIT 0xCCCCCCCCCCCCCCCC
typedef long long INT64;
class BigData
{
public:
BigData(INT64 value);
BigData(const char* pData);
public:
BigData operator+(const BigData& bigdata);
BigData operator-(const BigData& bigdata);
BigData operator*(const BigData& bigdata);
BigData operator/(const BigData& bigdata);
protected:
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);
protected:
bool IsINT64Overflow() const;
friend std::ostream& operator<<(std::ostream& _cout, const BigData& bigdata);
void INT64ToString();
bool IsLeftStrBig(const char* pLeft, int LSize, const char* pRight, int RSize);
char SubLoop(char* pLeft, int LSize, char* pRight, int RSize);
protected:
INT64 _value;
std::string _strData;
};
#endif
BigData.cpp
#include "BigData.h"
#include
BigData::BigData(INT64 value)
:_value(value)
{
INT64ToString(); //将_value中的值保存在_strData中
}
BigData::BigData(const char* pData)
{
//要处理的输入："12345678" "234567qwe" "+" " " "0000123456"
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;
//"0000123456"
int iDataLen = strlen(pData);
if (iDataLen > 1)
{
while ('0' == *pStr)
pStr++;
}
_strData.resize(strlen(pData)+1); //为_strData分配空间
_strData[0] = cSymbol; //第0位保存符号
//"123456qwe"
_value = 0;
int iCount = 1;
while (*pStr >= '0' && *pStr <= '9')
{
_value = _value*10 + (*pStr - '0');
_strData[iCount++] = *pStr;
pStr++;
}
_strData.resize(iCount);
if (cSymbol == '-')
_value = 0 - _value;
}
bool BigData::IsINT64Overflow() const
{
std::string temp("+9223372036854775807");
if (_strData[0] == '-')
temp = "-9223372036854775808";
if (_strData.size() < temp.size())
return false;
else if (_strData.size() == temp.size() && _strData <= temp)
return false;
return true;
}
void BigData::INT64ToString()
{
//处理符号位
char cSymbol = '+';
if (_value < 0)
cSymbol = '-';
INT64 temp = _value;
while (temp)
{
if (cSymbol == '+')
_strData.append(1, temp%10 + '0');
else
_strData.append(1, -(temp%10) + '0');
temp /= 10;
}
_strData.append(1, cSymbol);
std::reverse(_strData.begin(), _strData.end());
}
bool BigData::IsLeftStrBig(const char* pLeft, int LSize, const char* pRight, int RSize)
{
assert(pLeft != NULL && pRight != NULL);
if ((LSize > RSize) ||
(LSize == RSize && strcmp(pLeft, pRight) >= 0))
return true;
else
return false;
}
char BigData::SubLoop(char* pLeft, int LSize, char* pRight, int RSize)
{
assert(pLeft != NULL && pRight != NULL);
char cRet = '0';
while (true)
{
if (!IsLeftStrBig(pLeft, LSize, pRight, RSize))
break;
int iLIdx = LSize - 1;
int iRIdx = RSize - 1;
while (iLIdx >= 0 && iRIdx >= 0)
{
char ret = pLeft[iLIdx] - '0';
ret -= pRight[iRIdx] - '0';
if (ret < 0)
{
pLeft[iLIdx - 1] -= 1;
ret += 10;
}
pLeft[iLIdx] = ret + '0';
iLIdx--;
iRIdx--;
}
while (*pLeft == '0' && LSize > 0)
{
pLeft++;
LSize--;
}
cRet++;
}
return cRet;
}
std::ostream& operator<<(std::ostream& _cout, const BigData& bigdata)
{
if (!bigdata.IsINT64Overflow()) //_value没有溢出
{
_cout<= 0 && bigdata._value <= MAX_INT64 - _value) ||
(_value < 0 && bigdata._value >= MIN_INT64 - _value)) //相加后的和没有溢出
return BigData(_value + bigdata._value);
}
}
//两个数至少有一个溢出
//相加后的和溢出
if (_strData[0] == bigdata._strData[0]) //同号相加，调用加法
return BigData(Add(_strData, bigdata._strData).c_str());
else //异号相加，调用减法
return BigData(Sub(_strData, bigdata._strData).c_str());
}
BigData BigData::operator-(const BigData& bigdata)
{
if (!IsINT64Overflow() && !bigdata.IsINT64Overflow()) //两个数都没有溢出
{
if (_strData[0] == bigdata._strData[0])//同号
{
return BigData(_value - bigdata._value);
}
else //异号
{
if ((_value >= 0 && MAX_INT64 + bigdata._value >= _value) ||
(_value < 0 && MIN_INT64 + bigdata._value <= _value)) //结果没有溢出
return BigData(_value - bigdata._value);
}
}
//至少有一个数溢出或结果溢出
if (_strData[0] != bigdata._strData[0]) //异号相减，调用加法
return BigData(Add(_strData, bigdata._strData).c_str());
else //同号相减，调用减法
return BigData(Sub(_strData, bigdata._strData).c_str());
}
BigData BigData::operator*(const BigData& bigdata)
{
if (!IsINT64Overflow() && !bigdata.IsINT64Overflow()) //都没有溢出
{
if (_value == 0 || bigdata._value == 0)
{
return BigData((INT64)0);
}
if (_strData[0] == bigdata._strData[0]) //同号，积为正
{
if ((_value > 0 && MAX_INT64/_value >= bigdata._value) ||
(_value < 0 && MAX_INT64/_value <= bigdata._value)) //积没有溢出
{
return BigData(_value * bigdata._value);
}
}
else //异号,积为负
{
if ((_value > 0 && MIN_INT64/_value <= bigdata._value) ||
(_value < 0 && MIN_INT64/_value >= bigdata._value)) //积没有溢出
{
return BigData(_value * bigdata._value);
}
}
}
return BigData(Mul(_strData, bigdata._strData).c_str());
}
BigData BigData::operator/(const BigData& bigdata)
{
//除数不能为0
if ('0' == bigdata._strData[1])
assert(false);
// 都没溢出
if (!IsINT64Overflow() && !bigdata.IsINT64Overflow())
return BigData(_value / bigdata._value);
// 至少有一个溢出
//除数 == ±1
if (bigdata._strData == "+1" && bigdata._strData == "-1")
{
std::string strRet = _strData;
if (_strData[0] != bigdata._strData[0])
strRet[0] = '-';
return BigData(strRet.c_str());
}
//左 < 右
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));
//左 == 右
if (strcmp(_strData.c_str()+1, bigdata._strData.c_str()+1) == 0) //左==右
{
std::string strRet = "+1";
if (_strData[0] != bigdata._strData[0])
strRet[0] = '-';
else
return BigData(strRet.c_str());
}
//左 > 右
return BigData(Div(_strData, bigdata._strData).c_str());
}
std::string BigData::Add(std::string left, std::string right)
{
//让left保存位数大的数
int iLeftSize = left.size();
int iRightSize = right.size();
if (iLeftSize < iRightSize)
{
std::swap(left, right);
std::swap(iLeftSize, iRightSize);
}
//相加
std::string strRet;
strRet.resize(iLeftSize + 1);
strRet[0] = left[0]; //符号位
char Step = 0; //进位
for (int iIdx = 1; iIdx < iLeftSize; ++iIdx)
{
char cRet = left[iLeftSize - iIdx] - '0' + Step;
if (iIdx < iRightSize)
cRet += right[iRightSize - iIdx] - '0';
strRet[iLeftSize - iIdx + 1] = cRet % 10 + '0';
Step = cRet / 10;
}
strRet[1] = Step + '0';
return strRet;
}
std::string BigData::Sub(std::string left, std::string right)
{
int iLeftSize = left.size();
int iRightSize = right.size();
char cSymbol = left[0]; //差的符号位
if ((iLeftSize < iRightSize) ||
(iLeftSize == iRightSize && left < right))
{
std::swap(left, right);
std::swap(iLeftSize, iRightSize);
if (cSymbol == '+')
cSymbol = '-';
else
cSymbol = '+';
}
//相减
std::string strRet; //保存差
strRet.resize(left.size()); //先设置和左操作数一样大的空间
strRet[0] = cSymbol; //符号位
for (int Idx = 1; Idx < iLeftSize; ++Idx)
{
char cRet = left[iLeftSize - Idx] - '0';
if (Idx < iRightSize)
cRet -= (right[iRightSize - Idx] - '0');
if (cRet < 0) //有借位
{
left[iLeftSize - Idx - 1] -= 1;
cRet += 10;
}
strRet[iLeftSize - Idx] = cRet + '0';
}
return strRet;
}
std::string BigData::Mul(std::string left, std::string right)
{
//确定符号位
char cSymbol = '+';
if (left[0] != right[0])
cSymbol = '-';
//使左操作数位数小于右操作数位数
int iLeftSize = left.size();
int iRightSize = right.size();
if (iLeftSize > iRightSize)
{
std::swap(left, right);
std::swap(iLeftSize, iRightSize);
}
std::string strRet;
//strRet.resize(iLeftSize+iRightSize-1);
strRet.assign(iLeftSize+iRightSize-1, '0');
strRet[0] = cSymbol;
int iRetLen = strRet.size();
int iOffset = 0; //偏移
for (int iLeftIndex = 1; iLeftIndex < iLeftSize; ++iLeftIndex)
{
char cLeft = left[iLeftSize - iLeftIndex] - '0';
if (cLeft == 0) //当左操作数中有0时，直接左移，不计算
{
++iOffset;
continue;
}
char cStep = 0;
for (int iRightIndex = 1; iRightIndex < iRightSize; ++iRightIndex)
{
char cRet = cLeft*(right[iRightSize - iRightIndex] - '0') + cStep;
cRet += strRet[iRetLen - iRightIndex - iOffset] - '0';
strRet[iRetLen - iRightIndex - iOffset] = (cRet%10) + '0';
cStep = cRet/10;
}
strRet[iRetLen-iRightSize -iOffset] += cStep;
++iOffset;
}
return strRet;
}
std::string BigData::Div(std::string left, std::string right)
{
std::string strRet;
//确定符号位
strRet.append(1, '+');
if (left[0] != right[0])
strRet[0] = '-';
char* pLeft = (char*)(left.c_str()+1);
char* pRight = (char*)(right.c_str()+1);
int iLSize = left.size()-1; //被除数长度
int iDataLen = right.size()-1; //取iDataLen位被除数
int iIdx = 0; //iIdx和pLeft同步走,用来判断是否走到被除数结尾
while (iIdx < iLSize)
{
if (*pLeft == '0')
{
strRet.append(1, '0');
pLeft++;
iIdx++;
continue;
}
if (!IsLeftStrBig(pLeft, iDataLen, pRight, right.size()-1)) //取的iDataLen位被除数 < 除数
{
strRet.append(1, '0');
iDataLen++;
if (iDataLen + iIdx > iLSize)
break;
}
else
{
//循环相减
strRet.append(1, SubLoop(pLeft, iDataLen, pRight, right.size()-1));
while (*pLeft == '0')
{
pLeft++;
iIdx++;
iDataLen--;
}
iDataLen++;
}
}
return strRet;
}
BigDataTest.cpp
#include
using namespace std;
#include "BigData.h"
void AddTest()
{
//BigData b1("12345678");
//BigData b2("12345qwe");
//BigData b3("+");
//BigData b4("00001234");
//BigData b5(" ");
//BigData b6("99999999999999999999999999999999999999999999999999999999");
//BigData b7 ("-123213");
//cout<>input;
if (input == "quit")
{
break;
}
if (input.find('+') != -1)
{
string left = input.substr(0, input.find('+'));
string right = input.substr(input.find('+')+1, input.length()-1);
BigData bigdata1(left.c_str());
BigData bigdata2(right.c_str());
cout<<"结果： "<下面是一个简单的测试：
当前文章：C++实现大数运算
网站URL：http://bjjierui.cn/article/pjgggo.html
