大数运算
发布时间:2020-12-14 01:56:01 所属栏目:大数据 来源:网络整理
导读:? ? ? ? 由于编程语言提供的基本数值数据类型表示的数值范围有限,不能满足较大规模的高精度数值计算,因此需要利用其他方法实现高精度数值的计算,于是产生了大数运算。大数运算主要有加、减、乘三种方法。那么大数到底如何进行运算呢,学习过数据结构的都
? ? ? ? 由于编程语言提供的基本数值数据类型表示的数值范围有限,不能满足较大规模的高精度数值计算,因此需要利用其他方法实现高精度数值的计算,于是产生了大数运算。大数运算主要有加、减、乘三种方法。那么大数到底如何进行运算呢,学习过数据结构的都知道线性表,将大数拆分然后存储在线性表中,不失为一个很好的办法,下面通过字符串实现大数的构造及四则运算。 头文件如下: #ifndef?BIG_DATA_H #define?BIG_DATA_H #include<iostream> using?namespace?std; #include<assert.h> #include<string> ? #define?UN_INTT?0xCCCCCCCCCCCCCCCC #define?MAX_INT64?0x7FFFFFFFFFFFFFFF #define?MIN_INT64?0x8000000000000000 typedef?long?long?INT64; //内置类型 class?BigData { public: ????BigData(INT64?value?=?0xCCCCCCCCCCCCCCCC);//BigData(INT64?value); BigData(const?char*?pData);//对大数进行处理,优化 bool?IsINT64OverFlow()const;//判断大数是否溢出 void?INT64ToString();//由于值在_value中,需将_value转化成string类型 friend?std::ostream&?(operator<<(std::ostream&?_cout,?const?BigData&?bigdata));//输出大数 public: //大数的四则运算 BigData?operator+(const?BigData&?bigdata);//返回值不能传引用 BigData?operator-(const?BigData&?bigdata); BigData?operator*(const?BigData&?bigdata); BigData?operator/(const?BigData&?bigdata); char?SubLoop(char*?pLeft,?int?Lsize,?const?char*?pRight,?int?Rsize); std::string?Add(std::string?left,?std::string?right); std::string?Sub(std::string?left,?std::string?right); std::string?Mul(std::string?left,?std::string?right); std::string?Div(std::string?left,?std::string?right); private: std::string?_strData; INT64?_value; }; #endif 大数运算的构造函数,下面对类似以下情况进行处理: " ? ? ","+123456","00001234","12345xyz","123456789" 具体实现如下: BigData::BigData(INT64?value) ??????:_value(value) { INT64ToString();//在构造函数时将数字转化成字符串 } BigData::BigData(const?char*?pData)//对大数进行处理,优化 { //几种情况:"?????","123456789"; if?(NULL?==?pData) { assert(false); return; } char*?pStr?=?(char*)pData; char?cSymbol?=?pData[0];//标志符号位 if?('+'?==?cSymbol?||?'-'?==?cSymbol) { pStr++; } else?if?(cSymbol?>=?'0'?&&?cSymbol?<=?'9') { cSymbol?=?'+'; } else?return; //"00001234" while?('0'?==?*pStr) { pStr++; } //"12345xyz" _strData.resize(strlen(pData)?+?1);//string中resize()函数改变本字符串的大小 _strData[0]?=?cSymbol;//第一位存放符号位 _value?=?0; int?icount?=?1; while?(*pStr?>=?'0'?&&?*pStr?<=?'9') { _value?=?10?*?_value?+?*pStr?-?'0'; _strData[icount++]?=?*pStr; pStr++; } _strData.resize(icount);//将本字符串的大小调到icount if?('-'?==?cSymbol) { _value?=?0?-?_value;//负值 } } bool?BigData::IsINT64OverFlow()const//判断大数是否溢出 {//64位中数字范围为:[-Ox8FFFFFFF?FFFFFFFF,Ox7FFFFFFF?FFFFFFFF] std::string?temp?=?"+9223372036854775807"; if?('-'?==?_strData[0]) { temp?=?"-9223372036854775808"; } //比较该大数与边界的size,相等时进行字符串直接比较 if?(_strData.size()?<?temp.size()?||?_strData.size()?==?temp.size()?&&?_strData?<=?temp) return?true; else return?false; } void?BigData::INT64ToString()//将_value转化成string类型 {//append()在字符串的末尾添加num个字符ch-----basic_string?&(append(size_t?num,char?ch)) char?cSymbol?=?'+'; if?(_value?<?0) { cSymbol?=?'-'; } //12345->"54321" INT64?temp?=?_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;//包含符号位,故减2 while?(pLeft?<?pRight) { char?tmp?=?*pLeft; *pLeft?=?*pRight; *pRight?=?tmp; pLeft++; pRight--; } } 自主实现大数的输出,代码如下: td::ostream&?(operator<<(std::ostream&?_cout,?const?BigData&?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; } 大数的加法运算: BigData?BigData::operator+(const?BigData&?bigdata) { //两个数都没溢出,结果也没溢出,直接进行相加 if?(IsINT64OverFlow()?&&?bigdata.IsINT64OverFlow()) { //两个数一正一负 if?(_strData[0]?!=?bigdata._strData[0]) { return?_value?+?bigdata._value; } else {//两个数同号,没溢出的情况:如果边界是10,则10-3=7>=6?8,-10-(-3)=-7=<-6?-8 if?((_value?>=?0?&&?(MAX_INT64?-?_value?>=?bigdata._value))?|| (_value?<?0?&&?(MIN_INT64?-?_value?<=?bigdata._value))) { return?_value?+?bigdata._value; } else { return?BigData(Add(_strData,?bigdata._strData).c_str()); } } } //两个数至少一个溢出,结果溢出 //同号 if?(_strData[0]?==?bigdata._strData[0]) { return?BigData(Add(_strData,?bigdata._strData).c_str());//c._str(),size() } //异号 else {//两个数异号a,b;b为正数需要换负号,b为负数需要换正号 string?_StrData?=?bigdata._strData;//注意在此处定义字符串,不是BigData if?(_StrData[0]?==?'+') { _StrData[0]?=?'-'; } else { _StrData[0]?=?'+'; } return?BigData(Sub(_strData,?_StrData).c_str()); } return?BigData(INT64(0)); } std::string?BigData::Add(std::string?left,?std::string?right) { int?iLsize?=?left.size(); int?iRsize?=?right.size(); if?(iLsize?<?iRsize)//只需要左边为长度长的即可 { std::swap(left,?right); std::swap(iLsize,?iRsize); } std::string?sRet; sRet.resize(iLsize?+?1);//相加不会超过较大数的size+1 sRet[0]?=?left[0]; char?Step?=?0;//进位 //通过模除得到每位的数字及进位Step for?(int?iIdx?=?1;?iIdx?<?iLsize;iIdx++) { int?cRet?=?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'; return?sRet; } 大数的减法运算: BigData?BigData::operator-(const?BigData&?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]) { return?BigData(Sub(_strData,?bigdata._strData).c_str()); } else { return?BigData(Add(_strData,?bigdata._strData).c_str()); } return?BigData(INT64(0)); } std::string?BigData::Sub(std::string?left,?std::string?right) { int?iLsize?=?left.size(); int?iRsize?=?right.size(); char?cSymbol?=?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::string?sRet; sRet.resize(iLsize); sRet[0]?=?cSymbol;//保存符号位 for?(int?iIdx?=?1;?iIdx?<?iLsize;?iIdx++)//结束标志为iLsize-1,不是iLsize { //从低到高,取left每一位; char?cRet?=?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'; } return?sRet; } 大数的乘法运算: BigData?BigData::operator*(const?BigData&?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) { return?BigData(Mul(_strData,?bigdata._strData).c_str()); } return?BigData(INT64(0)); } std::string?BigData::Mul(std::string?left,?std::string?right) { int?iLsize?=?left.size(); int?iRsize?=?right.size(); char?cSymbol?=?'+';//确认符号位 if?(left[0]?!=?right[0]) { cSymbol?=?'-'; } if?(iLsize?>?iRsize)//使较小的数为left,提高效率。eg:99*12345678 { swap(left,?right); swap(iLsize,?iRsize); } std::string?sRet; //两个数相乘最大位数为两个数位数的和,left和right中有符号位故减1 sRet.assign(iLsize?+?iRsize?-?1,?'0');//assign()为字符串赋新值'0' sRet[0]?=?cSymbol; int?iDataLen?=?iLsize?+?iRsize?-?1; int?ioffset?=?0;//移位 //先取左边一位和右边相乘;再考虑移位可得到左边每位与右边相乘的结果 for?(int?iLdx?=?1;?iLdx?<?iLsize;?iLdx++) { char?cLeft?=?left[iLsize?-?iLdx]?-?'0'; if?(cLeft?==?0)//如果left中含有0,偏移量加1 { ioffset++; continue; } char?Step?=?0; //99*999=89910+8991; for?(int?iRdx?=?1;?iRdx?<?iRsize;?iRdx++) { char?cRet?=?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++; } return?sRet; } 大数的除法运算: BigData?BigData::operator/(const?BigData&?bigdata) { //1、除数为0 if?(bigdata._strData[1]?==?'0') { assert(false); } //2、两个数没溢出 if?(IsINT64OverFlow()?&&?bigdata.IsINT64OverFlow()) { return?_value?/?bigdata._value; } //3、除数为1或-1 if?(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]) { return?BigData(INT64(-1)); } return?BigData(INT64(1)); } 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)); } return?BigData(Div(_strData,?bigdata._strData).c_str()); } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |