由于编程语言提供的基本数值数据类型表示的数值范围有限，不能满足较大规模的高精度数值计算，因此需要利用其他方法实现高精度数值的计算，于是产生了大数运算。大数运算主要有加、减、乘三种方法。那么大数到底如何进行运算呢，学习过数据结构的都知道线性表，将大数拆分然后存储在线性表中，不失为一个很好的办法，下面通过字符串实现大数的构造及四则运算。

头文件如下：

#ifndefBIG_DATA_H#defineBIG_DATA_H#include<iostream>usingnamespacestd;#include<assert.h>#include<string>#defineUN_INTT0xCCCCCCCCCCCCCCCC#defineMAX_INT640x7FFFFFFFFFFFFFFF#defineMIN_INT640x8000000000000000typedeflonglongINT64;//内置类型classBigData{public:BigData(INT64value);BigData(constchar*pData);//对大数进行处理，优化friendstd::ostream&(operator<<(std::ostream&_cout,constBigData&bigdata));//输出大数public://大数的四则运算BigDataoperator+(constBigData&bigdata);//返回值不能传引用BigDataoperator-(constBigData&bigdata);BigDataoperator*(constBigData&bigdata);BigDataoperator/(constBigData&bigdata);std::stringAdd(std::stringleft,std::stringright);std::stringSub(std::stringleft,std::stringright);std::stringMul(std::stringleft,std::stringright);std::stringDiv(std::stringleft,std::stringright);private:boolIsINT64OverFlow()const;//判断大数是否溢出voidINT64ToString();//由于值在_value中，需将_value转化成string类型charSubLoop(char*pLeft,intLsize,constchar*pRight,intRsize);//循环相减boolIsLeftstrBig(constchar*pLeft,intLsize,constchar*pRight,intRsize);//判断是否left大于rightprivate:std::string_strData;INT64_value;};#endif

大数运算的构造函数，下面对类似以下情况进行处理：

" ","+123456","00001234","12345xyz","123456789"

具体实现如下：

BigData::BigData(INT64value):_value(value){INT64ToString();//在构造函数时将数字转化成字符串}BigData::BigData(constchar*pData)//对大数进行处理，优化{//几种情况："","+123456","00001234","12345xyz","123456789";if(NULL==pData){assert(false);return;}char*pStr=(char*)pData;charcSymbol=pData[0];//标志符号位if('+'==cSymbol||'-'==cSymbol){pStr++;}elseif(cSymbol>='0'&&cSymbol<='9'){cSymbol='+';}elsereturn;//"00001234"while('0'==*pStr){pStr++;}//"12345xyz"_strData.resize(strlen(pData)+1);//string中resize()函数改变本字符串的大小_strData[0]=cSymbol;//第一位存放符号位_value=0;inticount=1;while(*pStr>='0'&&*pStr<='9'){_value=10*_value+*pStr-'0';_strData[icount++]=*pStr;pStr++;}_strData.resize(icount);//将本字符串的大小调到icountif('-'==cSymbol){_value=0-_value;//负值}}boolBigData::IsINT64OverFlow()const//判断大数是否溢出{//64位中数字范围为：[-Ox8FFFFFFFFFFFFFFF，Ox7FFFFFFFFFFFFFFF]std::stringtemp="+9223372036854775807";if('-'==_strData[0]){temp="-9223372036854775808";}//比较该大数与边界的size，相等时进行字符串直接比较if(_strData.size()<temp.size()||_strData.size()==temp.size()&&_strData<=temp)returntrue;elsereturnfalse;}voidBigData::INT64ToString()//将_value转化成string类型{//append()在字符串的末尾添加num个字符ch-----basic_string&(append(size_tnum,charch))charcSymbol='+';if(_value<0){cSymbol='-';}//12345->"54321"INT64temp=_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;//包含符号位，故减2while(pLeft<pRight){chartmp=*pLeft;*pLeft=*pRight;*pRight=tmp;pLeft++;pRight--;}}

自主实现大数的输出，代码如下：

td::ostream&(operator<<(std::ostream&_cout,constBigData&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;}

大数的加法运算：

BigDataBigData::operator+(constBigData&bigdata){//两个数都没溢出，结果也没溢出，直接进行相加if(IsINT64OverFlow()&&bigdata.IsINT64OverFlow()){//两个数一正一负if(_strData[0]!=bigdata._strData[0]){return_value+bigdata._value;}else{//两个数同号，没溢出的情况：如果边界是10，则10-3=7>=68,-10-(-3)=-7=<-6-8if((_value>=0&&(MAX_INT64-_value>=bigdata._value))||(_value<0&&(MIN_INT64-_value<=bigdata._value))){return_value+bigdata._value;}else{returnBigData(Add(_strData,bigdata._strData).c_str());}}}//两个数至少一个溢出，结果溢出//同号if(_strData[0]==bigdata._strData[0]){returnBigData(Add(_strData,bigdata._strData).c_str());//c._str(),size()}//异号else{//两个数异号a,b；b为正数需要换负号，b为负数需要换正号string_StrData=bigdata._strData;//注意在此处定义字符串，不是BigDataif(_StrData[0]=='+'){_StrData[0]='-';}else{_StrData[0]='+';}returnBigData(Sub(_strData,_StrData).c_str());}returnBigData(INT64(0));}std::stringBigData::Add(std::stringleft,std::stringright){intiLsize=left.size();intiRsize=right.size();if(iLsize<iRsize)//只需要左边为长度长的即可{std::swap(left,right);std::swap(iLsize,iRsize);}std::stringsRet;sRet.resize(iLsize+1);//相加不会超过较大数的size+1sRet[0]=left[0];charStep=0;//进位//通过模除得到每位的数字及进位Stepfor(intiIdx=1;iIdx<iLsize;iIdx++){intcRet=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';returnsRet;}

大数的减法运算：

BigDataBigData::operator-(constBigData&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._strData[0]设为'-',Add符号随左边数字即被减数(-9999-1=-10000)BigData(Add(_strData,bigdata._strData).c_str());}}}//两个数至少一个溢出，//同号调用减法if(_strData[0]==bigdata._strData[0]){returnBigData(Sub(_strData,bigdata._strData).c_str());}else{returnBigData(Add(_strData,bigdata._strData).c_str());}returnBigData(INT64(0));}std::stringBigData::Sub(std::stringleft,std::stringright){intiLsize=left.size();intiRsize=right.size();charcSymbol=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::stringsRet;sRet.resize(iLsize);sRet[0]=cSymbol;//保存符号位for(intiIdx=1;iIdx<iLsize;iIdx++)//结束标志为iLsize-1,不是iLsize{//从低到高，取left每一位；charcRet=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';}returnsRet;}

大数的乘法运算：

BigDataBigData::operator*(constBigData&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){returnBigData(Mul(_strData,bigdata._strData).c_str());}returnBigData(INT64(0));}std::stringBigData::Mul(std::stringleft,std::stringright){intiLsize=left.size();intiRsize=right.size();charcSymbol='+';//确认符号位if(left[0]!=right[0]){cSymbol='-';}if(iLsize>iRsize)//使较小的数为left，提高效率。eg:99*12345678{swap(left,right);swap(iLsize,iRsize);}std::stringsRet;//两个数相乘最大位数为两个数位数的和，left和right中有符号位故减1sRet.assign(iLsize+iRsize-1,'0');//assign()为字符串赋新值'0'sRet[0]=cSymbol;intiDataLen=iLsize+iRsize-1;intioffset=0;//移位//先取左边一位和右边相乘；再考虑移位可得到左边每位与右边相乘的结果for(intiLdx=1;iLdx<iLsize;iLdx++){charcLeft=left[iLsize-iLdx]-'0';if(cLeft==0)//如果left中含有0，偏移量加1{ioffset++;continue;}charStep=0;//99*999=89910+8991;for(intiRdx=1;iRdx<iRsize;iRdx++){charcRet=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++;}returnsRet;}

大数的除法运算：

BigDataBigData::operator/(constBigData&bigdata){//1、除数为0if(bigdata._strData[1]=='0'){assert(false);}//2、两个数没溢出if(IsINT64OverFlow()&&bigdata.IsINT64OverFlow()){return_value/bigdata._value;}//3、除数为1或-1if(bigdata._value==1||bigdata._value==-1){return_value;}//4、除数和被除数相等//if(strcmp(_strData.data()+1,bigdata._strData.data()+1)==0)//data()返回内容的字符数组形式if(strcmp(_strData.c_str()+1,bigdata._strData.c_str()+1)==0){if(_strData[0]!=bigdata._strData[0]){returnBigData(INT64(-1));}returnBigData(INT64(1));}if(_strData.size()<bigdata._strData.size()||_strData.size()==bigdata._strData.size()&&strcmp(_strData.c_str()+1,bigdata._strData.c_str()+1)<0){returnBigData(INT64(0));}returnBigData(Div(_strData,bigdata._strData).c_str());}std::stringBigData::Div(std::stringleft,std::stringright){//此处用append()对字符串依次赋值std::stringsRet;sRet.append(1,'+');if(left[0]!=right[0]){sRet[0]='-';}char*pLeft=(char*)left.c_str()+1;char*pRight=(char*)right.c_str()+1;intDataLen=right.size()-1;//标记相除的除数位数intLsize=left.size()-1;intRsize=right.size()-1;//eg:222222/33首先取到22和33比较大小，如果大就直接相除，否则DataLen++；for(intiIdx=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;}returnsRet;}charBigData::SubLoop(char*pLeft,intLsize,constchar*pRight,intRsize){assert(pLeft&&pRight);charcRet=0;while(IsLeftstrBig(pLeft,Lsize,pRight,Rsize))//直到被减数小于减数停止运算{for(intiIdx=0;iIdx<Rsize;iIdx++)//进行减运算{charret=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++;}returncRet+'0';}boolBigData::IsLeftstrBig(constchar*pLeft,intLsize,constchar*pRight,intRsize)//判断是否left大于right{assert(pLeft&&pRight);char*pleft=(char*)pLeft;char*pright=(char*)pRight;if(Lsize>Rsize&&*pleft>'0')//eg:112和33{returntrue;}elseif(Lsize==Rsize)//eg:57和33{while(pright){if(*pleft>*pright){returntrue;}elseif(*pleft==*pright){pleft++;pright++;}elsereturnfalse;}}returnfalse;}