大数运算（小项目）

大数运算

我们都知道变量都有一个数据类型，每个数据类型都有自己所表示的范围，若当数据超过这个类型所表示的范围，就会出现错误，我们称这种现象叫做“溢出”。当然这样就要求每个变量的地址中所存储的数据不能够超过数据类型所表示的范围。整形int的表示范围是-128~127，数据类型表示范围最大的就属long long型，表示范围为：0x7FFFFFFFFFFFFFFF~0x8000000000000000。Long long型的数据类型也不能够表示更大的数据，那如果我们想要对一些大数据进行操作，那应当如何解决这种问题呢？

?

解决大数据的方法一般都是以一个字符串对其进行表示，操作时同样用的是字符串。下面主要讨论利用字符串进行大数据之间的加、减、乘、除的运算：

?

◆加法

?????加法操作主要有以下几种情况：两个数据都没有溢出，其结果也没有溢出的情况下，就可以直接进行“+”操作，若两个没有溢出且两个数据为异号，则相加之后也不会溢出，则直接进行“+”，其余的情况都要利用字符串进行保存，然后从最后一位进行相加，期间要设立一个变量用来保存进位。

◆减法

??? 减法操作一般是：两个数据同号且都没有溢出，或者两个数据没有溢出其结果也没有溢出的情况下，就可以直接“-”，若两个数据中至少有一个溢出，且两个数据异号，可以调用“+”来实现“-”的操作，若两个数据同号时，就需要重新定义“-”操作，对其进行运算。

◆乘法

????当两个数据中有一个数据为0时，则其结果也为0，当两个数据都没有溢出且其结果也不溢出，则可以直接进行“*”，否则，就和前面一样重新定义“*”。

◆除法

??? 要对两个数据进行除运算，就必须要保证除数不为0，若被除数<除数，则其结果为0，若除数为+/-1，则结果的绝对值和被除数绝对值相等，符号与除数和被除数的符号有关，若两个数据的绝对值相等，则结果为+/-1,。当两个数据都没有溢出的情况下，直接进行“/”，否则，重新定义“/”。

下面是具体的程序代码：（附带详细的注释）

#pragma?once
#include?<iostream>
using?namespace?std;
//处理大数据的方法就是利用字符串进行操作
#include?<string.h>
#include?<assert.h>

#define?UN_INT?0xcccccccccccccccc
#define?MAX_INT64?0x7FFFFFFFFFFFFFFF
#define?MIN_INT64?0x8000000000000000
typedef?long?long?INT64;

class?BigData
{
public:
?????BigData::BigData(INT64?value?=?0xcccccccccccccccc)??????//构造函数
??????????:_value(value)
?????{
??????????INT64ToString();
?????}
?????????
?????BigData(const?char?*ptr)????//字符串构造函数
?????{
??????????if?(NULL?==?ptr)??????//检查传入的指针是否为空的情况
??????????{
???????????????return;
??????????}
??????????char?*src?=?(char?*)ptr;
??????????char?cSymbol?=?ptr[0];??????//记录符号位
??????????if?(cSymbol?==?'+'?||?cSymbol?==?'-')??????//传入的字符串首字符是+/-
??????????{
???????????????src++;
??????????}
??????????else?if?(cSymbol?>=?'0'?&&?cSymbol?<=?'9')????????//传入的字符串没有+/-，直接是12345,默认为正数
??????????{
???????????????cSymbol?=?'+';
??????????}
??????????else
??????????{
???????????????return;
??????????}
??????????while?('0'?==?*src)??????//防止这种情况000001234567
??????????{
???????????????src++;
??????????}
??????????_strData.resize(strlen(ptr)?+?1);????//_strData大小，调用string类resize方法
??????????_strData[0]?=?cSymbol;???????//给+/-留第一个空间(cSymbol为‘+’)
??????????_value?=?0;????//保存字符串转换后的数据
??????????int?count?=?1;
??????????while?(*src?>=?'0'?&&?*src?<=?'9')?????//将字符进行拷贝
??????????{
???????????????_value?=?_value?*?10?+?(*src?-?'0');
???????????????_strData[count++]?=?*src;
???????????????src++;
??????????}
??????????_strData.resize(count);
??????????if?(cSymbol?==?'-')?????????//处理为'-'的情况
??????????{
???????????????_value?=?(-1)?*?_value;
??????????}
?????}

?//加法???溢出???无溢出
?????BigData?operator+(const?BigData&?bigData)????//+运算符重载（采用传值的方式，传引用则会更改this）
?????{
??????????if?(IsINT64Overflow()?&&?bigData.IsINT64Overflow())
??????????{
???????????????if?(_strData[0]?!=?bigData._strData[0])??????//两个值异号,不会溢出
???????????????{
????????????????????return?BigData(_value?+?bigData._value);??????//调用构造
???????????????}
???????????????//两个值同号，有可能溢出，下面为不溢出的条件
???????????????//10?-?(2)?=?8??10(溢出)??7（不溢出）?
???????????????//（-10）?-?（-2）?=?-8???-13（溢出）???-7（不溢出）
???????????????else?if?((_value?>=?0?&&?MAX_INT64?-?_value?>=?bigData._value)?||
????????????????(_value?<?0?&&?MIN_INT64?-?_value?<=?bigData._value))
???????????????{
????????????????????return?BigData(_value?+?bigData._value);
???????????????}
??????????}
??????????return?BigData(Add(_strData,?bigData._strData).c_str());
?????}

?????BigData?operator-(const?BigData&?bigData)?????//运算符-重载
?????{
??????????if?(IsINT64Overflow()?&&?bigData.IsINT64Overflow())?????//两个数都没有溢出
??????????{
???????????????if?(_strData[0]?==?bigData._strData[0])?????//减法、同号
???????????????{
????????????????????return?BigData(_value?-?bigData._value);
???????????????}
???????????????else
???????????????{
?????????????????//-10?+?3?=?-7???-6(不溢出)???-8（溢出）
?????????????????//10?+?(-2)?=?8????7(不溢出)???9（溢出）
?????????????????//异号、结果不溢出
????????????????????if?((_value?>?0?&&?MIN_INT64?+?_value?<=?bigData._value)?||???????
?????????????????????(_value?<?0?&&?MAX_INT64?+?_value?>=?bigData._value))
????????????????????{
?????????????????????????return?BigData(_value?-?bigData._value);
????????????????????}
???????????????}
??????????}
??????????else
??????????{
???????????????if?(_strData[0]?!=?bigData._strData[0])????//异号
???????????????{
????????????????????return?BigData(Add(_strData,?bigData._strData).c_str());
???????????????}
???????????????else
???????????????{
????????????????????return?BigData(Sub(_strData,?bigData._strData).c_str());
???????????????}
??????????}
?????}

?????BigData?operator*(const?BigData&?bigData)???//运算符*重载
?????{
??????????if?(_value?==?0?||?bigData._value?==?0)
??????????{
???????????????return?BigData(INT64(0));??????//返回long?long型0
??????????}
??????????if?(IsINT64Overflow()?&&?bigData.IsINT64Overflow())???//两个数据都没有溢出
??????????{
???????????????//10?/?2?=?5?6(溢出)??3（不溢出）
???????????????//10?/?(-2)?=?-5???-6(溢出)????-2（不溢出）
???????????????if?(_strData[0]?==?bigData._strData[0])
???????????????{
????????????????????if?((_value?>?0?&&?MAX_INT64?/?_value?>=?bigData._value)?||
?????????????????????(_value?<?0?&&?MAX_INT64?/?_value?<=?bigData._value))
????????????????????{
?????????????????????return?BigData(_value?*?bigData._value);
????????????????????}
???????????????}
???????????????else
???????????????{
????????????????????//2:??10?/?2?=?5??-(-6)(溢出)???-(-4)（不溢出）
????????????????????//-2:?10?/?-2?=?-5???-6(溢出)????-4（不溢出）
????????????????????if?((_value?>?0?&&?MAX_INT64?/?_value?>=?-bigData._value)?||
?????????????????????(_value?<?0?&&?MAX_INT64?/?_value?<=?-bigData._value))
????????????????????{
?????????????????????????return?_value?*?bigData._value;
????????????????????}
???????????????}
??????????}
??????????return?BigData(Mul(_strData,?bigData._strData).c_str());
?????}

?????//除法??除数不为零???无溢出直接除
?????//left?<?right????0
?????//right?=?+/-1;
?????//left?=?right????数值相等为+、-1；
?????BigData?operator/(const?BigData&?bigData)?????//运算符/重载
?????{
??????????if?('0'?==?bigData._strData[1])??????//检查除数是否为零
??????????{
???????????????assert(false);
???????????????return?BigData(INT64(0));
??????????}
??????????if?(IsINT64Overflow()?&&?bigData.IsINT64Overflow())????//两个都不溢出的情况
??????????{
???????????????return?BigData(_value?/?bigData._value);
??????????}
??????????//left?<?right
??????????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));
??????????}
??????????//除数为1或者-1
??????????if?(bigData._strData?==?"+1"?||?bigData._strData?==?"-1")
??????????{
???????????????string?ret?=?_strData;
???????????????if?(_strData[0]?!=?bigData._strData[0])
???????????????{
????????????????????ret[0]?=?'-';
???????????????}
???????????????else
???????????????{
????????????????????ret[0]?=?'+';
???????????????}
???????????????return?BigData(ret.c_str());
??????????}????
??????????//left?=?right
??????????if?(strcmp(_strData.c_str()?+?1,?bigData._strData.c_str()?+?1)?==?0)
??????????{
???????????????string?tmp?=?"+1";
???????????????if?(_strData[0]?!=?bigData._strData[0])
???????????????{
????????????????????tmp[0]?=?'-';
???????????????}
???????????????return?BigData(tmp.c_str());
??????????}
??????????return?BigData(Div(_strData,?bigData._strData).c_str());
?????}

private:
?????string?Add(string?left,?string?right)?????//字符串相加,left与right是同号的
?????{
??????????int?Lsize?=?left.size();????//返回的是字符串所占的字节数
??????????int?Rsize?=?right.size();
??????????//将两个数据更改为第一个数据大，第二个数据小，便于相加
??????????if?(Lsize?<?Rsize)
??????????{
???????????????swap(Lsize,?Rsize);
???????????????swap(left,?right);
??????????}
??????????string?ret;????//ret用来存放相加的结果
??????????ret.resize(Lsize?+?1);??//resize的作用就相当于开辟一块Lsize+1大小的空间，相加最大超过Lsize的1个空间
??????????ret[0]?=?left[0];?????//先将符号位进行拷贝
??????????char?tmp?=?0;????//保存进位
??????????for?(int?i?=?1;?i?<?Lsize;?i++)
??????????{
???????????????int?src?=?left[Lsize?-?i]?+?tmp?-?'0';
???????????????if?(i?<?Rsize)????//防止第二个数据会一直进行取字符操作，会越界
???????????????{
????????????????????src?+=?right[Rsize?-?i]?-?'0';
???????????????}
???????????????ret[Lsize?-?i?+?1]?=?src?%?10?+?'0';
???????????????tmp?=?src?/?10;
??????????}
??????????ret[1]?=?tmp?+?'0';
??????????return?ret;
?????}

?????string?Sub(string?left,?string?right)??????//字符串相减
?????{
??????????int?Lsize?=?left.size();
??????????int?Rsize?=?right.size();
??????????char?cSymbol?=?left[0];
??????????if?((left?<?right?&&?Lsize?==?Rsize)?||?Lsize?<?Rsize)??
??????????{
???????????????swap(left,?right);
???????????????swap(Lsize,?Rsize);
???????????????if?('+'?==?cSymbol)
???????????????{
????????????????????cSymbol?=?'-';
???????????????}
???????????????else
???????????????{
????????????????????cSymbol?=?'+';
???????????????}
??????????}
??????????string?ret;????//保存相减结果
??????????ret.resize(left.size());?
??????????ret[0]?=?cSymbol;
??????????for?(int?i?=?1;?i?<?Lsize;?i++)
??????????{
???????????????char?src?=?left[Lsize?-?i]?-?'0';
???????????????if?(i?<?Rsize)
???????????????{
????????????????????src?-=?right[Rsize?-?i]?-?'0';
???????????????}
???????????????if?(src?<?0)??????//判断借位
???????????????{
????????????????????left[Lsize?-?i?-?1]?-=?1;
????????????????????src?+=?10;
???????????????}
???????????????ret[Lsize?-?i]?=?src?+?'0';
??????????}
??????????return?ret;
?????}

?????string?Mul(string?left,?string?right)??????//字符串相乘
?????{
??????????int?Lsize?=?left.size();
??????????int?Rsize?=?right.size();
??????????char?cSymbol?=?'+';
??????????if?(left[0]?!=?right[0])
??????????{
???????????????cSymbol?=?'-';
??????????}
??????????if?(Lsize?>?Rsize)?????//将数字较小的作为第一个数据，能够提高循环的效率
??????????{
???????????????swap(left,?Rsize);
??????????}
??????????string?ret;
??????????ret.assign(Lsize?+?Rsize?-?1,?'0');?????//assign申请Lsize+Rsize-1个空间，并初始化为‘0’
??????????int?len?=?ret.size();
??????????int?num?=?0;
??????????ret[0]?=?cSymbol;
??????????for?(int?i?=?1;?i?<?Lsize;?i++)
??????????{
???????????????char?src?=?left[Lsize?-?i]?-?'0';
???????????????char?dst?=?0;
???????????????if?(src?==?0)
???????????????{
????????????????????dst++;
????????????????????continue;
???????????????}
???????????????for?(int?j?=?1;?j?<?Rsize;?j++)
???????????????{
????????????????????char?ptr?=?src?*?(right[Rsize?-?j]?-?'0')?+?dst;
????????????????????ptr?+=?ret[len?-?j?-?num]?-?'0';
????????????????????ret[len?-?j?-?num]?=?ptr?%?10?+?'0';
????????????????????dst?=?ptr?/?10;
???????????????}
???????????????ret[len?-?Rsize?-?num]?+=?dst;
???????????????num++;
??????????}
??????????return?ret;
?????}
?????
?????string?Div(string?left,?string?right)??????//字符串相除
?????{
??????????string?ret;
??????????ret.resize(1,?'+');
??????????if?(left[0]?!=?right[0])???????//确定商的符号
??????????{
???????????????ret[0]?=?'-';
??????????}
??????????char*?pleft?=?(char*)(left.c_str()?+?1);
??????????char*?pright?=?(char*)(right.c_str()?+?1);
??????????int?len?=?right.size()?-?1;????????//因为有符号位
??????????for?(int?i?=?0;?i?<?left.size()?-?1;?)
??????????{
???????????
???????????????if?(!(IsLeftString(pleft,?len,?pright,?right.size()-1)))
???????????????{
????????????????????ret.append(1,?'0');
????????????????????len++;
???????????????}
???????????????else
???????????????{
????????????????????ret.append(1,?loopmove(pleft,?right.size()?-?1));
????????????????????while?(*pleft?==?'0'?&&?len?>?0)
????????????????????{
?????????????????????????pleft++;
?????????????????????????i++;
?????????????????????????len--;
????????????????????}
????????????????????len++;
???????????????}
???????????????if?(len?>?right.size())//pLeft比pRight大一位结果为0，则pLeft中含有0
???????????????{
????????????????????pleft++;
????????????????????len--;
????????????????????i++;
???????????????}
???????????????if?(len?+?i?>?left.size()?-?1)
???????????????{
????????????????????break;
???????????????}
??????????}
??????????return?ret;
?????}
?
?????char?loopmove(char*?pleft,?int?Lsize,?const?char*?pright,?int?Rsize)
?????{
??????????assert(pleft?!=?NULL?&&?pright?!=?NULL);
??????????char?pret?=?'0';
??????????while?(1)???//被除数>除数
??????????{
???????????????if?(!IsLeftString(pleft,?Lsize,?Rsize))
???????????????{
????????????????????break;
???????????????}
???????????????for?(int?i?=?0;?i?<?Rsize;?i++)
???????????????{
????????????????????char?ret?=?pleft[Lsize?-?i?-?1]?-?'0';
????????????????????ret?-=?pright[Rsize?-?i?-?1]?-?'0';
????????????????????if?(ret?<?0)
????????????????????{
?????????????????????????pleft[Lsize?-?i?-?2]?-=?1;
?????????????????????????ret?+=?10;
????????????????????}
????????????????????pleft[Lsize?-?i?-?1]?=?ret?+?'0';
???????????????}
???????????????while?(*pleft?==?'0'?&&?Lsize?>?0)
???????????????{
????????????????????pleft++;
????????????????????Lsize--;
???????????????}
???????????????pret++;
??????????}
??????????return?pret;
?????}
????

?????bool?IsLeftString(const?char*?pleft,?int?Rsize)?//判断被除数大于或等于除数
?????{
??????????if?(Lsize?>?Rsize?||?(Lsize?==?Rsize?&&?strcmp(pleft,?pright)?>=?0))
??????????{
???????????????return?true;
??????????}
??????????return?false;
?????}

?????friend?std::ostream&?operator<<(std::ostream&?_cout,?const?BigData&?bigData)???//<<运算符重载（友元）
?????{
??????????if?(bigData.IsINT64Overflow())???//无溢出的情况
??????????{
???????????????_cout?<<?bigData._value?<<?std::endl;
??????????}
??????????else
??????????{
???????????????char*?ptr?=?(char*)bigData._strData.c_str();??
???????????????//c_str是以const?char*类型返回string中的字符串，因此对其要进行强制转换
???????????????if?(ptr[0]?==?'+')
???????????????{
????????????????????ptr++;
???????????????}
???????????????_cout?<<?ptr?<<?std::endl;
??????????}
??????????return?_cout;
?????}
?
?????bool?IsINT64Overflow()?const???//const声明方法是静态的,声明最大值
?????{
??????????string?temp("+9223372036854775807");???//string的对象temp实例化
??????????if?('-'?==?_strData[0])
??????????{
???????????????temp?=?"-9223372036854775808";
??????????}
??????????if?(_strData.size()?<?temp.size())????//无溢出为true
??????????{
???????????????return?true;
??????????}
??????????else?if?((_strData.size()?==?temp.size())?&&?(_strData?<=?temp))
??????????{
???????????????return?true;
??????????}
??????????else
??????????{
???????????????return?false;
??????????}
?????}
?????
?????void?INT64ToString()???????//将_value转换为字符串
?????{
??????????char?cSymbol?=?'+';
??????????if?(_value?<?0)
??????????{
???????????????cSymbol?=?'-';
??????????}
??????????_strData.append(1,?cSymbol);????//考虑符号位
??????????INT64?pnumber?=?_value;
??????????while?(pnumber)?????????//转化字符串,转换后的字符串与_value是相反的
??????????{
???????????????int?num?=?pnumber?%?10;;
???????????????if?(pnumber?<?0)
???????????????{
????????????????num?=?0?-?num;
???????????????}
???????????????_strData.append(1,?num?+?'0');
???????????????pnumber?/=?10;
??????????}
?
??????????char*?pleft?=?(char*)_strData.c_str()?+?1;
??????????char*?pright?=?pleft?+?_strData.size()?-?2;
??????????while?(pleft?<?pright)??????//字符串逆置
??????????{
???????????????char?tmp?=?*pleft;
???????????????*pleft?=?*pright;
???????????????*pright?=?tmp;
???????????????pleft++;
???????????????pright--;????
??????????}
?????}

private:
?????INT64?_value;
?????std::string?_strData;
};