项目背景:
大数运算,顾名思义,就是很大的数值的数进行一系列的运算。
我们知道,在数学中,数值的大小是没有上限的,但是在计算机中,由于字长的限制,计算机所能表示的范围是有限的,当我们对比较小的数进行运算时,如: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" #includeBigData::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
#includeusing 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<<"结果: "< 下面是一个简单的测试:
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网站题目:C++实现大数运算-创新互联
文章地址:http://cdkjz.cn/article/gsepj.html