大数四则运算

问题描述：如何实现对大数的加、减、乘、除操作。

分析问题：在处理大数时，使用long long这些基本类型就会发生溢出问题，我们可以使用c++的STL中string类型存储这些“极限”数据。那么就需要解决两个string类型的相加、相减、相乘以及相除。

首先模拟两个string类型相加：

  加法处理起来不难，左操作数和右操作数从最后一位开始逐位相加，再加进位（初始进位为0），将结果存放在临时字符串中，该字符串大小应该为左操作数位数加一。需要注意的是，不要忘了最后一次的进位。为了方便处理我们让左操作数的位数大于等于右操作数位数。

char cStep = 0;
string retStr;
retStr.resize(iLSize + 1);
    //逐位相加再加进位
for (int iIdx = 1; iIdx < iLSize; ++iIdx)
{
    char cRet = left[iLSize - iIdx] - ‘0‘ + cStep;
    if (iIdx < iRSize)            
    {
         cRet += (right[iRSize - iIdx] - ‘0‘);
    }
    retStr[iLSize - iIdx + 1] = (cRet % 10) + ‘0‘;
    cStep = cRet / 10;
}
retStr[1] = cStep + ‘0‘;

减法也是逐位相减，若结果小于零需要借位，将左操作数前一位减1，相减的结果加10保存在结果字符串对应位。这里我们让左操作数大于等于右操作数，若本身左操作数小于右操作数，则交换他们并将符号位赋为‘-’。

string retStr;
retStr.resize(iLSize);
retStr[0] = cSymbol;
//逐位相减
//1.取左操作数  2.取右操作数(未超出)  3.相减<0,借位：左前一位-=1,结果+10保存
for (int iIdx = 1; iIdx < iLSize; ++iIdx)
{
    char cRet = left[iLSize - iIdx] - ‘0‘;
    if (iIdx < iRSize)
    {
        cRet -= right[iRSize - iIdx] - ‘0‘;
    }
    if (cRet < 0)
    {
        left[iLSize - iIdx - 1] -= 1;
        cRet += 10;
    }
    retStr[iLSize - iIdx] = cRet + ‘0‘;
}

大数乘法需要取操作数1的每一位去和操作数2的每一位相乘，然后错位相加。每一次内循环完成之后，下一次的结果存放需要往前错一位。结果字符串的长度应该是两个操作数之和减一。(让长度小的作左操作数)

for (int iIdx = 1; iIdx < iLSize; ++iIdx)
{
    char cLeft = left[iLSize - iIdx] - ‘0‘;
    char cStep = 0;
    if (0 == cLeft)    //遇0直接错位
    {
        iOffSet++;
        continue;
    }
    for (int iRIdx = 1; iRIdx < iRSize; ++iRIdx)
    {
        char cRet = cLeft*(right[iRSize - iRIdx] - ‘0‘);
        cRet += cStep;
        cRet += (retStr[iDataLen - iOffSet - iRIdx] - ‘0‘);//加上对应位置原有的值
        retStr[iDataLen - iOffSet - iRIdx] = cRet % 10 + ‘0‘;     
        cStep = cRet / 10;
    }
    retStr[iDataLen - iOffSet - iRSize] += cStep;
    iOffSet++;
}

除法：1.取被除数大于除数的区间字符串；2.区间字符串和除数循环相减，直到区间字符串小于除数；3.处理因为减法而出现的零。

for (int iIdx = 0; iIdx < iLSize - 1; ++iIdx)
{
    //处理被除数中的‘0’
    if (‘0‘ == *pLeft)
    {
        pLeft++;
        retStr.append(1, ‘0‘);
        iIdx++;
        continue;
    }
    if  (!IsLeftStrBig(pLeft, iLSize, pRight, iRSize - 1))//用DataLen确定区间字符串
    {
        Datalen++;
        if (iIdx + Datalen > iLSize)
        {
            break;
        }
        retStr.append(1, ‘0‘);
        continue;
    }
    else
    {
        retStr.append(1, subLoop(pLeft, Datalen, pRight, iRSize - 1)); //循环相减
    }
    //删除掉因为进行减法而出现的0
    while (‘0‘ == *pLeft && Datalen > 0)
    {
        pLeft++;
        iIdx++;
        Datalen--;
    }
    Datalen++;
    if (iIdx + Datalen > iLSize)
    {
    break;
    }
}
return retStr;

本文出自 “11356774” 博客，请务必保留此出处http://11366774.blog.51cto.com/11356774/1754462

大数四则运算

原文：http://11366774.blog.51cto.com/11356774/1754462