大数四则运算

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

分析问题：在处理大数时，使用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,?iRSize?-?1));?//循环相减
????}
????//删除掉因为进行减法而出现的0
????while?('0'?==?*pLeft?&&?Datalen?>?0)
????{
????????pLeft++;
????????iIdx++;
????????Datalen--;
????}
????Datalen++;
????if?(iIdx?+?Datalen?>?iLSize)
????{
????break;
????}
}
return?retStr;