大数运算

一、为什么要有大数运算
在C/C++编程语言中，整型的最大存储类型是long long类型，大小是8个字节，一但超出这个范围，则就无法用编程语言的内置类型存储。因为编程语言的存储范围有限，所以它不能满足较大规模的高精度的计算，于是就产生了大数运算这种方法。

二、大数运算原理
由于内置类型的存储范围有限，所以我们可以将大数转换成字符串存储在数组里面，然后再对每一位做单独的加减乘除运算。
我们可以设计一个大数的数据类型，让这种数据类型既可以进行大数的运算，也可以支持没有超出内置类型范围的数的运算。
为了提高效率，如果要运算的数可以用内置类型表示，且计算结果也可以用内置类型表示，那么我们就直接进行运算。如果要运算的数超出范围，或者计算结果超出范围，那么我们就使用大数的运算法则。

三、具体实现

1、大数的数据类型设计
    可以用一个string和一个long long类型来表示一个大数类型，long long类型表示没有超出范围，string表示超出范围的大数。在初始化的时候我们可以将string和long long都进行初始化，在运算的时候再判断是用long long运算还是用string进行运算。
typedef long long INIT64;
class BigData
{
       friend ostream& operator<<(ostream& os,const BigData& b);
public:
       BigData(INIT64  value=0);
       BigData(string strData);
       BigData operator+(BigData b);
       BigData operator-(BigData b);
       BigData operator*(BigData b);
       BigData operator/(BigData b);
private:
       bool isINIT64overflow(const string& strData);
       string Add(string strLeft,string strRight);
       string Sub(string strLeft,string strRight);
       string Mul(string strLeft,string strRight);
       string Div(string strLeft,string strRight);
       char SubLoop(char* &pLeft,size_t& dataLen,const char *pRight,const size_t RSize);
       bool isLgtR(const char* pLeft,const size_t dataLen,const size_t RSize);
private:
       INIT64 _value;
       string _strData;
};

1.1、用一个整数初始化大数对象，其中sprintf的作用就相当于itoa.
BigData::BigData(INIT64  value)
       :_value(value)
{
       char buf[128] = { 0 };
       sprintf(buf,"%lld",_value);
       _strData =buf;
}
1.2、用一个字符串初始化一个大数对象，考虑到输入的字符串可能有各种异常情况，比如前面一空白字符或0开头，出现字母等等，我们将常见的异常情况过滤掉(可以参考atoi是怎么进行过滤的)。
BigData::BigData(string strData)
       :_value(0),_strData("+0")
{
       char* pData = (char*)strData.c_str();
       while (isspace(*pData))              //过滤空白
              pData++;
       if ('' == *pData)
              return;
       char symbol = *pData;
       if (('+' == *pData) || ('-' == *pData))    //过滤符号
              pData++;
       else if (isdigit(*pData))
              symbol = '+';
       else
              return;
       while('0' == *pData)         //过滤前面的0
              pData++;
       if ('' == *pData)
              return;
       _strData.resize(strlen(pData)+1);
       _strData[0] = symbol;
       int count = 1;
       while (*pData>='0' && *pData<='9')
       {
              _value = _value * 10 + *pData - '0';
              _strData[count++] = *pData;
              pData++;
       }
       if (*pData)
              _strData.resize(count);
       if (symbol == '-')
              _value = 0 - _value;
}

1.3、判断一个大数是不是超出范围，因为整数的最大数据类型是long long类型，我们必须用string中的值进行判断，判断大数是不是超出范围。
bool BigData::isINIT64overflow(const string& strData)
{
       const string max_value= "+9223372036854775807";
       const string min_value= "-9223372036854775808";
       if (strData.size() < max_value.size())
              return false;
       else if (strData.size() == max_value.size())
       {
              if (('+'==strData[0]&&strData<=max_value)
                     ||('-'==strData[0]&&strData>=min_value))
                     return false;
       }
       return true;
}

ostream& operator<<(ostream& os,const BigData& b)
{
       const char *str = b._strData.c_str();
       if ('+' == *str)
              cout << str + 1;
       else
              cout << str;
       return os;
}

2、加法的实现
BigData BigData::operator+(BigData b)
{
       if (!isINIT64overflow(_strData) && !isINIT64overflow(b._strData))   //如果都没溢出
       {
              if (_strData[0] != b._strData[0])     //异号直接相加，不会溢出
                     return _value + b._value;
              else if ('+' == _strData[0] && '+' == b._strData[0])
              {
                     INIT64 max_value = 9223372036854775807;
                     if (max_value - _value >= b._value)       //两个正数相加不会溢出
                     {
                           return _value + b._value;
                     }
              }
              else if ('-' == _strData[0] && '-' == b._strData[0])
              {
                     INIT64 min_value =0-9223372036854775808;
                     if (min_value - _value <= b._value)   //两个负数相加不会溢出
                     {
                           return _value + b._value;
                     }
              }
       }
       if (_strData[0] == b._strData[0])      //同号相加
              return BigData(Add(_strData,b._strData));
       else                                         //异号相加可以转换成减法
       {
               //异号相加转换成正号相减
              string Left = _strData;       
              string Right = b._strData;
              Left[0] = '+';
              Right[0] = '+';
              if ('-' == _strData[0])       
                     swap(Left,Right);
              return BigData(Sub(Left,Right));
       }
}


string BigData::Add(string strLeft,string strRight)
{
       size_t LSize = strLeft.size();
       size_t RSize = strRight.size();
       if (LSize < RSize)                 //为了方便，我们保证+号左边的数的位数不小于加号右边的数
       {
              swap(strLeft,strRight);
              swap(LSize,RSize);
       }
       string strTemp;
       strTemp.resize(LSize+1);                 //两个数相加，结果的位数最长是两个运算数中位数最长的运算数加+1
       strTemp[0] = strLeft[0];                
       char step = 0;                            //记录进位
       for (size_t index = 1; index < LSize;index++)
       {
              char ret = strLeft[LSize - index]-'0';
              ret += step;
              if (RSize>index)
              {
                     ret=ret+strRight[RSize-index] - '0';
              }
              step = ret / 10;                     //保存进位情况
              strTemp[LSize + 1 - index] = ret%10+'0'; 
       }
       strTemp[1] = step+'0';                   //向最高位进位，取决于step的值
       return strTemp;
}

3、减法的实现参考加法

4、乘法的实现
BigData BigData::operator * (BigData b)
{
       if ("+0" == _strData || "+0" == b._strData)
              return BigData(0);
       if (!isINIT64overflow(_strData) && !isINIT64overflow(b._strData))
       {
              INIT64 max_value = 9223372036854775807;
              INIT64 min_value = 0 - 9223372036854775808;
              if (_strData[0] == b._strData[0])
              {
                     if (('+' == _strData[0] && max_value / _value >= b._value) || 
                           ('-' == _strData[0] && max_value / _value <= b._value))
                           return _value*b._value;
              }
              else
              {
                     if (('+' == _strData[0] && min_value / _value <= b._value) || 
                           ('-' == _strData[0] && min_value / _value >= b._value))
                           return BigData(_value*b._value);
              }
       }
       //判断运算数中有没有为正负1的特殊情况
       if ("+1"==_strData)
              return BigData(b._strData);
       if ("+1" == b._strData)
              return BigData(_strData);
       if ("-1" == _strData)
       {
              string ret = b._strData;
              if ('+' == b._strData[0])
                     ret[0] = '-';
              else
                     ret[0] = '+';
              return BigData(ret);
       }
       if ("-1" == b._strData)
       {
              string ret =_strData;
              if ('+' ==_strData[0])
                     ret[0] = '-';
              else
                     ret[0] = '+';
              return BigData(ret);
       }
       return BigData(Mul(_strData,b._strData));
}


string BigData::Mul(string strLeft,string strRight)
{
       size_t LSize = strLeft.size();
       size_t RSize = strRight.size();

       //乘法相乘的时候，保证*号左边的数的长度小于等于*号右边的数
       if(LSize > RSize)
       {
              swap(LSize,RSize);
              swap(strLeft,strRight);
       }
       char symbol = '+';
       if (strLeft[0] != strRight[0])         //异号相乘为负
              symbol='-';
       string strTemp;
       strTemp.resize(LSize+RSize-1,'0');      //两数相乘，结果的位数最长是两个运算数位数之和
       strTemp[0] = symbol;
       //因为两个数相乘，即乘数的每一位都要和被乘数相运算，所以必须用两个循环
       for (size_t i = 1; i < LSize;i++)
       {
              if ('0' == strLeft[LSize - i])
                     continue;
              char step=0;                         //记录进位
              for (size_t j=1;j<RSize;j++)
              {
                     char ret = strLeft[LSize-i]-'0';
                     ret*=(strRight[RSize-j]-'0');
                     ret += step+strTemp[LSize + RSize - j - i] - '0';
                     strTemp[LSize + RSize - j - i]= ret%10+'0';
                     step = ret / 10;
              }
              strTemp[LSize- i] += step;
       }
       return strTemp;
}

5、除法的实现
除法的实现有些复杂，原理如下图所示：

BigData BigData::operator/(BigData b)
{
       if ("+0" == b._strData)        //除数不为0
       {
              cout << "exception" << endl;
              return BigData("");
       }

        //考虑一些特殊情况
       if (!isINIT64overflow(_strData) && !isINIT64overflow(b._strData))
       {
              return _value / b._value;
       }
       if ("+0" == _strData || _strData.size()<b._strData.size() || 
              (_strData.size()==b._strData.size() && strncmp(_strData.c_str()+1,b._strData.c_str()+1,_strData.size()-1)<0))
              return BigData(0);
       if (_strData.size() == b._strData.size() && strncmp(_strData.c_str() + 1,b._strData.c_str() + 1,_strData.size() - 1)==0)
       {
              if (_strData[0]==b._strData[0])
                     return BigData(1);
              else
                     return BigData(-1);
       }
       if ("+1" == b._strData)
              return BigData(_strData);
       else if ("-1" == b._strData)
       {
              string ret= _strData;
              ret[0] = '+';
              if ('+' == _strData[0])
                     ret[0] = '-';
              return BigData(ret);
       }

       return BigData(Div(_strData,b._strData));
}
string BigData::Div(string strLeft,string strRight)
{
       char symbol = '+';
       if (strLeft[0] != strRight[0])
              symbol = '-';
       size_t LSize = strLeft.size();
       size_t RSize = strRight.size();
       char *pLeft = (char*)strLeft.c_str()+1;
       char *pRight = (char*)strRight.c_str()+1;
       size_t dataLen =0;
       string strTemp;
       strTemp.append(1,symbol);
       while (''!=(*(pLeft+dataLen-1)))
       {
              if ('0' == *pLeft)
              {
                     pLeft++;
                     strTemp.append(1,'0');
                     continue;
              }
              if (!isLgtR(pLeft,dataLen,pRight,RSize-1))
              {
                     strTemp.append(1,'0');
                     dataLen++;
              }
              else
              {
                     strTemp.append (1,SubLoop(pLeft,RSize)+'0');
                     dataLen++;
              }
       }
       return strTemp;
}
char BigData::SubLoop(char* &pLeft,const size_t RSize)
{
       char count = 0;
       while (isLgtR(pLeft,RSize-1))
       {
              for (size_t index = 1; index <= dataLen; index++)
              {
                     char ret = *(pLeft + dataLen - index) - '0';
                     if (RSize>index)
                     {
                           ret -= (*(pRight + RSize - index-1) - '0');
                     }
                     if (ret < 0)
                     {
                           *(pLeft + dataLen - index - 1) -= 1;
                           ret += 10;
                     }
                     *(pLeft + dataLen - index) = ret + '0';
              }
              count++;
              while ('0' == *pLeft&&dataLen>0)
              {
                     pLeft++;
                     dataLen--;
              }
       }
       return count;
}
//判断以pLeft开始dataLen长度所表示的数的大小是不是大于除数
bool BigData::isLgtR(const char* pLeft,const size_t RSize)  
{
       if (dataLen > RSize)
              return true;
       else if (dataLen == RSize)
       {
              if (strncmp(pLeft,dataLen) >= 0)
                     return true;
       }
       return false;
}

完整源代码