大数四则运算

快来打我* 2022-07-17 04:17 167阅读 0赞

.cpp
    #include"BigData.h"
    
    BigData::BigData(INT64 value)
    :_value(value)
    {
              INT64ToString(); //构造函数时将数字转换为字符串
    }
    
    BigData::BigData(const char* pData)//对大数进行处理.
    {
               //几种情况："     ","+123456","00001234","12345xyz","123456789";
               if (NULL == pData)  //如果是空
              {
                        assert(false );  //断言false，返回
                        return;
              }
               char* pStr = (char *)pData;
               char cSymbol = pData [0];//第一位
               if ('+' == cSymbol || '-' == cSymbol)
              {
                       pStr++;  //后移
              }
               else if (cSymbol >= '0' && cSymbol <= '9')
              {
                       cSymbol = '+';  //将符号位置为+
              }
               else
                        return;
               //处理"000000000000001234" 情况
               while ('0' == *pStr)
              {
                       pStr++;
              }
               //处理 带字母的情况
              _strData.resize(strlen( pData) + 1);//string中resize()函数改变本字符串的大小
              _strData[0] = cSymbol; //第一位存放符号位
              _value = 0;
               int icount = 1;
               while (*pStr >= '0' && *pStr <= '9')  //字母不处理，丢弃
              {
                       _value = 10 * _value + *pStr - '0';
                       _strData[icount++] = *pStr;
                       pStr++;
              }
              _strData.resize(icount); //将本字符串的大小调到icount
    
               if ('-' == cSymbol)   //负数
              {
                       _value = 0 - _value; //负值
              }
    }
    
    bool BigData ::IsINT64OverFlow()const//溢出判断
    {//64位中数字范围为：[-Ox8FFFFFFF FFFFFFFF，Ox7FFFFFFF FFFFFFFF]
              std:: string temp = "+9223372036854775807" ;
               if ('-' == _strData[0]) 
              {
                       temp = "-9223372036854775808";
              }
               //1.比较该大数与边界的size。2.相等时进行字符串直接比较
               if (_strData.size() < temp.size() || _strData.size() == temp.size() && _strData <= temp)
                        return true ;
               else
                        return false ;
    }
    void BigData ::INT64ToString()//将value转换为字符串
    {//append()在字符串的末尾添加num个字符ch-----basic_string &(append(size_t num,char ch))
               char cSymbol = '+' ;  //正号
               if (_value < 0)
              {
                       cSymbol = '-';
              }
               //12345->"54321"
               INT64 temp = _value;
              _strData.append(1, cSymbol);  //先添加符号位
               if (cSymbol == '-' )//负数转变成正数再模除
              {
                       temp = 0 - temp;
              }
               while (temp)
              {
                       _strData.append(1, temp % 10 + '0');
                       temp /= 10;
              }
               //"54321"->"12345" 
               char* pLeft = (char *)_strData.c_str() + 1;
               char* pRight = pLeft + _strData.size() - 2;//包含符号位，故减2
               while (pLeft < pRight)  //倒序交换
              {
                        char tmp = *pLeft;
                       *pLeft = *pRight;
                       *pRight = tmp;
                       pLeft++;
                       pRight--;
              }
    }
    
    //operator<<
    std::ostream& (operator<<(std:: ostream& _cout , const BigData& bigdata))//输出大数
    {//判断是否溢出，'+'不需要输出
               if (bigdata .IsINT64OverFlow())//没有溢出
              {
                        _cout << bigdata ._value << std::endl;
              }
               else
              { //c_str()函数返回一个指向正规C字符串的指针, 内容与本字符串相同
                        char* pData = (char *)bigdata._strData.c_str();
                        if ('+' == pData[0])
                                 pData++;
                        _cout << pData << std::endl;
              }
               return _cout ;
    }
    
    //operator+
    BigData BigData ::operator+(const BigData& bigdata )
    {
               //两个数都没溢出，结果也没溢出，直接进行相加
               if (IsINT64OverFlow() && bigdata .IsINT64OverFlow())
              {
                        //异号
                        if (_strData[0] != bigdata ._strData[0])
                       {
                                  return _value + bigdata ._value;
                       }
                        else  //同号
                       { //两个数同号，没溢出的情况：如果边界是10，则10-3=7>=6 8,-10-(-3)=-7=<-6 -8
                                  //正数时，最大值-value>=结果，才不会溢出
                                  //负数时，最大负数-value<=结果，才不会溢出
                                  if ((_value >= 0 && (MAX_INT64 - _value >= bigdata._value)) ||
                                          (_value < 0 && (MIN_INT64 - _value <= bigdata._value)))
                                 {
                                           return _value + bigdata ._value;
                                 }
                                  else //溢出->调用溢出加法
                                 {
                                           return BigData (Add(_strData, bigdata._strData).c_str());
                                 }
                       }
              }
               //两个数至少一个溢出，结果溢出
               if (_strData[0] == bigdata ._strData[0])  //同号
              {
                        return BigData (Add(_strData, bigdata._strData).c_str());
              }
               //异号
               else
              { //两个数异号a,b；b为正数需要换负号，b为负数需要换正号
                        //将b的符号进行转换，在调用大数减法
                        string _StrData = bigdata ._strData;//注意定义字符串
                        if (_StrData[0] == '+' )
                       {
                                 _StrData[0] = '-';
                       }
                        else
                       {
                                 _StrData[0] = '+';
                       }
                        return BigData (Sub(_strData, _StrData).c_str());
              }
    }
    //溢出加法
    std::string BigData::Add(std::string left, std:: string right )
    {
               int iLsize = left .size();  //size
               int iRsize = right .size();
               if (iLsize < iRsize)//选出大的长度给iLsize
              {
                       std::swap( left, right );
                       std::swap(iLsize, iRsize);
              }
              std:: string sRet;
              sRet.resize(iLsize + 1); //相加不会超过较大数的size+1
              sRet[0] = left[0];
               char Step = 0;//进位标识符
    
               //
               //模除得到每位的数字及进位Step
               for (int iIdx = 1; iIdx < iLsize; iIdx++)
              {
                        int cRet = left [iLsize - iIdx] + Step - '0';
                        if (iIdx < iRsize)
                       {
                                 cRet += right[iRsize - iIdx] - '0' ;//cRet转为数字：-‘0’
                       }
                       sRet[iLsize - iIdx + 1] = cRet % 10 + '0';//sRet比iLsize多一位,存放字符，故+‘0’
                       Step = cRet / 10;
              }
              sRet[1] = Step + '0'; //???
               return sRet;
    }
    
    BigData BigData ::operator-(const BigData& bigdata )
    {
               //两个数都没溢出，结果也没溢出，相减
               if (IsINT64OverFlow() && bigdata .IsINT64OverFlow())
              {
                        if (_strData[0] == bigdata ._strData[0])
                       {
                                  return _value - bigdata ._value;  //
                       }
                        else
                       {
                                  //两个数异号，相减没溢出
                                  //-10 + 3 = -7 <= -6(减式：3-(-6))；10+（-3）= 7 >= 6(减式：-3-(6))
                                  if (_value >= 0 && (MIN_INT64 + _value <= bigdata._value) ||
                                          _value < 0 && (MAX_INT64 + _value >= bigdata._value))
                                 {
                                           return _value + bigdata ._value;
                                 }
                                  else
                                 { //调用溢出加法
                                           BigData(Add(_strData, bigdata._strData).c_str());
                                 }
                       }
              }
               //两个数至少一个溢出，
               //同号调用减法
               if (_strData[0] == bigdata ._strData[0])
              {
                        return BigData (Sub(_strData, bigdata._strData).c_str());
              }
               else //异号调用加法
              {
                        return BigData (Add(_strData, bigdata._strData).c_str());
              }
              
    }
    
    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))//左边小于右边都进行交换
              { //-12-(-21)=9,21-34=-13发现两数的差与减数的相反
                       std::swap( left, right );
                       std::swap(iLsize, iRsize);
                        if (cSymbol == '-' )
                       {
                                 cSymbol = '+';
                       }
                        else
                       {
                                 cSymbol = '-';
                       }
              }
              std:: string sRet;
              sRet.resize(iLsize); //用大的长度进行开辟空间
              sRet[0] = cSymbol; //保存符号位
               for (int iIdx = 1; iIdx < iLsize; iIdx++)//结束标志为iLsize-1,不是iLsize
              {
                        //从低到高，取left每一位；
                        char cRet = left [iLsize - iIdx] - '0';
                        //在right范围内从低到高，取right每一位，然后相减；
                        if (iIdx < iRsize)
                       {
                                 cRet -= right[iRsize - iIdx] - '0' ;
                       }
                        //判断是否借位
                        if (cRet < 0)
                       {
                                  left[iLsize - iIdx - 1] -= 1; //上一位减一
                                 cRet += 10;  //
                       }
                       sRet[iLsize - iIdx] = cRet + '0';
              }
               return sRet;
    }
    
    BigData BigData ::operator*(const BigData& bigdata )
    {//无溢出
               if (IsINT64OverFlow() && bigdata .IsINT64OverFlow())
              {
                        if (_strData[0] == bigdata ._strData[0])//同号
                       {
                                  //例如:边界是10，10 / 2 = 5 > 4; 10 / -2 = -5 < -4;
                                  //结果不会溢出
                                  if (_value > 0 && MAX_INT64 / _value >= bigdata._value ||
                                          _value < 0 && MAX_INT64 / _value <= bigdata._value)
                                 {
                                           return _value*bigdata ._value;
                                 }
                       }
                        else //异号
                       {
                                  //例如:边界是-10，-10 / 2 = -5 < -4; -10 / -2 = 5 > 4;
                                  //不会溢出
                                  if (_value>0 && MIN_INT64 / _value <= bigdata._value ||
                                          _value < 0 && MIN_INT64 / _value >= bigdata._value)
                                 {
                                           return _value*bigdata ._value;
                                 }
                       }
              }
               //两数至少有一个溢出
               if (_value != 0 && bigdata ._value != 0)
              {
                        return BigData (Mul(_strData, bigdata._strData).c_str());
              }
    }
    //溢出乘法
    std::string BigData::Mul(std::string left, std:: string right )
    {
               int iLsize = left .size();
               int iRsize = right .size();
               char cSymbol = '+' ;//确认符号位
               if (left [0] != right[0])
              {
                       cSymbol = '-';
              }
               if (iLsize > iRsize)//使较小的数为left，提高效率。eg:99*12345678
              {
                       swap( left, right );
                       swap(iLsize, iRsize);
              }
              std:: string sRet;
               //两个数相乘最大位数为两个数位数的和，left和right中有符号位故减1
              sRet.assign(iLsize + iRsize - 1, '0');//assign()为字符串赋新值'0'
              sRet[0] = cSymbol;
               int iDataLen = iLsize + iRsize - 1;
               int ioffset = 0;//pian移位
               //先取左边一位和右边相乘；再考虑移位可得到左边每位与右边相乘的结果
               for (int iLdx = 1; iLdx < iLsize; iLdx++)
              {
                        char cLeft = left [iLsize - iLdx] - '0';
                        if (cLeft == 0)//如果left中含有0，偏移量加1
                       {
                                 ioffset++;
                                  continue;
                       }
                        char Step = 0;
                        //99*999=89910+8991;
                        for (int iRdx = 1; iRdx < iRsize; iRdx++)
                       {
                                  char cRet = cLeft * (right [iRsize - iRdx] - '0') + Step;
                                 cRet += sRet[iDataLen - iRdx - ioffset] - '0';//cRet存放当前最终乘加的结果
                                 sRet[iDataLen - iRdx - ioffset] = cRet % 10 + '0';//存放字符+'0'
                                 Step = cRet / 10;
                       }
                       sRet[iDataLen - iRsize - ioffset] += Step;
                       ioffset++;
              }
               return sRet;
    }
    
    
    BigData BigData ::operator/(const BigData& bigdata )
    {
               //1、除数为0
               if (bigdata ._strData[1] == '0')
              {
                        assert(false );
              }
               //2、两个数没溢出
               if (IsINT64OverFlow() && bigdata .IsINT64OverFlow())
              {
                        return _value / bigdata ._value;
              }
               //3、除数为1或-1
               if (bigdata ._value == 1 || bigdata._value == -1)
              {
                        return _value;
              }
               //4、除数和被除数相等
               //data()返回内容的字符数组形式
               if (strcmp(_strData.c_str() + 1, bigdata ._strData.c_str() + 1) == 0)
              {
                        if (_strData[0] != bigdata ._strData[0])
                       {
                                  return BigData (INT64(-1));
                       }
                        return BigData (INT64(1));
              }
               //除数大于被除数，返回0
               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));
              }
               //调用溢出除法
               return BigData (Div(_strData, bigdata._strData).c_str());
    }
    std::string BigData::Div(std::string left, std:: string right )
    {//此处用append()对字符串依次赋值
              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 DataLen = right .size() - 1;//标记相除的除数位数
               int Lsize = left .size() - 1;
               int Rsize = right .size() - 1;
               //eg:222222/33首先取到22和33比较大小，如果大就直接相除，否则DataLen++；
               for (int iIdx = 0; iIdx < Lsize;)
              {
                        if (!(IsLeftstrBig(pLeft, DataLen, pRight, Rsize)))//如果取到的数小于除数时，结果商0，向后再取一位
                       {
                                 sRet.append(1, '0');
                                 DataLen++;
                       }
                        else
                       {
                                 sRet.append(1, SubLoop(pLeft, DataLen, pRight, Rsize));//循环相减得到该位的商
                                  //判断pLeft中进行循环相减后依次去掉0，
                                  while (*pLeft == '0' && DataLen > 0)
                                 {
                                          pLeft++;
                                          DataLen--;
                                          iIdx++;
                                 }
                                 DataLen++;
                       }
                        if (DataLen > Rsize + 1)//pLeft比pRight大一位结果为0，则pLeft中含有0
                       {
                                 pLeft++;
                                 DataLen--;
                                 iIdx++;
                       }
                        if (DataLen + iIdx > Lsize)//判断是否除法结束
                                  break;
              }
               return sRet;
    }
    //循环相减
    char BigData ::SubLoop(char* pLeft, int Lsize, const char * pRight, int Rsize)
    {
               assert(pLeft && pRight);
               char cRet = 0;
               while (IsLeftstrBig(pLeft , Lsize, pRight, Rsize ))//直到被减数小于减数停止运算
              {
                        for (int iIdx = 0; iIdx < Rsize; iIdx++) //进行减运算
                       {
                                  char ret = pLeft [Lsize - iIdx - 1] - '0';
                                 ret -= pRight[Rsize - iIdx - 1] - '0';
                                  if (ret < 0)
                                 {
                                           pLeft[Lsize - iIdx - 2] -= 1;
                                          ret += 10;
                                 }
                                  pLeft[Lsize - iIdx - 1] = ret + '0';
                       }
                        while (*pLeft == '0'&& Lsize>0)
                       {
                                  pLeft++;
                                  Lsize--;
                       }
                       cRet++;
              }
               return cRet + '0' ;
    }
    
    //判断是否left大于right
    bool BigData ::IsLeftstrBig(const char* pLeft , int Lsize, const char * pRight, int Rsize)
    {
               assert(pLeft && pRight);
               char* pleft = (char *)pLeft;
               char* pright = (char *)pRight;
               if (Lsize > Rsize && *pleft > '0')//eg:112和33
              {
                        return true ;
              }
               else if (Lsize == Rsize)//eg:57和33
              {
                        while (pright)
                       {
                                  if (*pleft > *pright)
                                 {
                                           return true ;
                                 }
                                  else if (*pleft == *pright)
                                 {
                                          pleft++;
                                          pright++;
                                 }
                                  else
                                           return false ;
                       }
              }
               return false ;
    }
    
    .h
    #ifndef BIG_DATA_H
    #define BIG_DATA_H
    
    #include<iostream>
    using namespace std;
    #include<assert.h>
    #include<string>
    
    #define UN_INTT 0xCCCCCCCCCCCCCCCC
    #define MAX_INT64 0x7FFFFFFFFFFFFFFF
    #define MIN_INT64 0x8000000000000000
    
    typedef long long INT64;
    
    //内置类型
    class BigData
    {
    public:
              BigData( INT64 value);
              BigData( const char * pData);//对大数进行处理，优化
               friend std::ostream & (operator<<(std::ostream& _cout, const BigData& bigdata));//输出大数
    public:
               //大数的四则运算
               BigData operator+(const BigData& bigdata); //返回值不能传引用
               BigData operator-(const BigData& bigdata);
               BigData operator*(const BigData& bigdata);
               BigData operator/(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:
               bool IsINT64OverFlow()const ;//判断大数是否溢出
               void INT64ToString();//由于值在_value中，需将_value转化成string类型
               char SubLoop(char * pLeft, int Lsize, const char * pRight, int Rsize);//循环相减
               bool IsLeftstrBig(const char* pLeft, int Lsize, const char* pRight, int Rsize);//判断是否left大于right
    private:
              std:: string _strData;
               INT64 _value;
    };
    
    #endif
    
    
    test.cpp
    #define _CRT_SECURE_NO_WARNINGS 1
    
    
    #include<iostream>
    using namespace std;
    #include"BigData.h"
    
    
    void Test1()
    {
               //BigData b1(1234);
               //BigData b2("123456");
               //BigData b3("+1234567");
               //BigData b4("+1234567aaaa");
               //BigData b5("+");
               //BigData b6("     ");
               //BigData b7("-12345678");
               //BigData b8("-0000000012345aaa");
               //cout << b1 << endl;
               //cout << b2 << endl;
               //cout << b3 << endl;
               //cout << b4 << endl;
               //cout << b5 << endl;
               //cout << b6 << endl;
               //cout << b7 << endl;
               //cout << b8 << endl;
               //b3 = b2 + b1;
    }
    
    
    
    //test Add
    void Test2()
    {
               /*BigData left1(1234);
              BigData right1(4321);
              BigData ret = (left1 + right1);
              cout << ret << endl;*/
    
               /*BigData left2(9223372036854775807);
              BigData right2(2);
              BigData ret = (left2 + right2);
              cout << ret << endl;*/
    
               /*BigData left3(-9223372036854775807);
              cout << left3 << endl;
              BigData right3(-6);
              cout << right3 << endl;
              BigData ret = (left3 + right3);
              cout << ret << endl;*/
    
               /*BigData left2("999999999999999999999999999999");
              cout << left2 << endl;
              BigData right2("111111111111111111111111111111");
              cout << right2 << endl;
              BigData ret = (left2 + right2);
              cout << ret << endl;*/
    }
    
    void Test3()
    {
    
               /* BigData left2(1234);
              cout << left2 << endl;
              BigData right2(34);
              cout << right2 << endl;
              BigData ret = (left2 - right2);
              cout << ret << endl;*/
    
               /*BigData left2(9223372036854775807);
              cout << left2 << endl;
              BigData right2(-999);
              cout << right2 << endl;
              BigData ret = (left2 - right2);
              cout << ret << endl;*/
    
    
               /*BigData left2(9223372036854775807);
              cout << left2 << endl;
              BigData right2(999);
              cout << right2 << endl;
              BigData ret = (left2 - right2);
              cout << ret << endl;*/
    
               /*BigData left2(-9223372036854775807);
              cout << left2 << endl;
              BigData right2(-999);
              cout << right2 << endl;
              BigData ret = (left2 - right2);
              cout << ret << endl;*/
    
    
               BigData left2("1111111111111111111111111111111111111" );
              cout << left2 << endl;
               BigData right2("99" );
              cout << right2 << endl;
               BigData ret = (left2 - right2);
              cout << ret << endl;
    
    
               BigData left3(9223372036854775807);
              cout << left3 << endl;
               BigData right3("-999" );
              cout << right3 << endl;
               BigData ret3 = (left3 - right3);
              cout << ret3 << endl;
    
    
    }
    
    
    //test mul
    void Test4()
    {
               /*BigData left2("999");
              cout << left2 << endl;
              BigData right2("9999999999999999999999999999999999999999");
              cout << right2 << endl;
              BigData ret = (left2 * right2);
              cout << ret << endl;
              */
    
               /*BigData left2("-999");
              cout << left2 << endl;
              BigData right2("99999999999999");
              cout << right2 << endl;
              BigData ret = (left2 * right2);
              cout << ret << endl;*/
    
    }
    //Div
    void Test5()
    {
               /*BigData left1(1234);
              BigData right1(4321);
              BigData ret = (left1 / right1);
              cout << ret << endl;*/
    
               /*BigData left1(123456789);
              BigData right1(4321);
              BigData ret = (left1 / right1);
              cout << ret << endl;*/
    
               BigData left2("999999999999999999999999999999" );
               //cout << left2 << endl;
               BigData right2("111111111111111111111111111111" );
               //cout << right2 << endl;
               BigData ret = (left2 / right2);
              cout << ret << endl;
    
    }
    int main()
    {
    
               //Test1();
               //Test2();
               //Test3();
               //Test4();
              Test5();
              system( "pause");
               return 0;
    }