小項目--大數運算

頭文件BigData.h：
#ifndef BIG_DATA_H
#define BIG_DATA_H

#include<string>

#define MAX_INT64 0x7FFFFFFFFFFFFFFF
#define MIN_INT64 0x8000000000000000

#define UN_INIT 0xCCCCCCCCCCCCCCCC

typedef long long INT64;

class BigData
{
public:
          BigData( INT64 value = 0xCCCCCCCCCCCCCCCC);
          BigData( const char * pData);

           BigData operator+(const BigData& bigdata);  //傳值方式
           BigData operator-(const BigData& bigdata);
           BigData operator*(const BigData& bigdata);
           BigData operator/(const BigData& bigdata);
private:
           bool IsINT64OverFlow()const ;
           void INT64ToString();
           bool IsLeftStrBig(const char* pLeft, int LSize, const char* pRight, int RSize);
           char SubLoop(char * pLeft, int LSize, const char * pRight, int RSize);

           friend std::ostream & operator<<(std::ostream& _cout, const BigData& bigdata);

          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);


private:
           INT64 _value;
          std:: string _strData;
};
#endif





源文件BigData.cpp:
#define _CRT_SECURE_NO_WARNINGS 1

#include "BigData.h"
#include <assert.h>
#include<string>

//構造函數
BigData::BigData(INT64 value)
    :_value(value)
{
          INT64ToString();
}

//拷貝構造函數
BigData::BigData(const char* pData)
{
           //參數檢測
           if (NULL == pData)
          {
                    assert(false );
                    return;
          }

           char cSombol = pData [0];
           char *pStr = (char *)pData;
           //檢查符號,"+","-"
           if ('+' == cSombol || '-' == cSombol)
          {
                   pStr++;
          }

           //檢查第一位字符位
           else if (cSombol >= '0'&&cSombol <= '9')
          {
                   cSombol = '+';
          }

           //處理全為空格，“      ”
           else
          {
                    return;
          }

           //消除0，“000012345”
           while (*pStr == '0' )
          {
                   pStr++;
          }

          _strData.resize(strlen( pData)+1);
          _strData[0] = cSombol;   //保存符號位
           //處理非法字符，“123456qwe”
          _value = 0;
           int iCount = 1;
           while (*pStr >= '0' && *pStr <= '9')
          {
                    //轉化步驟
                   _value = _value * 10 + (*pStr - '0');
                   _strData[iCount++] = *pStr;
                   pStr++;
          }
          _strData.resize(iCount);

           //處理負數
           if (cSombol == '-' )
          {
                   _value = 0 - _value;
          }
}

//大數加法
BigData BigData ::operator+(const BigData& bigdata )
{
           //左右操作數都沒有溢出，為內置類型
           if (IsINT64OverFlow() && bigdata .IsINT64OverFlow())
          {
                     //異號相加，+，-
                    if (_strData[0] != bigdata ._strData[0])
                   {
                              return BigData (_value + bigdata._value);
                   }
                    else   //同號相加
                   {
                              INT64 tmp = MIN_INT64 - _value;
                              if ((_value >= 0 && MAX_INT64 - _value >= bigdata._value)||
                                      (_value  < 0 && tmp/*MIN_INT64 - _value*/ <= bigdata._value))
                             {
                                       return BigData (_value + bigdata._value);
                             }
                   }
          }
           //至少有一個溢出或結果溢出
           if (_strData[0] == bigdata ._strData[0])
          {
                    return BigData (Add(_strData, bigdata._strData).c_str());
          }
           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());
          }
           return BigData (Sub(_strData, bigdata._strData).c_str());
}

//大數乘法
BigData BigData ::operator*(const BigData& bigdata )
{
           //除數不為0
           if (_value == 0 || bigdata ._value == 0)
          {
                    return BigData (INT64(0));
          }
           //沒有溢出
           if (IsINT64OverFlow() && bigdata .IsINT64OverFlow())
          {
                    //同號
                    if (_strData[0] == bigdata ._strData[0])
                   {
                              if ((_value>0 && MAX_INT64 / _value >= bigdata._value)||
                                      (_value<0 && MIN_INT64 / _value <= bigdata._value))
                             {
                                       return BigData (_value*bigdata._value);
                             }
                   }
                    //異號
                    else
                   {
                              if ((_value>0 && MAX_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 )
{
           //除數為零
           if (bigdata ._strData[1] == '0')
          {
                    assert(false );

          }
           //都沒溢出
           if (IsINT64OverFlow() && bigdata .IsINT64OverFlow())
          {
                    return BigData (_value / bigdata._value);
          }
           //被除數小于除數
           if (_strData.size() < bigdata ._strData.size()||                 //123    123445
                   (_strData.size() == bigdata._strData.size()&&                //2239   2234
                   strcmp(_strData.c_str()+1, bigdata._strData.c_str()+1)<0)) 
          {
                    return BigData (INT64(0));
          }
           //
           if (bigdata ._strData == "+1" || _strData == "-1")
          {
                   std:: string ret = _strData;
                    if (_strData[0] != bigdata ._strData[0])
                   {
                             ret[0] = '-';
                   }
                    return BigData (ret.c_str());
          }
           //數值相等
           if (strcmp(_strData.c_str() + 1, bigdata ._strData.c_str() + 1) == 0)
          {
                   std:: string ret = "+1" ;
                    if (_strData[0] != bigdata ._strData[0])
                   {
                             ret[0] = '-';
                   }
                    return BigData (ret.c_str());
          }
           return BigData (Div(_strData, bigdata._strData).c_str());
}

//字符串加法
std::string BigData::Add(std::string left, std:: string right )
{
           int iLSize = left .size();
           int iRSize = right .size();
           if (iLSize < iRSize)
          {
                   std::swap( left, right );  //長的放在左邊
                   std::swap(iLSize, iRSize);
          }
          std:: string sRet;
          sRet.resize(iLSize + 1);  //最高位可能有進位
          sRet[0] = left[0];
           char step = 0;     //記錄進位

           for (int iIdx = 1; iIdx < iLSize; iIdx++)
          {
                    char cRet = left [iLSize - iIdx] - '0' + step;
                    if (iIdx < iRSize)
                   {
                             cRet += ( right[iRSize - iIdx] - '0' );
                   }
                   sRet[iLSize - iIdx + 1] = cRet % 10 + '0';
                   step = cRet / 10;
          }

          sRet[1] = step + '0';   //最高位的進位
           return sRet;
}

//字符串減法
std::string BigData::Sub(std::string left, std:: string right )
{
           int iLSize = left .size();
           int iRSize = right .size();
           char cSymbol = left [0];
           if (iLSize < iRSize||
                   iLSize ==iRSize&&
                    left < right )
          {
                   std::swap( left, right ); 
                   std::swap(iLSize, iRSize);
                    if (cSymbol == '+' )
                   {
                             cSymbol = '-';
                   }
                    else
                   {
                             cSymbol = '+';
                   }
          }

          std:: string strRet;     //保存結果
          strRet.resize( left.size());
          strRet[0] = cSymbol;
           //從低往高，取left的每一位
           //從低往高，取right的每一位
           for (int Idx = 1; Idx < iLSize; Idx++)
          {
                    char cRet = left [iLSize - Idx] - '0';
                    if (Idx < iRSize)
                   {
                             cRet -= ( right[iRSize - Idx] - '0' );
                   }
                   
                    //判斷是否借位
                    if (cRet < 0)
                   {
                              left[iLSize - Idx - 1] -= 1;
                             cRet += 10;
                   }
                   strRet[iLSize - Idx] = cRet + '0';
          }
           return strRet;
}

//字符串乘法
std::string BigData::Mul(std::string left, std:: string right )
{
           //確定符號位
           char cSymbol = '+' ;
           if (left [0] != right[0])
          {
                   cSymbol = '-';
          }

           int iLSize = left .size();
           int iRSize = right .size();
           if (iLSize > iRSize)
          {
                   std::swap( left, right );
                   std::swap(iLSize, iRSize);
          }

          std:: string sRet;
          sRet.assign(iLSize + iRSize - 1, '0');
          sRet[0] = cSymbol;
           int iDataLen = sRet.size();
           int ioffset = 0;  //記錄偏移量

           //取左邊一位，與右邊的每一位相乘
           for (int iLIdx = 1; iLIdx < iLSize; ++iLIdx)
          {
                    char cLeft = left [iLSize - iLIdx] - '0';
                    char cStep = 0;
                    if (cLeft == 0)
                   {
                             ioffset++;
                              continue;
                   }

                    for (int iRIdx = 1; iRIdx < iRSize; ++iRIdx)
                   {
                              char cRet = cLeft*(right [iRSize - iRIdx] - '0') + cStep;
                             cRet += sRet[iDataLen - iRIdx - ioffset] - '0';
                             sRet[iDataLen - iRIdx - ioffset] = (cRet % 10) + '0';
                             cStep = cRet / 10;
                   }
                   sRet[iDataLen - iRSize - ioffset] += cStep;
                   ioffset++;
          }
           return sRet;
}

//字符串除法
std::string BigData::Div(std::string left, std:: string right )
{
          std:: 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 LSize = left .size() - 1;
           int DataLen = right .size() - 1;

           for (int iIdx = 0; iIdx < LSize;)
          {
                    //處理被除數中的0
                    if (*pLeft == '0' )
                   {
                             sRet.append(1, '0');
                             pLeft++;
                             iIdx++;
                              continue;
                   }

                    if (!IsLeftStrBig(pLeft, DataLen, pRight, right.size() - 1))
                   {
                             sRet.append(1, '0');
                             DataLen++;
                              if (DataLen + iIdx > LSize)
                             {
                                       break;
                             }
                   }
                    else
                   {
                             sRet.append(1, SubLoop(pLeft, DataLen, pRight, right.size() - 1));
                              while (*pLeft == '0' && DataLen > 0)
                             {
                                      pLeft++;
                                      iIdx++;
                                      DataLen--;
                             }
                             DataLen++;
                              if (DataLen + iIdx > LSize)
                             {
                                       break;
                             }
                   }
          }
           return sRet;
}

//判斷左邊的數大于右邊的數
bool BigData ::IsLeftStrBig(const char* pLeft , int LSize, const char * pRight, int RSize)
{
           if (LSize > RSize ||
                    LSize == RSize && strcmp(pLeft, pRight) >= 0)
          {
                    return true ;
          }
           return false ;
}

//循環相減
char BigData ::SubLoop(char* pLeft, int LSize, const char * pRight, int RSize)
{
           assert(pLeft != NULL && pRight != NULL );
           char cRet = '0' ;
           while (true )
          {
                    //左小于右
                    if (!IsLeftStrBig(pLeft , LSize, pRight, RSize ))
                   {
                              break;
                   }

                    int LDataLen = LSize - 1;
                    int RDataLen = RSize - 1;
                    //處理循環相減
                    while (LDataLen >= 0 && RDataLen >= 0)
                   {
                              char ret = pLeft [LDataLen] - '0';
                             ret -= pRight[RDataLen] - '0' ;
                              if (ret < 0)
                             {
                                       pLeft[LDataLen - 1] -= 1;
                                      ret += 10;
                             }
                              pLeft[LDataLen] = ret + '0' ;
                             LDataLen--;
                             RDataLen--;
                   }
                    //跳過相減產生的多余的0
                    while (*pLeft == '0' && LSize > 0)
                   {
                              pLeft++;
                              LSize--;
                   }
                   cRet++;
          }
           return cRet;
}


//檢查是否溢出
bool BigData ::IsINT64OverFlow() const
{
           //+9223372036854775807
           //-9223372036854775808
          std:: string tmp("+9223372036854775807" );
           if (_strData[0] == '-' )
          {
                   tmp = "-9223372036854775808";
          }
           if (_strData.size() < tmp.size())
          {
                    return true ;
          }
           else if ((_strData.size() == tmp.size()) && (_strData <= tmp))
          {
                    return true ;
          }
           return false ;
}

void BigData ::INT64ToString()
{
           //處理符號位
           INT64 tmp = _value;
           char cSymbol = '+' ;
           if (_value < 0)
          {
                   cSymbol = '-';
          }
          _strData.append(1, cSymbol);  //append  追加

           //轉化
           while (tmp)
          {
                    int c = tmp % 10;
                    if (c < 0)
                   {
                             c = 0 - c;
                   }
                   _strData.append(1, c + '0');
                   tmp /= 10;
          }
           char *pleft = (char *) _strData.c_str() + 1;
           char *pright = pleft + _strData.size() - 2;
           while (pleft < pright)
          {
                    char cTemp = *pleft;
                   *pleft++ = *pright;
                   *pright-- = cTemp;
          }
}

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

測試BigDataTest.cpp:
#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
using namespace std;
#include"BigData.h"

void test1()    //測試加法
{
           //BigData b1(23456);
           //BigData b2("23456");
           //BigData b3("+23456");
           //BigData b4("+23456dfg");
           //BigData b5("-23456");
           //BigData b6("       ");
           //BigData b7("000000023456");

           //cout << b1 << endl;
           //cout << b2 << endl;
           //cout << b3 << endl;
           //cout << b4 << endl;
           //cout << b5 << endl;
           //cout << b6 << endl;
           //cout << b7 << endl;

           /*BigData left(36789);
          BigData right(23761);
          cout << left + right << endl;*/


           /*BigData left(9223372036854775807);
          BigData right(2);
          cout << left + right << endl;*/

           /*BigData left1("-9223372036854775808");
          BigData right1("-3");
          cout << left1 + right1 << endl;*/

           BigData left("99999999999999999999999999999999" );
           BigData right("11111111111111111111111111111111" );
          cout << left + right << endl;
}

void test2()      //測試減法
{
           /*BigData left(56789);
          BigData right(25323);
          cout << left - right << endl;*/

           /*BigData left(9223372036854775807);
          BigData right(999);
          cout << left - right << endl;*/

           /*BigData left("111111111111111111111111111111111111111");
          BigData right("99");
          cout << left - right << endl;*/

           /*BigData left(9223372036854775807);
          BigData right(-999);
          cout << left - right << endl;*/
          
           /*BigData left("-9223372036854775808");
          BigData right("999");
          cout << left - right << endl;*/

           BigData left("-9223372036854775809" );
           BigData right("-999" );
          cout << left - right << endl;
}

void test3()     //測試乘法
{
           /*BigData left("99");
          BigData right("999999999999999999999999999999999");
          cout << left*right << endl;*/

           //BigData left(99999);
           //BigData right(99);
           //cout << left*right << endl;

           /*BigData left("99");
          BigData right("-999999999999999999999999999999999");
          cout << left*right << endl;*/

           BigData left(-99);
           BigData right(99999);
          cout << left*right << endl;
}

void test4()      //測試除法
{
           /*BigData left(99999);
          BigData right(99999);
          cout << left/right << endl;*/

           /*BigData left("222222222222222222222222222222");
          BigData right("33");
          cout << left / right << endl;*/

           /*BigData left(-999990000000000);
          BigData right(99999);
          cout << left / right << endl;*/

           BigData left(678789);
           BigData right(99999135547);
          cout << left / right << endl;
}

int main()
{
           //test1();
           //test2();
           //test3();
          test4();
          system( "pause");
           return 0;
}