高精度运算 | Blueve 湛蓝
我的图书馆
高精度运算 | Blueve 湛蓝
标签归档：高精度运算
取模(Mod)运算应当是我们这个高精度运算类的最后一种运算了^ ^，长达一周的高精度整数运算的介绍的尾声也即将到来~后面部分我将重点介绍模运算，并对高精度整数运算类的最终成品做一点总结。
那么模运算究竟是什么呢？按照大家通俗的理解就是除法运算中剩下的尾巴——余数。其实却实可以这样理解，首先，我们来明确一下除法的表达：
A / B = [A / B] + R / B
[]运算代表向下取整，比如[1.6] = 1。那么[A / B]实际上就是我们做除法运算后所得到的“商”（其实如果商为负数的话，这样说是不合适的，我会在下文中具体解释），而R / B则是除法运算后面的浮点数部分（假如以后有机会做高精度浮点数的运算的话，用这个式子来求是很方便的哦~）。R则是我们这次的主角——模值。
经过整理，我们就可以得到取模运算在数学上的定义：
R = A – [A / B] * B
上面这个公式中所有的运算我们之前都已经完成过了，哈哈，看来代码也就是一行的事呀，可是，一次除法运算、一次乘法运算、一次减法运算……这三个都是相对较为复杂的运算拼在一起，似乎不是很好，回忆一下上一篇文章，特别是那张图，有没有发现，余数出现在了运算的中间过程，那么我只要直接把这个数字拿走，岂不是连完整的一次除法运算都不用就可以得到了么？等等，余数和模的概念还是有点区别的，比如说：
算式中出现了负数，但是不要紧，我们可以根据之前得到的公式得到运算的结果，但在计算之前，我要做一些说明：
这个公式在计算机中使用和实际数学上的使用是有差异的，差异就在于[]运算，这个运算的定义是：对于A，[A]为小于或等于A的整数的上界，通俗讲就是小于或等于A的第一个整数。这点上，和计算机的运算有所不同，计算机采用的“向下取整”策略是去除数字的浮点部分，对于[-1.6]来说，数学上的运算应为-2，但在计算机中，却是-1，这就导致了在出现负数的模运算的时候，计算机的运算结果会和数学上定义的模运算结果出现一个符号的差异，出于约定俗称的规则，我们这里的模运算依照的是计算机的规则，所以在应用计算机模运算的结果的时候，在有负数出现的情况下，数学上的一些性质就会失效，这点需要注意。下面文字中的[]运算，均为计算机中的“舍去取整”。
按照计算机模运算的规则，三个模运算的结果分别是：
记得我们的所有运算都是基于正整数和正整数的么？也就是，我们在除法运算的中间过程中所得到的余数，是不会带符号的，我们需要人为的得到余数的符号，这样才能得到正确的模值。从上面的三个例子我们初步观察得到一个假设，即：被除数的符号和模的符号相同。
在这个假设的引导下，我们来证明：
A / B = [A / B] + R / B
R = A – [A / B] * B
1: A & 0, B & 0
∴A / B & 0, [A / B] & 0
=& [A / B] &= A / B
∴[A / B] * B &= A
∴0 &= A – [A / B] * B = R
2: A & 0, B & 0
∴A / B & 0, [A / B] & 0
=& [A / B] &= A / B
∴[A / B] * B &= A
∴0 &= A – [A / B] * B = R
3: A & 0, B & 0
∴A / B & 0, [A / B] & 0
=& [A / B] &= A / B
∴[A / B] * B &= A
∴0 &= A – [A / B] * B = R
4: A & 0, B & 0
∴A / B & 0, [A / B] & 0
=& [A / B] &= A / B
∴[A / B] * B &= A
∴0 &= A – [A / B] * B = R
R 的符号与 A 的符号相同。
至此，我们就可以复制粘贴除法运算的代码，并稍作修改，用作求模了：
12345678910111213141516171819202122232425262728//重载 % 运算符 使之支持用 % 进行高精度整数的取模运算BigInt operator % (const BigInt bInt) const{&&&&BigInt rslt,&&&&if(*this == 0) return BigInt(0);&&& //除数为0 返回0&&&&//获取相除的被除数的长度&&&&//按倒序位读取被除数&&&&vector&int&::size_type i(num.size());&&&&while(i--)&&&&{&&&&&&&&if(rslt == 0) rslt.num.pop_back();&&&&&&&&rslt.num.insert(rslt.num.begin(), num[i]);& //插入一个数&&&&&&&&//开始试除&&&&&&&&int i(10);&&&&&&&&while(i--)& //由大到小进行试除运算&&&&&&&&{&&&&&&&&&&&&tmp = rslt - (bInt & 0 ? -bInt : bInt) *&&&&&&&&&&&&if(tmp &= 0) //首个非负的试除结果&&&&&&&&&&&&{&&&&&&&&&&&&&&&&rslt =&&&&&&&&&&&&&&&&break;&&&&&&&&&&&&}&&&&&&&&}&&&&}&&&&//模的符号与被除数相同&&&&rslt.symbol =&&&&return }
高精度整数运算类的功能至此就算完备了，但这真的会是最终结果么？显然不是，我们在实现各种运算的时候使用的都是最简单的模拟手算的方法，然而这样做，效率可能并不高，在这个高精度整数运算类中，各种运算的时间复杂度是这样的，这是关于数字的位数的：
加法：O(n)
减法：O(n)
乘法：O(n^2)
除法：O(n^3)
取模：O(n^3)
乘法、除法以及取模运算的时间复杂度增长率实在是太高了，然而这些运算在需要高精度整数运算的一些应用中却又必不可少。事实上，我们有很多方法来提高这些运算的时间效率及空间效率，在时间上对于乘法来说，有二分法，或者目前最快的FFT（接近于n的时间复杂度增长率），这些算法都在实际应用中得到了广泛的应用。在空间上，我们可以使用N进制来存储数字（比如100000进制），这样可以充分利用我们的int类型的容器空间，并且也会一定程度减少时间复杂度的常量系数的大小（进制的提高可以缩短存储的位数，这大家都懂）。虽然这次对于高精度运算类的介绍已经要结束，但是我在未来的文章中，仍然会对其进行改进，并介绍那些著名的优化算法，同时也会给出一些实际应用的算法实例。
以下是完整版的高精度整数运算类的代码，我对其中一些冗余的代码进行的删除：
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383/*&* 高精度整数运算&* 存储及输入输出高精度整数&* 两个整数相加&* 两个整数相减&* 两个整数相乘&* 两个整数相除&* 两个整数求模&* 两个整数比较&* BigInt.h&* @Blueve&* &* 6 4 4 4&*/#include &string&#include &vector&using namespace class BigInt{public:&&&&bool &&&&&&& //标记数字的正负&&&&vector&int&& //存储高精度整数&&&&BigInt(string sNum = "0")&&&&{&&&&&&&&*this = sN&&&&}&&&&BigInt(int iNum)&&&&{&&&&&&&&*this = iN&&&&}&&&&//重载 = 运算符 使之支持用 = 直接用内置整型进行赋值&&&&BigInt operator = (const int iNum)&&&&{&&&&&&&&//清空原有数字&&&&&&&&num.erase(num.begin(), num.end());&&&&&&&&//获取数字的符号&&&&&&&&int tmp(iNum);&&&&&&&&if(iNum & 0)&&&&&&&&{&&&&&&&&&&&&symbol = true;&&&&&&&&&&&&tmp = -&&&&&&&&}&&&&&&&&else&&&&&&&&&&&&symbol = false;&&&&&&&&//以倒序存储高精度整数&&&&&&&&//将数字按位存数&&&&&&&&while(tmp &= 10)&&&&&&&&{&&&&&&&&&&&&num.push_back(tmp % 10);&&&&&&&&&&&&tmp /= 10;&&&&&&&&}&&&&&&&&if(tmp != 0) num.push_back(tmp);&&&&&&&&else if(num.empty()) num.push_back(0);&&&&&&&&return *this;&&&&}&&&&//重载 = 运算符 使之支持用 = 直接用字符串进行赋值&&&&BigInt operator = (const string sNum)&&&&{&&&&&&&&//清空原有数字&&&&&&&&num.erase(num.begin(), num.end());&&&&&&&&//以倒序存储高精度整数&&&&&&&&for(string::size_type i(sNum.size() - 1); i & 0; --i)&&&&&&&&&&&&num.push_back(sNum[i] - '0');&&&&&&&&//确定数字符号&&&&&&&&if(sNum[0] == '-') symbol = true;&&&&&&&&else&&&&&&&&{&&&&&&&&&&&&symbol = false;&&&&&&&&&&&&num.push_back(sNum[0] - '0');&&&&&&&&}&&&&&&&&//清除前导零&&&&&&&&for(vector&int&::size_type i(num.size() - 1); num[i] == 0 && i & 0; --i)&&&&&&&&&&&&num.pop_back();&&&&&&&&return *this;&&&&}&&&&//重载 = 运算符 使之支持用 = 直接高精度整数进行赋值&&&&BigInt operator = (const BigInt bInt)&&&&{&&&&&&&&//清空原有数字&&&&&&&&num.erase(num.begin(), num.end());&&&&&&&&//以倒序存储高精度整数&&&&&&&&for(vector&int&::size_type i(0); i & bInt.num.size(); ++i)&&&&&&&&&&&&num.push_back(bInt.num[i]);&&&&&&&&//符号转存&&&&&&&&symbol = bInt.&&&&&&&&return *this;&&&&}&&&&//重载 + 运算符 使之支持用 + 进行高精度整数的加法运算&&&&BigInt operator + (const BigInt bInt) const&&&&{&&&&&&&&BigI&&&&&&&&//同号相加&&&&&&&&if(bInt.symbol == (*this).symbol)&&&&&&&&{&&&&&&&&&&&&if(bInt.symbol) rslt.symbol = true; //同负&&&&&&&&}&&&&&&&&else if((*this).symbol) //左负 右正&&&&&&&&{&&&&&&&&&&&&rslt = bInt - (-*this);&&&&&&&&&&&&rslt.symbol = true;&&&&&&&&&&&&return &&&&&&&&}&&&&&&&&else if(bInt.symbol)&&& //左正 右负&&&&&&&&{&&&&&&&&&&&&rslt = *this - (-bInt);&&&&&&&&&&&&return &&&&&&&&}&&&&&&&&//获取相加的两个数字的长度&&&&&&&&vector&int&::size_type lenA(num.size()), lenB(bInt.num.size()),&&&&&&&&lng = (lenA & lenB ? lenA : lenB);&& //记录长度较长的&&&&&&&&//逐位相加&&&&&&&&for(vector&int&::size_type i(0); i & ++i)&&&&&&&&{&&&&&&&&&&&&int tmp(rslt.num[rslt.num.size() - 1]); //获取当前位原有的数字&&&&&&&&&&&&//相加&&&&&&&&&&&&if(i & lenA) tmp += num[i];&&&&&&&&&&&&if(i & lenB) tmp += bInt.num[i];&&&&&&&&&&&&rslt.num[rslt.num.size() - 1] = tmp % 10;&& //存入&&&&&&&&&&&&rslt.num.push_back(tmp / 10);&& //进位&&&&&&&&}&&&&&&&&if(rslt.num[lng] == 0) rslt.num.pop_back(); //末位为0则弹出&&&&&&&&return &&&&}&&&&//重载 - 运算符 使之支持用 - 进行高精度整数的加法运算&&&&BigInt operator - (BigInt bInt) const&&&&{&&&&&&&&BigInt rslt, myInt(*this),&&&&&&&&//获取相加的两个数字的长度&&&&&&&&vector&int&::size_type lenA(num.size()), lenB(bInt.num.size()), lng, shrt,&&&&&&&&shrt = (lenA & lenB ? lenB : lenA);& //记录长度较短的&&&&&&&&lng = (lenA & lenB ? lenA : lenB);&& //记录长度较长的&&&&&&&&//同号相减&&&&&&&&if(bInt.symbol == myInt.symbol)&&&&&&&&{&&&&&&&&&&&&if(!bInt.symbol)&&& //同正&&&&&&&&&&&&{&&&&&&&&&&&&&&&&if(myInt & bInt)&&&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&tmp = myI myInt = bI bInt =& //交换&&&&&&&&&&&&&&&&&&&&rslt.symbol = true;&&&&&&&&&&&&&&&&}&&&&&&&&&&&&}&&&&&&&&&&&&else&&& //同负&&&&&&&&&&&&{&&&&&&&&&&&&&&&&if(myInt & bInt)&&&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&tmp = myI myInt = bI bInt =& //交换&&&&&&&&&&&&&&&&&&&&rslt.symbol = false;&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&myInt = -myI bInt = -bI&& //变正&&&&&&&&&&&&&&&&rslt.symbol = true;&&&&&&&&&&&&}&&&&&&&&}&&&&&&&&else if(myInt.symbol) return -(-myInt + bInt);& //左负 右正&&&&&&&&else if(bInt.symbol) return myInt + (-bInt);&&& //左正 右负&&&&&&&&//逐位相减&&&&&&&&for(vector&int&::size_type i(0); i & ++i)&&&&&&&&{&&&&&&&&&&&&if(i & shrt)&&&&&&&&&&&&{//相减&&&&&&&&&&&&&&&&if(myInt.num[i] & bInt.num[i])&&&&&&&&&&&&&&&&{//借位&&&&&&&&&&&&&&&&&&&&myInt.num[i + 1] -= 1;&&&&&&&&&&&&&&&&&&&&rslt.num[i] = myInt.num[i] + 10 - bInt.num[i];& //减&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&else rslt.num[i] = myInt.num[i] - bInt.num[i];& //减&&&&&&&&&&&&}&&&&&&&&&&&&else rslt.num[i] = myInt.num[i];&&&&&&&&&&&&rslt.num.push_back(0);&&&&&&&&}&&&&&&&&//消去前导0&&&&&&&&for(vector&int&::size_type i(rslt.num.size() - 1); rslt.num[i] == 0 && i & 0; --i)&&&&&&&&&&&&rslt.num.pop_back();&&&&&&&&return &&&&}&&&&&&&&&//重载 - 运算符 使之支持用 - 进行高精度整数的加法运算 单目运算&&&&BigInt operator - () const&&&&{&&&&&&&&BigInt rslt(*this);&&&&&&&&if(rslt != 0) rslt.symbol = !rslt.&&&&&&&&return &&&&}&&&&//重载 * 运算符 使之支持用 * 进行高精度整数的乘法运算&&&&BigInt operator * (const BigInt bInt) const&&&&{&&&&&&&&BigI&&&&&&&&//获取相乘的两个数字的长度&&&&&&&&vector&int&::size_type lenA(num.size()), lenB(bInt.num.size()), len(lenA + lenB);&&&&&&&&rslt.num.insert(rslt.num.begin(), len - 1, 0);& //预留位数&&&&&&&&//逐位相乘&&&&&&&&for(vector&int&::size_type i(0); i & lenA; ++i)&&&&&&&&&&&&for(vector&int&::size_type j(0); j & lenB; ++j)&&&&&&&&&&&&{&&&&&&&&&&&&&&&&rslt.num[i + j] += num[i] * bInt.num[j];&&&&&&&&&&&&&&&&rslt.num[i + j + 1] += rslt.num[i + j] / 10;&&&&&&&&&&&&&&&&rslt.num[i + j] %= 10;&&&&&&&&&&&&}&&&&&&&&if(rslt.num[len - 1] == 0) rslt.num.pop_back(); //去除前导零&&&&&&&&//同号为正 异号为负&&&&&&&&if(rslt != 0) rslt.symbol = symbol ^ bInt.&&&&&&&&return &&&&}&&&&//重载 / 运算符 使之支持用 / 进行高精度整数的除法运算&&&&BigInt operator / (const BigInt bInt) const&&&&{&&&&&&&&BigInt tmp, tmp2;&&&&&&&&string rsltS((*this).num.size(), '0');&&&&&&&&if(bInt == 0) return BigInt(0); //除数为0 返回0&&&&&&&&//获取相除的被除数的长度&&&&&&&&//按倒序位读取被除数&&&&&&&&vector&int&::size_type i(num.size());&&&&&&&&string::size_type j(0);&&&&&&&&while(i--)&&&&&&&&{&&&&&&&&&&&&if(tmp == 0) tmp.num.pop_back();&&&&&&&&&&&&tmp.num.insert(tmp.num.begin(), num[i]);&&& //插入一个数&&&&&&&&&&&&//开始试除&&&&&&&&&&&&int i(10);&&&&&&&&&&&&while(i--)& //由大到小进行试除运算&&&&&&&&&&&&{&&&&&&&&&&&&&&&&tmp2 = tmp - (bInt & 0 ? -bInt : bInt) *& //这里对除数为负数的情况作了一些判断，我们在运算过程中要确保符号均为正&&&&&&&&&&&&&&&&if(tmp2 &= 0)&&& //首个非负的试除结果&&&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&rsltS[j] +=& //商&&&&&&&&&&&&&&&&&&&&tmp = tmp2;&&&&&&&&&&&&&&&&&&&&break;&&&&&&&&&&&&&&&&}&&&&&&&&&&&&}&&&&&&&&&&&&++j;&&&&&&&&}&&&&&&&&BigInt rslt(rsltS); //结果 该构造函数自动去除前导零&&&&&&&&//同号为正 异号为负&&&&&&&&if(rslt != 0) rslt.symbol = symbol ^ bInt.&&&&&&&&return &&&&}&&&&//重载 % 运算符 使之支持用 % 进行高精度整数的取模运算&&&&BigInt operator % (const BigInt bInt) const&&&&{&&&&&&&&BigInt rslt,&&&&&&&&if(*this == 0) return BigInt(0);&&& //除数为0 返回0&&&&&&&&//获取相除的被除数的长度&&&&&&&&//按倒序位读取被除数&&&&&&&&vector&int&::size_type i(num.size());&&&&&&&&while(i--)&&&&&&&&{&&&&&&&&&&&&if(rslt == 0) rslt.num.pop_back();&&&&&&&&&&&&rslt.num.insert(rslt.num.begin(), num[i]);& //插入一个数&&&&&&&&&&&&//开始试除&&&&&&&&&&&&int i(10);&&&&&&&&&&&&while(i--)& //由大到小进行试除运算&&&&&&&&&&&&{&&&&&&&&&&&&&&&&tmp = rslt - (bInt & 0 ? -bInt : bInt) *&&&&&&&&&&&&&&&&if(tmp &= 0) //首个非负的试除结果&&&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&rslt =&&&&&&&&&&&&&&&&&&&&break;&&&&&&&&&&&&&&&&}&&&&&&&&&&&&}&&&&&&&&}&&&&&&&&//模的符号与被除数相同&&&&&&&&rslt.symbol =&&&&&&&&return &&&&}&&&&//重载 += 运算符 使之支持用 += 进行高精度整数的加法运算&&&&BigInt operator += (const BigInt bInt)&&&&{&&&&&&&&*this = *this + bI&&&&&&&&return *this;&&&&}&&&&//重载 -= 运算符 使之支持用 -= 进行高精度整数的减法运算&&&&BigInt operator -= (const BigInt bInt)&&&&{&&&&&&&&*this = *this - bI&&&&&&&&return *this;&&&&}&&&&//重载 *= 运算符 使之支持用 *= 进行高精度整数的乘法运算&&&&BigInt operator *= (const BigInt bInt)&&&&{&&&&&&&&*this = *this * bI&&&&&&&&return *this;&&&&}&&&&//重载 /= 运算符 使之支持用 /= 进行高精度整数的除法运算&&&&BigInt operator /= (const BigInt bInt)&&&&{&&&&&&&&*this = *this / bI&&&&&&&&return *this;&&&&}&&&&//重载 %= 运算符 使之支持用 %= 进行高精度整数的模运算&&&&BigInt operator %= (const BigInt bInt)&&&&{&&&&&&&&*this = *this % bI&&&&&&&&return *this;&&&&}&&&&//重载 & 运算符 使之支持使用 & 直接进行高精度整数的比较&&&&bool operator & (const BigInt bInt) const&&&&{&&&&&&&&vector&int&::size_type bLen(bInt.num.size());&&&&&&&&&&&&&&&&&if(!bInt.symbol && symbol)& return true;&&& //左正 右负&&&&&&&&else if(bInt.symbol && !symbol) return false;&& //左负 右正&&&&&&&&else if(num.size() != bLen)&&&& //长度不一样，直接返回大小结果&&&&&&&&{&&&&&&&&&&&&if(!symbol) return num.size() & bL&&&&&&&&&&&&else return num.size() & bL&&&&&&&&}&&&&&&&&//由末位开始逐个比较&&&&&&&&for(vector&int&::size_type i(bLen - 1); i & 0; --i)&&&&&&&&{&&&&&&&&&&&&if(num[i] != bInt.num[i])&&&&&&&&&&&&{&&&&&&&&&&&&&&&&if(!bInt.symbol && !(*this).symbol) return num[i] & bInt.num[i];&&&&&&&&&&&&&&&&else return bInt.num[i] & num[i];&&&&&&&&&&&&}&&&&&&&&}&&&&&&&&if(!bInt.symbol && !symbol) return num[0] & bInt.num[0]; //左正 右正&&&&&&&&else return bInt.num[0] & num[0];&&& //左负右负&&&&}&&&&//重载其它比较运算符&&&&bool operator & (const BigInt bInt) const&&&&{&&&&&&&&return bInt & *this;&&&&}&&&&bool operator &= (const BigInt bInt) const&&&&{&&&&&&&&return !(*this & bInt);&&&&}&&&&bool operator &= (const BigInt bInt) const&&&&{&&&&&&&&return !(*this & bInt);&&&&}&&&&&&&&&bool operator != (const BigInt bInt) const&&&&{&&&&&&&&return (*this & bInt) || (*this & bInt);&&&&}&&&&bool operator == (const BigInt bInt) const&&&&{&&&&&&&&return !(*this != bInt);&&&&}};//重载C++输入流运算符 使之支持C++IO流直接输入高精度整数istream& operator && (istream &in, BigInt& x){&&&&&&&&in &&&&&&x =&&&&return }//重载C++输出流运算符 使之支持C++IO流直接输出高精度整数ostream& operator && (ostream &out, BigInt& x){&&&&if(x.symbol) cout && '-';&&&&//以数字的正确顺序输出&&&&for(vector&int&::size_type i(x.num.size() - 1); i & 0; --i)&&&&&&&&out && x.num[i];&&&&out && x.num[0];&&&&return }
除法是我们实现高精度整数运算中的最后一个四则运算，之所以会放到如此靠后的位置，那是因为在我看来，除法是这四个运算里最难实现的。实际上，在实现除法的运算中，我们用到了几乎之前所有的内容，包含“比较”、“乘法”、“减法”。所以在有了前面的铺垫后，我们实现高精度整数的除法运算就轻而易举了。
依照惯常思路，我们利用我们手算除法的方式来实现高精度除法运算，如图1所示。
我们从左侧逐位获取被除数的一位，然后进行试除，并记录商，反复操作后就能得到高精度商，这个商是向下取整的（没有浮点位），在除法运算的试除的过程中，我们把除数从9开始作为商进行试除，试除的商递减，第一个使得被除数相同位数字减去试除商乘以除数的结果大于零的试除商，即为实际此位上的商。
最后只需要把前导零去除，并按照乘法处理数字符号的方法给结果填上正负标记即可（除法和乘法可以相互转化，但是在运算中我们没有这么做的原因是，除数求倒的过程需要高精度的浮点数，而且该浮点数很可能是无限循环的，这会导致我们的结果最后并不准确）。
下面就是除法的具体实现过程，注意到，其中使用了高精度乘法、高精度减法以及高精度的比较运算：
12345678910111213141516171819202122232425262728293031323334//重载 / 运算符 使之支持用 / 进行高精度整数的除法运算BigInt operator / (const BigInt bInt) const{&&&&BigI&&&&string rsltS;&&&&if(bInt == 0) return BigInt(0); //除数为0 返回0&&&&//获取相除的两个数字的长度&&&&vector&int&::size_type lenA(num.size()), lenB(bInt.num.size()), len(0);&&&&//按倒序位读取被除数&&&&vector&int&::size_type i(lenA);&&&&while(i--)&&&&{&&&&&&&&if(tmp == 0) tmp.num.pop_back();&&&&&&&&tmp.num.insert(tmp.num.begin(), num[i]);&&& //插入一个数&&&&&&&&//开始试除&&&&&&&&BigInt tmp2;&&& //存储试除&&&&&&&&int i(10);&&&&&&&&while(i--)& //由大到小进行试除运算&&&&&&&&{&&&&&&&&&&&&tmp2 = (bInt & 0 ? -bInt : bInt) *&&& //这里对除数为负数的情况作了一些判断，我们在运算过程中要确保符号均为正&&&&&&&&&&&&tmp2 = tmp - tmp2;& //减去试除结果&&&&&&&&&&&&if(tmp2 &= 0)&&& //首个非负的试除结果&&&&&&&&&&&&{&&&&&&&&&&&&&&&&rsltS += i + '0';&& //商&&&&&&&&&&&&&&&&tmp = tmp2;&&&&&&&&&&&&&&&&break;&&&&&&&&&&&&}&&&&&&&&}&&&&}&&&&BigInt rslt(rsltS); //结果 该构造函数自动去除前导零&&&&//同号为正 异号为负&&&&rslt.symbol = symbol ^ bInt.&&&&return }
下面就是目前完整的高精度运算类，对之前的代码做了一些小修改：
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379/*&* 高精度整数运算&* 实现存储及输入输出高精度整数的功能&* 实现两个整数相加的功能&* 实现两个整数相减的功能&* 实现两个整数相乘的功能&* 实现两个整数相除的功能&* 实现两个整数比较的功能&* BigInt.h&* @Blueve&* &* 5 4 4 4&*/#include &string&#include &vector&using namespace class BigInt{public:&&&&bool &&&&&&& //标记数字的正负&&&&vector&int&& //存储高精度整数&&&&BigInt(string sNum = "0")&&&&{&&&&&&&&*this = sN&&&&}&&&&BigInt(int iNum)&&&&{&&&&&&&&*this = iN&&&&}&&&&//重载 = 运算符 使之支持用 = 直接用内置整型进行赋值&&&&BigInt operator = (const int iNum)&&&&{&&&&&&&&//清空原有数字&&&&&&&&num.erase(num.begin(), num.end());&&&&&&&&//获取数字的符号&&&&&&&&int tmp(iNum);&&&&&&&&if(iNum & 0)&&&&&&&&{&&&&&&&&&&&&symbol = true;&&&&&&&&&&&&tmp = -&&&&&&&&}&&&&&&&&else&&&&&&&&{&&&&&&&&&&&&symbol = false;&&&&&&&&}&&&&&&&&//以倒序存储高精度整数&&&&&&&&//将数字按位存数&&&&&&&&while(tmp &= 10)&&&&&&&&{&&&&&&&&&&&&num.push_back(tmp % 10);&&&&&&&&&&&&tmp /= 10;&&&&&&&&}&&&&&&&&if(tmp != 0) num.push_back(tmp);&&&&&&&&else if(num.empty()) num.push_back(0);&&&&&&&&return *this;&&&&}&&&&//重载 = 运算符 使之支持用 = 直接用字符串进行赋值&&&&BigInt operator = (const string sNum)&&&&{&&&&&&&&//清空原有数字&&&&&&&&num.erase(num.begin(), num.end());&&&&&&&&//以倒序存储高精度整数&&&&&&&&for(string::size_type i(sNum.size() - 1); i & 0; --i)&&&&&&&&{&&&&&&&&&&&&num.push_back(sNum[i] - '0');&&&&&&&&}&&&&&&&&//确定数字符号&&&&&&&&if(sNum[0] == '-')&&&&&&&&{&&&&&&&&&&&&symbol = true;&&&&&&&&}&&&&&&&&else&&&&&&&&{&&&&&&&&&&&&symbol = false;&&&&&&&&&&&&num.push_back(sNum[0] - '0');&&&&&&&&}&&&&&&&&//清除前导零&&&&&&&&for(vector&int&::size_type i(num.size() - 1); num[i] == 0 && i & 0; --i)&&&&&&&&{&&&&&&&&&&&&num.pop_back();&&&&&&&&}&&&&&&&&return *this;&&&&}&&&&//重载 = 运算符 使之支持用 = 直接高精度整数进行赋值&&&&BigInt operator = (const BigInt bInt)&&&&{&&&&&&&&//清空原有数字&&&&&&&&num.erase(num.begin(), num.end());&&&&&&&&//以倒序存储高精度整数&&&&&&&&for(vector&int&::size_type i(0); i & bInt.num.size(); ++i)&&&&&&&&{&&&&&&&&&&&&num.push_back(bInt.num[i]);&&&&&&&&}&&&&&&&&//符号转存&&&&&&&&symbol = bInt.&&&&&&&&return *this;&&&&}&&&&//重载 + 运算符 使之支持用 + 进行高精度整数的加法运算&&&&BigInt operator + (const BigInt bInt) const&&&&{&&&&&&&&BigI&&&&&&&&//同号相加&&&&&&&&if(bInt.symbol == (*this).symbol)&&&&&&&&{&&&&&&&&&&&&if(bInt.symbol) rslt.symbol = true; //同负&&&&&&&&}&&&&&&&&else if((*this).symbol) //左负 右正&&&&&&&&{&&&&&&&&&&&&rslt = bInt - (-*this);&&&&&&&&&&&&rslt.symbol = true;&&&&&&&&&&&&return &&&&&&&&}&&&&&&&&else if(bInt.symbol)&&& //左正 右负&&&&&&&&{&&&&&&&&&&&&rslt = *this - (-bInt);&&&&&&&&&&&&return &&&&&&&&}&&&&&&&&//获取相加的两个数字的长度&&&&&&&&vector&int&::size_type lenA(num.size()), lenB(bInt.num.size()),&&&&&&&&lng = (lenA & lenB ? lenA : lenB);&& //记录长度较长的&&&&&&&&//逐位相加&&&&&&&&for(vector&int&::size_type i(0); i & ++i)&&&&&&&&{&&&&&&&&&&&&int tmp(rslt.num[rslt.num.size() - 1]); //获取当前位原有的数字&&&&&&&&&&&&//相加&&&&&&&&&&&&if(i & lenA) tmp += num[i];&&&&&&&&&&&&if(i & lenB) tmp += bInt.num[i];&&&&&&&&&&&&rslt.num[rslt.num.size() - 1] = tmp % 10;&& //存入&&&&&&&&&&&&rslt.num.push_back(tmp / 10);&& //进位&&&&&&&&}&&&&&&&&if(rslt.num[lng] == 0) rslt.num.pop_back(); //末位为0则弹出&&&&&&&&return &&&&}&&&&//重载 - 运算符 使之支持用 - 进行高精度整数的加法运算&&&&BigInt operator - (BigInt bInt) const&&&&{&&&&&&&&BigInt rslt, myInt(*this),&&&&&&&&//获取相加的两个数字的长度&&&&&&&&vector&int&::size_type lenA(num.size()), lenB(bInt.num.size()), lng, shrt,&&&&&&&&shrt = (lenA & lenB ? lenB : lenA);& //记录长度较短的&&&&&&&&lng = (lenA & lenB ? lenA : lenB);&& //记录长度较长的&&&&&&&&//同号相减&&&&&&&&if(bInt.symbol == myInt.symbol)&&&&&&&&{&&&&&&&&&&&&if(!bInt.symbol)&&& //同正&&&&&&&&&&&&{&&&&&&&&&&&&&&&&if(myInt & bInt)&&&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&tmp = myI myInt = bI bInt =& //交换&&&&&&&&&&&&&&&&&&&&rslt.symbol = true;&&&&&&&&&&&&&&&&}&&&&&&&&&&&&}&&&&&&&&&&&&else&&& //同负&&&&&&&&&&&&{&&&&&&&&&&&&&&&&if(myInt & bInt)&&&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&tmp = myI myInt = bI bInt =& //交换&&&&&&&&&&&&&&&&&&&&rslt.symbol = false;&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&myInt = -myI bInt = -bI&& //变正&&&&&&&&&&&&&&&&rslt.symbol = true;&&&&&&&&&&&&}&&&&&&&&}&&&&&&&&else if(myInt.symbol) return -(-myInt + bInt);& //左负 右正&&&&&&&&else if(bInt.symbol) return myInt + (-bInt);&&& //左正 右负&&&&&&&&//逐位相减&&&&&&&&for(vector&int&::size_type i(0); i & ++i)&&&&&&&&{&&&&&&&&&&&&if(i & shrt)&&&&&&&&&&&&{&&&&&&&&&&&&&&&&//相减&&&&&&&&&&&&&&&&if(myInt.num[i] & bInt.num[i])&&&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&//借位&&&&&&&&&&&&&&&&&&&&myInt.num[i + 1] -= 1;&&&&&&&&&&&&&&&&&&&&rslt.num[i] = myInt.num[i] + 10 - bInt.num[i];& //减&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&else rslt.num[i] = myInt.num[i] - bInt.num[i];& //减&&&&&&&&&&&&}&&&&&&&&&&&&else rslt.num[i] = myInt.num[i];&&&&&&&&&&&&rslt.num.push_back(0);&&&&&&&&}&&&&&&&&//消去前导0&&&&&&&&for(vector&int&::size_type i(rslt.num.size() - 1); rslt.num[i] == 0 && i & 0; --i)&&&&&&&&{&&&&&&&&&&&&rslt.num.pop_back();&&&&&&&&}&&&&&&&&return &&&&}&&&&//重载 - 运算符 使之支持用 - 进行高精度整数的加法运算 单目运算&&&&BigInt operator - () const&&&&{&&&&&&&&BigInt rslt(*this);&&&&&&&&if(rslt != 0) rslt.symbol = !rslt.&&&&&&&&return &&&&}&&&&//重载 * 运算符 使之支持用 * 进行高精度整数的乘法运算&&&&BigInt operator * (const BigInt bInt) const&&&&{&&&&&&&&BigI&&&&&&&&//获取相乘的两个数字的长度&&&&&&&&vector&int&::size_type lenA(num.size()), lenB(bInt.num.size()), len(0);&&&&&&&&//逐位相乘&&&&&&&&for(vector&int&::size_type i(0); i & lenA; ++i)&&&&&&&&&&&&for(vector&int&::size_type j(0); j & lenB; ++j)&&&&&&&&&&&&&&&&if(rslt.num.size() - 1 & i + j)&&&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&++&&&&&&&&&&&&&&&&&&&&rslt.num.push_back(num[i] * bInt.num[j]);&& //增加一位&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&else rslt.num[i + j] += num[i] * bInt.num[j];&&&&&&&&//进位&&&&&&&&++&&&&&&&&for(vector&int&::size_type i(0); i & ++i)&&&&&&&&{&&&&&&&&&&&&if(i + 1 & rslt.num.size())&&&&&&&&&&&&{&&&&&&&&&&&&&&&&rslt.num[i + 1] += rslt.num[i] / 10;&&&&&&&&&&&&}&&&&&&&&&&&&else if(rslt.num[i] &= 10)&&&&&&&&&&&&{&&&&&&&&&&&&&&&&rslt.num.push_back(rslt.num[i] / 10);&&&&&&&&&&&&&&&&++&&&&&&&&&&&&}&&&&&&&&&&&&else break;&&&&&&&&&&&&rslt.num[i] %= 10;&&&&&&&&}&&&&&&&&//同号为正 异号为负&&&&&&&&rslt.symbol = symbol ^ bInt.&&&&&&&&return &&&&}&&&&//重载 / 运算符 使之支持用 / 进行高精度整数的除法运算&&&&BigInt operator / (const BigInt bInt) const&&&&{&&&&&&&&BigI&&&&&&&&string rsltS;&&&&&&&&if(bInt == 0) return BigInt(0); //除数为0 返回0&&&&&&&&//获取相除的两个数字的长度&&&&&&&&vector&int&::size_type lenA(num.size()), lenB(bInt.num.size()), len(0);&&&&&&&&//按倒序位读取被除数&&&&&&&&vector&int&::size_type i(lenA);&&&&&&&&while(i--)&&&&&&&&{&&&&&&&&&&&&if(tmp == 0) tmp.num.pop_back();&&&&&&&&&&&&tmp.num.insert(tmp.num.begin(), num[i]);&&& //插入一个数&&&&&&&&&&&&//开始试除&&&&&&&&&&&&BigInt tmp2;&&& //存储试除&&&&&&&&&&&&int i(10);&&&&&&&&&&&&while(i--)& //由大到小进行试除运算&&&&&&&&&&&&{&&&&&&&&&&&&&&&&tmp2 = (bInt & 0 ? -bInt : bInt) *&&& //这里对除数为负数的情况作了一些判断，我们在运算过程中要确保符号均为正&&&&&&&&&&&&&&&&tmp2 = tmp - tmp2;& //减去试除结果&&&&&&&&&&&&&&&&if(tmp2 &= 0)&&& //首个非负的试除结果&&&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&rsltS += i + '0';&& //商&&&&&&&&&&&&&&&&&&&&tmp = tmp2;&&&&&&&&&&&&&&&&&&&&break;&&&&&&&&&&&&&&&&}&&&&&&&&&&&&}&&&&&&&&}&&&&&&&&BigInt rslt(rsltS); //结果 该构造函数自动去除前导零&&&&&&&&//同号为正 异号为负&&&&&&&&rslt.symbol = symbol ^ bInt.&&&&&&&&return &&&&}&&&&//重载 += 运算符 使之支持用 += 进行高精度整数的加法运算&&&&BigInt operator += (const BigInt bInt)&&&&{&&&&&&&&*this = *this + bI&&&&&&&&return *this;&&&&}&&&&//重载 -= 运算符 使之支持用 -= 进行高精度整数的减法运算&&&&BigInt operator -= (const BigInt bInt)&&&&{&&&&&&&&*this = *this - bI&&&&&&&&return *this;&&&&}&&&&//重载 *= 运算符 使之支持用 *= 进行高精度整数的乘法运算&&&&BigInt operator *= (const BigInt bInt)&&&&{&&&&&&&&*this = *this * bI&&&&&&&&return *this;&&&&}&&&&//重载 /= 运算符 使之支持用 /= 进行高精度整数的除法运算&&&&BigInt operator /= (const BigInt bInt)&&&&{&&&&&&&&*this = *this / bI&&&&&&&&return *this;&&&&}&&&&//重载 & 运算符 使之支持使用 & 直接进行高精度整数的比较&&&&bool operator & (const BigInt bInt) const&&&&{&&&&&&&&vector&int&::size_type bLen(bInt.num.size());&&&&&&&&if(!bInt.symbol && symbol)& return true;&&& //左正 右负&&&&&&&&else if(bInt.symbol && !symbol) return false;&& //左负 右正&&&&&&&&else if(num.size() != bLen)&&&& //长度不一样，直接返回大小结果&&&&&&&&{&&&&&&&&&&&&if(!symbol) return num.size() & bL&&&&&&&&&&&&else return num.size() & bL&&&&&&&&}&&&&&&&&//由末位开始逐个比较&&&&&&&&for(vector&int&::size_type i(bLen - 1); i & 0; --i)&&&&&&&&{&&&&&&&&&&&&if(num[i] != bInt.num[i])&&&&&&&&&&&&{&&&&&&&&&&&&&&&&if(!bInt.symbol && !(*this).symbol) return num[i] & bInt.num[i];&&&&&&&&&&&&&&&&else return bInt.num[i] & num[i];&&&&&&&&&&&&}&&&&&&&&}&&&&&&&&if(!bInt.symbol && !symbol) return num[0] & bInt.num[0]; //左正 右正&&&&&&&&else return bInt.num[0] & num[0];&&& //左负右负&&&&}&&&&//重载其它比较运算符&&&&bool operator & (const BigInt bInt) const&&&&{&&&&&&&&return bInt & *this;&&&&}&&&&bool operator &= (const BigInt bInt) const&&&&{&&&&&&&&return !(*this & bInt);&&&&}&&&&bool operator &= (const BigInt bInt) const&&&&{&&&&&&&&return !(*this & bInt);&&&&}&&&&bool operator != (const BigInt bInt) const&&&&{&&&&&&&&return (*this & bInt) || (*this & bInt);&&&&}&&&&bool operator == (const BigInt bInt) const&&&&{&&&&&&&&return !(*this != bInt);&&&&}};//重载C++输入流运算符 使之支持C++IO流直接输入高精度整数istream& operator && (istream &in, BigInt& x){&&&&&&&&in &&&&&&x =&&&&return }//重载C++输出流运算符 使之支持C++IO流直接输出高精度整数ostream& operator && (ostream &out, BigInt& x){&&&&if(x.symbol) cout && '-';&&&&//以数字的正确顺序输出&&&&for(vector&int&::size_type i(x.num.size() - 1); i & 0; --i)&&&&{&&&&&&&&out && x.num[i];&&&&}&&&&out && x.num[0];&&&&return }
鉴于从本篇文章开始后的高精度运算类加入了“负数”概念，在实现高精度整数运算的时候如果要求能计算负数，那就需要在每次运算的时候加入很多判断，这在解题过程中会使效率降低很多，所以我将本篇文章及之后相关的文章都归类到“”当中。实际上，在比赛中如果需要用到负数，只要知道负数的下界，我们就可以用正整数来表示负数，方法为：
运算中处理的数字 = 实际数字 + 负数下界的绝对值
通过这样的方法我们可以规避对于负数运算的额外判断，而且可以确保在运算过程中只会涉及到正整数间的运算，而绝不会出现负数。
但是对于一个真正的高精度运算而言，存在下界是不允许的，所以在这里，我们就来探讨整个整数域上的高精度运算。
在高精度整数类中，我们增加一个成员symbol来表示当前数字的符号是正或是负。这样我们在运算的时候就可以针对数字的符号来选择进行何种方式的运算。需要关注的是，我们要处理的是正整数，数字的符号是作为一种标记来存在的，所以现在我先将正负数字之间存在的各种运算关系整理如下，使我们在运算过程中只考虑正数与正数的运算：
正数 + 正数 = 正数 + 正数
负数 + 正数 = 正数 – (-负数)
正数 + 负数 = 正数 – (-负数)
负数 + 负数 = -((-负数) + (-负数))
关于正负数之间的减法，我们是这样规定的：
基本的规则是：
绝对值较大的数字 – 绝对值较小的数字
也就是所有涉及负数的运算，都要符合这个规则，如果一个较小数字去减较大数字，那么则交换这两个数字，最后的结果符号改变一下即可。
正数 – 负数 = 正数 + (-负数)
正数 – 正数 = 正数 – 正数
负数 – 正数 = -((-负数) + 正数)
负数 – 负数 = -((-负数) – (-负数))
这样，我们就把各种情况考虑到了，在涉及到运算的过程中，我们只要考虑正数和正数的运算即可了。
其中“-”运算符单独和数字一起使用的时候作为负号，只改变数字的符号标记，对其值不做任何改变（对数字0的处理除外）。在C++当中，只需要将“-”进行单目运算符的重载即可实现。
至于减法的实现，和之前加法的实现类似，只不过“进位”要改为“借位”，稍微有点区别，但是实现起来并不困难。
在引入负数之后，乘法以及比较的算法也需要做出一些调整，乘法比较简单：
因数符号相同 = 正数
因数符号不同 = 负数
而对于比较而言，增加的部分需要，遵循下面的规则：
正数 & 负数
负数 ? 负数 = 绝对值大的数字小
和上面的运算类似，这样做，是为了让我们在对数字进行操作的时候，仅仅考虑数字本身，而不考虑符号。
截止到目前的高精度运算类的代码附于下面，我对其中涉及本篇文章内容的代码进行高亮处理，方便阅读：
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338/*&* 高精度整数运算&* 实现存储及输入输出高精度整数的功能&* 实现两个正整数相加的功能&* 实现两个正整数相乘的功能&* 实现两个正整数比较的功能&* BigInt.h&* @Blueve&* &* 1 1 1 2&*/#include &string&#include &vector&using namespace class BigInt{public:&&&&bool &&&&&&& //标记数字的正负&&&&vector&int&& //存储高精度整数&&&&BigInt(string sNum = "0")&&&&{&&&&&&&&*this = sN&&&&}&&&&BigInt(int iNum)&&&&{&&&&&&&&*this = iN&&&&}&&&&//重载 = 运算符 使之支持用 = 直接用内置整型进行赋值&&&&BigInt operator = (const int iNum)&&&&{&&&&&&&&//清空原有数字&&&&&&&&num.erase(num.begin(), num.end());&&&&&&&&//获取数字的符号&&&&&&&&int &&&&&&&&if(iNum & 0)&&&&&&&&{&&&&&&&&&&&&symbol = true;&&&&&&&&&&&&tmp = -iN&&&&&&&&}&&&&&&&&else&&&&&&&&{&&&&&&&&&&&&symbol = false;&&&&&&&&&&&&tmp = iN&&&&&&&&}&&&&&&&&//以倒序存储高精度整数&&&&&&&&//将数字按位存数&&&&&&&&while(tmp &= 10)&&&&&&&&{&&&&&&&&&&&&num.push_back(tmp % 10);&&&&&&&&&&&&tmp /= 10;&&&&&&&&}&&&&&&&&if(tmp != 0) num.push_back(tmp);&&&&&&&&else if(num.empty()) num.push_back(0);&&&&&&&&return *this;&&&&}&&&&//重载 = 运算符 使之支持用 = 直接用字符串进行赋值&&&&BigInt operator = (const string sNum)&&&&{&&&&&&&&//清空原有数字&&&&&&&&num.erase(num.begin(), num.end());&&&&&&&&//以倒序存储高精度整数&&&&&&&&for(string::size_type i(sNum.size() - 1); i & 0; --i)&&&&&&&&{&&&&&&&&&&&&num.push_back(sNum[i] - '0');&&&&&&&&}&&&&&&&&//确定数字符号&&&&&&&&if(sNum[0] == '-')&&&&&&&&{&&&&&&&&&&&&symbol = true;&&&&&&&&}&&&&&&&&else&&&&&&&&{&&&&&&&&&&&&symbol = false;&&&&&&&&&&&&num.push_back(sNum[0] - '0');&&&&&&&&}&&&&&&&&//清除前导零&&&&&&&&for(vector&int&::size_type i(num.size() - 1); num[i] == 0 && i & 0; --i)&&&&&&&&{&&&&&&&&&&&&num.pop_back();&&&&&&&&}&&&&&&&&return *this;&&&&}&&&&//重载 = 运算符 使之支持用 = 直接高精度整数进行赋值&&&&BigInt operator = (const BigInt bInt)&&&&{&&&&&&&&//清空原有数字&&&&&&&&num.erase(num.begin(), num.end());&&&&&&&&//以倒序存储高精度整数&&&&&&&&for(vector&int&::size_type i(0); i & bInt.num.size(); ++i)&&&&&&&&{&&&&&&&&&&&&num.push_back(bInt.num[i]);&&&&&&&&}&&&&&&&&//符号转存&&&&&&&&symbol = bInt.&&&&&&&&return *this;&&&&}&&&&//重载 + 运算符 使之支持用 + 进行高精度整数的加法运算&&&&BigInt operator + (const BigInt bInt) const&&&&{&&&&&&&&BigI&&&&&&&&//同号相加&&&&&&&&if(bInt.symbol == (*this).symbol)&&&&&&&&{&&&&&&&&&&&&if(bInt.symbol) rslt.symbol = true; //同负&&&&&&&&}&&&&&&&&else if((*this).symbol) //左负 右正&&&&&&&&{&&&&&&&&&&&&rslt = bInt - (-*this);&&&&&&&&&&&&rslt.symbol = true;&&&&&&&&&&&&return &&&&&&&&}&&&&&&&&else if(bInt.symbol)&&& //左正 右负&&&&&&&&{&&&&&&&&&&&&rslt = *this - (-bInt);&&&&&&&&&&&&return &&&&&&&&}&&&&&&&&//获取相加的两个数字的长度&&&&&&&&vector&int&::size_type lenA(num.size()), lenB(bInt.num.size()),&&&&&&&&lng = (lenA & lenB ? lenA : lenB);&& //记录长度较长的&&&&&&&&//逐位相加&&&&&&&&for(vector&int&::size_type i(0); i & ++i)&&&&&&&&{&&&&&&&&&&&&int tmp(rslt.num[rslt.num.size() - 1]); //获取当前位原有的数字&&&&&&&&&&&&//相加&&&&&&&&&&&&if(i & lenA) tmp += num[i];&&&&&&&&&&&&if(i & lenB) tmp += bInt.num[i];&&&&&&&&&&&&rslt.num[rslt.num.size() - 1] = tmp % 10;&& //存入&&&&&&&&&&&&rslt.num.push_back(tmp / 10);&& //进位&&&&&&&&}&&&&&&&&if(rslt.num[lng] == 0) rslt.num.pop_back(); //末位为0则弹出&&&&&&&&return &&&&}&&&&//重载 - 运算符 使之支持用 - 进行高精度整数的加法运算&&&&BigInt operator - (BigInt bInt) const&&&&{&&&&&&&&BigInt rslt, myInt(*this),&&&&&&&&//获取相加的两个数字的长度&&&&&&&&vector&int&::size_type lenA(num.size()), lenB(bInt.num.size()), lng, shrt,&&&&&&&&shrt = (lenA & lenB ? lenB : lenA);& //记录长度较短的&&&&&&&&lng = (lenA & lenB ? lenA : lenB);&& //记录长度较长的&&&&&&&&//同号相减&&&&&&&&if(bInt.symbol == myInt.symbol)&&&&&&&&{&&&&&&&&&&&&if(!bInt.symbol)&&& //同正&&&&&&&&&&&&{&&&&&&&&&&&&&&&&if(myInt & bInt)&&&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&tmp = myI myInt = bI bInt =& //交换&&&&&&&&&&&&&&&&&&&&rslt.symbol = true;&&&&&&&&&&&&&&&&}&&&&&&&&&&&&}&&&&&&&&&&&&else&&& //同负&&&&&&&&&&&&{&&&&&&&&&&&&&&&&if(myInt & bInt)&&&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&tmp = myI myInt = bI bInt =& //交换&&&&&&&&&&&&&&&&&&&&rslt.symbol = false;&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&myInt = -myI bInt = -bI&& //变正&&&&&&&&&&&&&&&&rslt.symbol = true;&&&&&&&&&&&&}&&&&&&&&}&&&&&&&&else if(myInt.symbol) return -(-myInt + bInt);& //左负 右正&&&&&&&&else if(bInt.symbol) return myInt + (-bInt);&&& //左正 右负&&&&&&&&//逐位相减&&&&&&&&for(vector&int&::size_type i(0); i & ++i)&&&&&&&&{&&&&&&&&&&&&if(i & shrt)&&&&&&&&&&&&{&&&&&&&&&&&&&&&&//相减&&&&&&&&&&&&&&&&if(myInt.num[i] & bInt.num[i])&&&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&//借位&&&&&&&&&&&&&&&&&&&&myInt.num[i + 1] -= 1;&&&&&&&&&&&&&&&&&&&&rslt.num[i] = myInt.num[i] + 10 - bInt.num[i];& //减&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&else rslt.num[i] = myInt.num[i] - bInt.num[i];& //减&&&&&&&&&&&&}&&&&&&&&&&&&else rslt.num[i] = myInt.num[i];&&&&&&&&&&&&rslt.num.push_back(0);&&&&&&&&}&&&&&&&&//消去前导0&&&&&&&&len = rslt.num.size();&&&&&&&&while(len--)&&&&&&&&{&&&&&&&&&&&&if(rslt.num[len] == 0) rslt.num.pop_back();&&&&&&&&&&&&else break;&&&&&&&&}&&&&&&&&if(rslt.num.empty()) rslt.num.push_back(0); //确保有零存在&&&&&&&&return &&&&}&&&&//重载 - 运算符 使之支持用 - 进行高精度整数的加法运算 单目运算&&&&BigInt operator - () const&&&&{&&&&&&&&BigInt rslt(*this);&&&&&&&&if(rslt != 0) rslt.symbol = !rslt.&&&&&&&&return &&&&}&&&&//重载 * 运算符 使之支持用 * 进行高精度整数的乘法运算&&&&BigInt operator * (const BigInt bInt) const&&&&{&&&&&&&&BigI&&&&&&&&//获取相乘的两个数字的长度&&&&&&&&vector&int&::size_type lenA(num.size()), lenB(bInt.num.size()), len(0);&&&&&&&&//逐位相乘&&&&&&&&for(vector&int&::size_type i(0); i & lenA; ++i)&&&&&&&&&&&&for(vector&int&::size_type j(0); j & lenB; ++j)&&&&&&&&&&&&&&&&if(rslt.num.size() - 1 & i + j)&&&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&++&&&&&&&&&&&&&&&&&&&&rslt.num.push_back(num[i] * bInt.num[j]);&& //增加一位&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&else rslt.num[i + j] += num[i] * bInt.num[j];&&&&&&&&//进位&&&&&&&&for(vector&int&::size_type i(0); i & ++i)&&&&&&&&{&&&&&&&&&&&&if(i + 1 & rslt.num.size())&&&&&&&&&&&&{&&&&&&&&&&&&&&&&rslt.num[i + 1] += rslt.num[i] / 10;&&&&&&&&&&&&}&&&&&&&&&&&&else if(rslt.num[i] &= 10)&&&&&&&&&&&&{&&&&&&&&&&&&&&&&rslt.num.push_back(rslt.num[i] / 10);&&&&&&&&&&&&&&&&++&&&&&&&&&&&&}&&&&&&&&&&&&else break;&&&&&&&&&&&&rslt.num[i] %= 10;&&&&&&&&}&&&&&&&&//同号为正 异号为负&&&&&&&&rslt.symbol = symbol ^ bInt.&&&&&&&&return &&&&}&&&&//重载 += 运算符 使之支持用 += 进行高精度整数的加法运算&&&&BigInt operator += (const BigInt bInt)&&&&{&&&&&&&&*this = *this + bI&&&&&&&&return *this;&&&&}&&&&//重载 -= 运算符 使之支持用 -= 进行高精度整数的减法运算&&&&BigInt operator -= (const BigInt bInt)&&&&{&&&&&&&&*this = *this - bI&&&&&&&&return *this;&&&&}&&&&//重载 *= 运算符 使之支持用 *= 进行高精度整数的乘法运算&&&&BigInt operator *= (const BigInt bInt)&&&&{&&&&&&&&*this = *this * bI&&&&&&&&return *this;&&&&}&&&&//重载 & 运算符 使之支持使用 & 直接进行高精度整数的比较&&&&bool operator & (const BigInt bInt) const&&&&{&&&&&&&&vector&int&::size_type bLen(bInt.num.size());&&&&&&&&if(!bInt.symbol && symbol)& return true;&&& //左正 右负&&&&&&&&else if(bInt.symbol && !symbol) return false;&& //左负 右正&&&&&&&&else if(num.size() != bLen)&&&& //长度不一样，直接返回大小结果&&&&&&&&{&&&&&&&&&&&&if(!symbol) return num.size() & bL&&&&&&&&&&&&else return num.size() & bL&&&&&&&&}&&&&&&&&//由末位开始逐个比较&&&&&&&&for(vector&int&::size_type i(bLen - 1); i & 0; --i)&&&&&&&&{&&&&&&&&&&&&if(num[i] != bInt.num[i])&&&&&&&&&&&&{&&&&&&&&&&&&&&&&if(!bInt.symbol && !(*this).symbol) return num[i] & bInt.num[i];&&&&&&&&&&&&&&&&else return bInt.num[i] & num[i];&&&&&&&&&&&&}&&&&&&&&}&&&&&&&&if(!bInt.symbol && !symbol) return num[0] & bInt.num[0]; //左正 右正&&&&&&&&else return bInt.num[0] & num[0];&&& //左负右负&&&&}&&&&//重载其它比较运算符&&&&bool operator & (const BigInt bInt) const&&&&{&&&&&&&&return bInt & *this;&&&&}&&&&bool operator &= (const BigInt bInt) const&&&&{&&&&&&&&return !(*this & bInt);&&&&}&&&&bool operator &= (const BigInt bInt) const&&&&{&&&&&&&&return !(*this & bInt);&&&&}&&&&bool operator != (const BigInt bInt) const&&&&{&&&&&&&&return (*this & bInt) || (*this & bInt);&&&&}&&&&bool operator == (const BigInt bInt) const&&&&{&&&&&&&&return !(*this != bInt);&&&&}};//重载C++输入流运算符 使之支持C++IO流直接输入高精度整数istream& operator && (istream &in, BigInt& x){&&&&&&&&in &&&&&&x =&&&&return }//重载C++输出流运算符 使之支持C++IO流直接输出高精度整数ostream& operator && (ostream &out, BigInt& x){&&&&if(x.symbol) cout && '-';&&&&//以数字的正确顺序输出&&&&for(vector&int&::size_type i(x.num.size() - 1); i & 0; --i)&&&&{&&&&&&&&out && x.num[i];&&&&}&&&&out && x.num[0];&&&&return }
比较运算用于比较两个高精度整数的大小，算法十分简单，只需要按照两个规则，就可以得到两个数字谁大谁小：
（1）如果一个数字比另一个数字位数少，则这个数字必比另一个数字小。
这就要求我们存储的数字不能有前导零。
（2）从末位开始向个位逐个比较，位上的数字大的，则这个数字也大。
通过这样的比较法则，我们就可以实现比较运算小于号“&”：
12345678910111213//重载 & 运算符 使之支持使用 & 直接进行高精度整数的比较bool operator & (const BigInt bInt) const{&&&&vector&int&::size_type bLen(bInt.num.size());&&&&//长度不一样，直接返回大小结果&&&&if(num.size() != bLen) return num.size() & bL&&&&//由末位开始逐个比较&&&&for(vector&int&::size_type i(bLen - 1); i & 0; --i)&&&&{&&&&&&&&if(num[i] != bInt.num[i]) return num[i] & bInt.num[i];&&&&}&&&&return num[0] & bInt.num[0];}
神奇的是，我们只需要一个小于的比较运算符，就可以实现其它所有的比较运算符，请看下面的代码：
12345678910111213141516171819202122232425//重载其它比较运算符bool operator & (const BigInt bInt) const{&&&&return bInt & *this;}bool operator &= (const BigInt bInt) const{&&&&return !(*this & bInt);}bool operator &= (const BigInt bInt) const{&&&&return !(*this & bInt);}bool operator != (const BigInt bInt) const{&&&&return (*this & bInt) || (*this & bInt);}bool operator == (const BigInt bInt) const{&&&&return !(*this != bInt);}
下面给出完整的高精度运算类的代码：
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220/*&* 高精度整数运算&* 实现存储及输入输出高精度整数的功能&* 实现两个正整数相加的功能&* 实现两个正整数相乘的功能&* 实现两个正整数比较的功能&* BigInt.h&* @Blueve&* &* 1 1 1 2&*/#include &string&#include &vector&using namespace class BigInt{public:&&&&vector&int&& //存储高精度整数&&&&BigInt(string sNum = "0")&&&&{&&&&&&&&*this = sN&&&&}&&&&BigInt(int iNum)&&&&{&&&&&&&&*this = iN&&&&}&&&&//重载 = 运算符 使之支持用 = 直接用内置整型进行赋值&&&&BigInt operator = (const int iNum)&&&&{&&&&&&&&//清空原有数字&&&&&&&&num.erase(num.begin(), num.end());&&&&&&&&//以倒序存储高精度整数&&&&&&&&//将数字按位存数&&&&&&&&int tmp(iNum);&&&&&&&&while(tmp &= 10)&&&&&&&&{&&&&&&&&&&&&num.push_back(tmp % 10);&&&&&&&&&&&&tmp /= 10;&&&&&&&&}&&&&&&&&if(tmp != 0) num.push_back(tmp);&&&&&&&&else if(num.empty()) num.push_back(0);&&&&&&&&return *this;&&&&}&&&&//重载 = 运算符 使之支持用 = 直接用字符串进行赋值&&&&BigInt operator = (const string sNum)&&&&{&&&&&&&&//清空原有数字&&&&&&&&num.erase(num.begin(), num.end());&&&&&&&&//以倒序存储高精度整数&&&&&&&&for(string::size_type i(sNum.size() - 1); i & 0; --i)&&&&&&&&{&&&&&&&&&&&&num.push_back(sNum[i] - '0');&&&&&&&&}&&&&&&&&num.push_back(sNum[0] - '0');&&&&&&&&//清除前导零&&&&&&&&for(vector&int&::size_type i(num.size() - 1); num[i] == 0 && i & 0; --i)&&&&&&&&{&&&&&&&&&&&&num.pop_back();&&&&&&&&}&&&&&&&&return *this;&&&&}&&&&//重载 = 运算符 使之支持用 = 直接高精度整数进行赋值&&&&BigInt operator = (const BigInt bInt)&&&&{&&&&&&&&//清空原有数字&&&&&&&&num.erase(num.begin(), num.end());&&&&&&&&//以倒序存储高精度整数&&&&&&&&for(vector&int&::size_type i(0); i & bInt.num.size(); ++i)&&&&&&&&{&&&&&&&&&&&&num.push_back(bInt.num[i]);&&&&&&&&}&&&&&&&&return *this;&&&&}&&&&//重载 + 运算符 使之支持用 + 进行高精度整数的加法运算&&&&BigInt operator + (const BigInt bInt) const&&&&{&&&&&&&&BigI&&&&&&&&//获取相加的两个数字的长度&&&&&&&&vector&int&::size_type lenA(num.size()), lenB(bInt.num.size()),&&&&&&&&lng = (lenA & lenB ? lenA : lenB);&& //记录长度较长的&&&&&&&&//逐位相加&&&&&&&&for(vector&int&::size_type i(0); i & ++i)&&&&&&&&{&&&&&&&&&&&&int tmp(rslt.num[rslt.num.size() - 1]); //获取当前位原有的数字&&&&&&&&&&&&//相加&&&&&&&&&&&&if(i & lenA) tmp += num[i];&&&&&&&&&&&&if(i & lenB) tmp += bInt.num[i];&&&&&&&&&&&&rslt.num[rslt.num.size() - 1] = tmp % 10;&& //存入&&&&&&&&&&&&rslt.num.push_back(tmp / 10);&& //进位&&&&&&&&}&&&&&&&&if(rslt.num[lng] == 0) rslt.num.pop_back(); //末位为0则弹出&&&&&&&&return &&&&}&&&&//重载 * 运算符 使之支持用 * 进行高精度整数的乘法运算&&&&BigInt operator * (const BigInt bInt) const&&&&{&&&&&&&&BigI&&&&&&&&//获取相乘的两个数字的长度&&&&&&&&vector&int&::size_type lenA(num.size()), lenB(bInt.num.size()), len(0);&&&&&&&&//逐位相乘&&&&&&&&for(vector&int&::size_type i(0); i & lenA; ++i)&&&&&&&&{&&&&&&&&&&&&for(vector&int&::size_type j(0); j & lenB; ++j)&&&&&&&&&&&&{&&&&&&&&&&&&&&&&if(rslt.num.size() - 1 & i + j)&&&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&++&&&&&&&&&&&&&&&&&&&&rslt.num.push_back(num[i] * bInt.num[j]);&& //增加一位&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&else&&&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&rslt.num[i + j] += num[i] * bInt.num[j];&&&&&&&&&&&&&&&&}&&&&&&&&&&&&}&&&&&&&&}&&&&&&&&//进位&&&&&&&&for(vector&int&::size_type i(0); i & ++i)&&&&&&&&{&&&&&&&&&&&&if(i + 1 & rslt.num.size())&&&&&&&&&&&&{&&&&&&&&&&&&&&&&rslt.num[i + 1] += rslt.num[i] / 10;&&&&&&&&&&&&}&&&&&&&&&&&&else if(rslt.num[i] &= 10)&&&&&&&&&&&&{&&&&&&&&&&&&&&&&rslt.num.push_back(rslt.num[i] / 10);&&&&&&&&&&&&&&&&++&&&&&&&&&&&&}&&&&&&&&&&&&else&&&&&&&&&&&&{&&&&&&&&&&&&&&&&break;&&&&&&&&&&&&}&&&&&&&&&&&&rslt.num[i] %= 10;&&&&&&&&}&&&&&&&&return &&&&}&&&&//重载 += 运算符 使之支持用 += 进行高精度整数的加法运算&&&&BigInt operator += (const BigInt bInt)&&&&{&&&&&&&&*this = *this + bI&&&&&&&&return *this;&&&&}&&&&//重载 *= 运算符 使之支持用 *= 进行高精度整数的乘法运算&&&&BigInt operator *= (const BigInt bInt)&&&&{&&&&&&&&*this = *this * bI&&&&&&&&return *this;&&&&}&&&&//重载 & 运算符 使之支持使用 & 直接进行高精度整数的比较&&&&bool operator & (const BigInt bInt) const&&&&{&&&&&&&&vector&int&::size_type bLen(bInt.num.size());&&&&&&&&//长度不一样，直接返回大小结果&&&&&&&&if(num.size() != bLen) return num.size() & bL&&&&&&&&//由末位开始逐个比较&&&&&&&&for(vector&int&::size_type i(bLen - 1); i & 0; --i)&&&&&&&&{&&&&&&&&&&&&if(num[i] != bInt.num[i]) return num[i] & bInt.num[i];&&&&&&&&}&&&&&&&&return num[0] & bInt.num[0];&&&&}&&&&//重载其它比较运算符&&&&bool operator & (const BigInt bInt) const&&&&{&&&&&&&&return bInt & *this;&&&&}&&&&bool operator &= (const BigInt bInt) const&&&&{&&&&&&&&return !(*this & bInt);&&&&}&&&&bool operator &= (const BigInt bInt) const&&&&{&&&&&&&&return !(*this & bInt);&&&&}&&&&bool operator != (const BigInt bInt) const&&&&{&&&&&&&&return (*this & bInt) || (*this & bInt);&&&&}&&&&bool operator == (const BigInt bInt) const&&&&{&&&&&&&&return !(*this != bInt);&&&&}};//重载C++输入流运算符 使之支持C++IO流直接输入高精度整数istream& operator && (istream &in, BigInt& x){&&&&&&&&in &&&&&&x =&&&&return }//重载C++输出流运算符 使之支持C++IO流直接输出高精度整数ostream& operator && (ostream &out, BigInt& x){&&&&//以数字的正确顺序输出&&&&for(vector&int&::size_type i(x.num.size() - 1); i & 0; --i)&&&&{&&&&&&&&out && x.num[i];&&&&}&&&&out && x.num[0];&&&&return }
在本篇文章中我们将实现高精度乘法运算。
乘法和加法比起来就复杂很多了，我们知道乘法可以由加法直接实现（连续加因数2次因数1），在有我们之前的加法运算的基础的情况下，这种乘法运算极其简单便能实现（但是需要先做出高精度数比较运算，这是下节的内容了，不过这种方法并不明智，对于一个N位数乘以N位数的运算，其时间复杂度为O(10^N)，这个增长速度实在是太大了。
那么我们继续按照上次的思路，回到我们算乘法的竖式，看图1：
对于我们的乘法运算，按照计算机的运算思路，就是两个大循环，逐位相乘，最后再相加，然后转换为十进制数字，也就是进位，就能得到我们的结果了。
下面是乘法的实现方法：
123456789101112131415161718192021222324252627282930313233343536373839404142//重载 * 运算符 使之支持用 * 进行高精度整数的乘法运算BigInt operator * (const BigInt bInt) const{&&&&BigI&&&&//获取相乘的两个数字的长度&&&&vector&int&::size_type lenA(num.size()), lenB(bInt.num.size()), len(0);&&&&//逐位相乘&&&&for(vector&int&::size_type i(0); i & lenA; ++i)&&&&{&&&&&&&&for(vector&int&::size_type j(0); j & lenB; ++j)&&&&&&&&{&&&&&&&&&&&&if(rslt.num.size() - 1 & i + j)&&&&&&&&&&&&{&&&&&&&&&&&&&&&&++&&&&&&&&&&&&&&&&rslt.num.push_back(num[i] * bInt.num[j]);&& //增加一位&&&&&&&&&&&&}&&&&&&&&&&&&else&&&&&&&&&&&&{&&&&&&&&&&&&&&&&rslt.num[i + j] += num[i] * bInt.num[j];&&&&&&&&&&&&}&&&&&&&&}&&&&}&&&&//进位&&&&for(vector&int&::size_type i(0); i & ++i)&&&&{&&&&&&&&if(i + 1 & rslt.num.size())&&&&&&&&{&&&&&&&&&&&&rslt.num[i + 1] += rslt.num[i] / 10;&&&&&&&&}&&&&&&&&else if(rslt.num[i] &= 10)&&&&&&&&{&&&&&&&&&&&&rslt.num.push_back(rslt.num[i] / 10);&&&&&&&&&&&&++&&&&&&&&}&&&&&&&&else&&&&&&&&{&&&&&&&&&&&&break;&&&&&&&&}&&&&&&&&rslt.num[i] %= 10;&&&&}&&&&return }
依照惯例，给出完整的高精度整数类的代码，除了增加了乘法及乘法相关的运算符的重载外，为了防止乘法运算中相加过程中出现数值溢出，原先的short类型的容器修改为了int，这样可以确保不会出现乘法运算溢出的现象，同时在每次赋值和输入的最后，会自动去掉数字的前导零：
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179/*&* 高精度整数运算&* 实现存储及输入输出高精度整数的功能&* 实现两个正整数相加的功能&* 实现两个正整数相乘的功能&* BigInt.h&* @Blueve&* &* 0 1 1 2&*/#include &string&#include &vector&using namespace class BigInt{public:&&&&vector&int&& //存储高精度整数&&&&BigInt(string sNum = "0")&&&&{&&&&&&&&*this = sN&&&&}&&&&BigInt(int iNum)&&&&{&&&&&&&&*this = iN&&&&}&&&&//重载 = 运算符 使之支持用 = 直接用内置整型进行赋值&&&&BigInt operator = (const int iNum)&&&&{&&&&&&&&//清空原有数字&&&&&&&&num.erase(num.begin(), num.end());&&&&&&&&//以倒序存储高精度整数&&&&&&&&//将数字按位存数&&&&&&&&int tmp(iNum);&&&&&&&&while(tmp &= 10)&&&&&&&&{&&&&&&&&&&&&num.push_back(tmp % 10);&&&&&&&&&&&&tmp /= 10;&&&&&&&&}&&&&&&&&if(tmp != 0) num.push_back(tmp);&&&&&&&&else if(num.empty()) num.push_back(0);&&&&&&&&return *this;&&&&}&&&&//重载 = 运算符 使之支持用 = 直接用字符串进行赋值&&&&BigInt operator = (const string sNum)&&&&{&&&&&&&&//清空原有数字&&&&&&&&num.erase(num.begin(), num.end());&&&&&&&&//以倒序存储高精度整数&&&&&&&&for(string::size_type i(sNum.size() - 1); i & 0; --i)&&&&&&&&{&&&&&&&&&&&&num.push_back(sNum[i] - '0');&&&&&&&&}&&&&&&&&num.push_back(sNum[0] - '0');&&&&&&&&//清除前导零&&&&&&&&for(vector&int&::size_type i(num.size() - 1); num[i] == 0 && i & 0; --i)&&&&&&&&{&&&&&&&&&&&&num.pop_back();&&&&&&&&}&&&&&&&&return *this;&&&&}&&&&//重载 = 运算符 使之支持用 = 直接高精度整数进行赋值&&&&BigInt operator = (const BigInt bInt)&&&&{&&&&&&&&//清空原有数字&&&&&&&&num.erase(num.begin(), num.end());&&&&&&&&//以倒序存储高精度整数&&&&&&&&for(vector&int&::size_type i(0); i & bInt.num.size(); ++i)&&&&&&&&{&&&&&&&&&&&&num.push_back(bInt.num[i]);&&&&&&&&}&&&&&&&&return *this;&&&&}&&&&//重载 + 运算符 使之支持用 + 进行高精度整数的加法运算&&&&BigInt operator + (const BigInt bInt) const&&&&{&&&&&&&&BigI&&&&&&&&//获取相加的两个数字的长度&&&&&&&&vector&int&::size_type lenA(num.size()), lenB(bInt.num.size()),&&&&&&&&lng = (lenA & lenB ? lenA : lenB);&& //记录长度较长的&&&&&&&&//逐位相加&&&&&&&&for(vector&int&::size_type i(0); i & ++i)&&&&&&&&{&&&&&&&&&&&&int tmp(rslt.num[rslt.num.size() - 1]); //获取当前位原有的数字&&&&&&&&&&&&//相加&&&&&&&&&&&&if(i & lenA) tmp += num[i];&&&&&&&&&&&&if(i & lenB) tmp += bInt.num[i];&&&&&&&&&&&&rslt.num[rslt.num.size() - 1] = tmp % 10;&& //存入&&&&&&&&&&&&rslt.num.push_back(tmp / 10);&& //进位&&&&&&&&}&&&&&&&&if(rslt.num[lng] == 0) rslt.num.pop_back(); //末位为0则弹出&&&&&&&&return &&&&}&&&&//重载 * 运算符 使之支持用 * 进行高精度整数的乘法运算&&&&BigInt operator * (const BigInt bInt) const&&&&{&&&&&&&&BigI&&&&&&&&//获取相乘的两个数字的长度&&&&&&&&vector&int&::size_type lenA(num.size()), lenB(bInt.num.size()), len(0);&&&&&&&&//逐位相乘&&&&&&&&for(vector&int&::size_type i(0); i & lenA; ++i)&&&&&&&&{&&&&&&&&&&&&for(vector&int&::size_type j(0); j & lenB; ++j)&&&&&&&&&&&&{&&&&&&&&&&&&&&&&if(rslt.num.size() - 1 & i + j)&&&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&++&&&&&&&&&&&&&&&&&&&&rslt.num.push_back(num[i] * bInt.num[j]);&& //增加一位&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&else&&&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&rslt.num[i + j] += num[i] * bInt.num[j];&&&&&&&&&&&&&&&&}&&&&&&&&&&&&}&&&&&&&&}&&&&&&&&//进位&&&&&&&&for(vector&int&::size_type i(0); i & ++i)&&&&&&&&{&&&&&&&&&&&&if(i + 1 & rslt.num.size())&&&&&&&&&&&&{&&&&&&&&&&&&&&&&rslt.num[i + 1] += rslt.num[i] / 10;&&&&&&&&&&&&}&&&&&&&&&&&&else if(rslt.num[i] &= 10)&&&&&&&&&&&&{&&&&&&&&&&&&&&&&rslt.num.push_back(rslt.num[i] / 10);&&&&&&&&&&&&&&&&++&&&&&&&&&&&&}&&&&&&&&&&&&else&&&&&&&&&&&&{&&&&&&&&&&&&&&&&break;&&&&&&&&&&&&}&&&&&&&&&&&&rslt.num[i] %= 10;&&&&&&&&}&&&&&&&&return &&&&}&&&&//重载 += 运算符 使之支持用 += 进行高精度整数的加法运算&&&&BigInt operator += (const BigInt bInt)&&&&{&&&&&&&&*this = *this + bI&&&&&&&&return *this;&&&&}&&&&//重载 *= 运算符 使之支持用 *= 进行高精度整数的乘法运算&&&&BigInt operator *= (const BigInt bInt)&&&&{&&&&&&&&*this = *this * bI&&&&&&&&return *this;&&&&}};//重载C++输入流运算符 使之支持C++IO流直接输入高精度整数istream& operator && (istream &in, BigInt& x){&&&&&&&&in &&&&&&x =&&&&return }//重载C++输出流运算符 使之支持C++IO流直接输出高精度整数ostream& operator && (ostream &out, BigInt& x){&&&&//以数字的正确顺序输出&&&&for(vector&int&::size_type i(x.num.size() - 1); i & 0; --i)&&&&{&&&&&&&&out && x.num[i];&&&&}&&&&out && x.num[0];&&&&return }
在解决了高精度整数的输入、存储以及输出的问题后，我们终于开始正式思考“运算”部分的实现。
加法是最简单的一种四则运算，也是我们小学时数学最先就学到的运算规则，对于内置的整数类型而言，计算机通过二进制的电位运算可以快速的得到结果，而对于我们按位存入的高精度整数而言，要想对其进行加法运算，我们就需要返璞归真，首先，我们来回忆下小学时的加法，看图1：
从个位开始相加，结果放在横线下，如果相加的结果超过10，则进1到下一位。
没错，我们就是要所要依靠的就是这样一个简单的规则！
首先考虑到我们存储数字的方式：如果两个数字位数不同，则会出现超过数位的数字再相加时vector out of range的情况，所以我们要把两个数字一个一个加到结果的位置上（比如图1的个位，结果位原先是0，先把4加到结果位，结果位变为4，然后再把2加到结果为，变为6），这样可以方便我们对两个加数的各个位的情况进行把握。
下面就是加法运算的具体实现方法：
1234567891011121314151617181920//重载 + 运算符 使之支持用 + 进行高精度整数的加法运算BigInt operator + (const BigInt bInt){&&&&BigI&&&&//获取相加的两个数字的长度&&&&vector&short&::size_type lenA(num.size()), lenB(bInt.num.size()),&&&&lng = (lenA & lenB ? lenA : lenB);&& //记录长度较长的&&&&//逐位相加&&&&for(vector&short&::size_type i(0); i & ++i)&&&&{&&&&&&&&int tmp(rslt.num[rslt.num.size() - 1]); //获取当前位原有的数字&&&&&&&&//相加&&&&&&&&if(i & lenA) tmp += num[i];&&&&&&&&if(i & lenB) tmp += bInt.num[i];&&&&&&&&rslt.num[rslt.num.size() - 1] = tmp % 10;&& //存入&&&&&&&&rslt.num.push_back(tmp / 10);&& //进位&&&&}&&&&if(rslt.num[lng] == 0) rslt.num.pop_back(); //末位为0则弹出&&&&return }
在此之后，我还对“+=”运算符进行了重载，有了刚才的“+”，这个运算符的重载异常的简单。下面给出加入了加法运算的高精度运算类的完整代码：
对上一次的代码有所改进，使高精度运算可以直接接受内置型整数（你把int都换成BigInt不会有什么区别，该咋用咋用，不过截止到目前为止，你只能用加法:P），体会下C++的方便吧！一个符号重载之后可以到处用呀~~
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123/*&* 高精度整数运算&* 实现存储及输入输出高精度整数的功能&* 实现两个正整数相加的功能&* BigInt.h&* @Blueve&* &* 0 0 1 1&*/#include &string&#include &vector&using namespace class BigInt{public:&&&&vector&short&&&& //存储高精度整数&&&&BigInt(string sNum = "0")&&&&{&&&&&&&&*this = sN&&&&}&&&&BigInt(int iNum)&&&&{&&&&&&&&*this = iN&&&&}&&&&//重载 = 运算符 使之支持用 = 直接用内置整型进行赋值&&&&BigInt operator = (const int iNum)&&&&{&&&&&&&&//清空原有数字&&&&&&&&num.erase(num.begin(), num.end());&&&&&&&&//以倒序存储高精度整数&&&&&&&&//将数字按位存数&&&&&&&&int tmp(iNum);&&&&&&&&while(tmp &= 10)&&&&&&&&{&&&&&&&&&&&&num.push_back(tmp % 10);&&&&&&&&&&&&tmp /= 10;&&&&&&&&}&&&&&&&&if(tmp != 0) num.push_back(tmp);&&&&&&&&else if(num.empty()) num.push_back(0);&&&&&&&&return *this;&&&&}&&&&//重载 = 运算符 使之支持用 = 直接用字符串进行赋值&&&&BigInt operator = (const string sNum)&&&&{&&&&&&&&//清空原有数字&&&&&&&&num.erase(num.begin(), num.end());&&&&&&&&//以倒序存储高精度整数&&&&&&&&for(string::size_type i(sNum.size() - 1); i & 0; --i)&&&&&&&&{&&&&&&&&&&&&num.push_back(sNum[i] - '0');&&&&&&&&}&&&&&&&&num.push_back(sNum[0] - '0');&&&&&&&&return *this;&&&&}&&&&//重载 = 运算符 使之支持用 = 直接高精度整数进行赋值&&&&BigInt operator = (const BigInt bInt)&&&&{&&&&&&&&//清空原有数字&&&&&&&&num.erase(num.begin(), num.end());&&&&&&&&//以倒序存储高精度整数&&&&&&&&for(vector&short&::size_type i(0); i & bInt.num.size(); ++i)&&&&&&&&{&&&&&&&&&&&&num.push_back(bInt.num[i]);&&&&&&&&}&&&&&&&&return *this;&&&&}&&&&//重载 + 运算符 使之支持用 + 进行高精度整数的加法运算&&&&BigInt operator + (const BigInt bInt)&&&&{&&&&&&&&BigI&&&&&&&&//获取相加的两个数字的长度&&&&&&&&vector&short&::size_type lenA(num.size()), lenB(bInt.num.size()),&&&&&&&&lng = (lenA & lenB ? lenA : lenB);&& //记录长度较长的&&&&&&&&//逐位相加&&&&&&&&for(vector&short&::size_type i(0); i & ++i)&&&&&&&&{&&&&&&&&&&&&int tmp(rslt.num[rslt.num.size() - 1]); //获取当前位原有的数字&&&&&&&&&&&&//相加&&&&&&&&&&&&if(i & lenA) tmp += num[i];&&&&&&&&&&&&if(i & lenB) tmp += bInt.num[i];&&&&&&&&&&&&rslt.num[rslt.num.size() - 1] = tmp % 10;&& //存入&&&&&&&&&&&&rslt.num.push_back(tmp / 10);&& //进位&&&&&&&&}&&&&&&&&if(rslt.num[lng] == 0) rslt.num.pop_back(); //末位为0则弹出&&&&&&&&return &&&&}&&&&//重载 += 运算符 使之支持用 += 进行高精度整数的加法运算&&&&BigInt operator += (const BigInt bInt)&&&&{&&&&&&&&*this = *this + bI&&&&&&&&return *this;&&&&}};//重载C++输入流运算符 使之支持C++IO流直接输入高精度整数istream& operator && (istream &in, BigInt& x){&&&&&&&&in &&&&&&x =&&&&return }//重载C++输出流运算符 使之支持C++IO流直接输出高精度整数ostream& operator && (ostream &out, BigInt& x){&&&&//以数字的正确顺序输出&&&&for(vector&short&::size_type i(x.num.size() - 1); i & 0; --i)&&&&{&&&&&&&&out && x.num[i];&&&&}&&&&out && x.num[0];&&&&return }
在解题过程中，经常会出现需要运算的数据超过系统内置的整型范围的情况，在这种时候我们就需要用到高精度运算算法，我将分几篇文章来解释，如何实现高精度运算，并且我将会将高精度运算封装为一个命名为BigInt的高精度整数类，方便未来的使用。
在本篇中，主要实现的是高精度整数的存储、输入与输出。
在给出具体的实现之前，我先介绍一点预备知识，关于C++标准库vector。
vector这个词在中提及过，vector是C++提供的一种顺序容器，而对于vector这种容器来说，其特点就是支持快速的随机访问（想一想数组通过下标值访问的方式），作为一种可变长的容器，我们可以把它当作一种“高端的数组”，用vector来存储高精度整数的好处在于可以解决由大整型数组来存数高精度整数时所造成的空间浪费问题。
我们对于高精度整数的存储方式是按位存储，为了避免运算的时候对齐各个位时产生麻烦，所以我们从个位开始存储，也就是说，在vector容器中存储的数字顺序，与你实际看到的数字顺序是正好相反的。
下面就给出具体的实现方法，我在关键的位置都有详尽的注释来说明：
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980/*&* 高精度整数运算&* 实现存储及输入输出高精度整数的功能&* BigInt.h&* @Blueve&* &* 0 0 0 0&*/#include &string&#include &vector&using namespace class BigInt{public:&&&&vector&short&&&& //存储高精度整数&&&&BigInt(): num(0) {}&&&&BigInt(string sNum)&&&&{&&&&&&&&(*this) = sN&&&&}&&&&//重载 = 运算符 使之支持用 = 直接用字符串进行赋值&&&&BigInt operator = (const string sNum)&&&&{&&&&&&&&//清空原有数字&&&&&&&&num.erase(num.begin(), num.end());&&&&&&&&//以倒序存储高精度整数&&&&&&&&for(string::size_type i(sNum.size() - 1); i & 0; --i)&&&&&&&&{&&&&&&&&&&&&num.push_back(sNum[i] - '0');&&&&&&&&}&&&&&&&&num.push_back(sNum[0] - '0');&&&&&&&&return (*this);&&&&}&&&&//重载 = 运算符 使之支持用 = 直接高精度整数进行赋值&&&&BigInt operator = (const BigInt bInt)&&&&{&&&&&&&&//清空原有数字&&&&&&&&num.erase(num.begin(), num.end());&&&&&&&&//以倒序存储高精度整数&&&&&&&&for(vector&short&::size_type i(0); i & bInt.num.size(); ++i)&&&&&&&&{&&&&&&&&&&&&num.push_back(bInt.num[i]);&&&&&&&&}&&&&&&&&return (*this);&&&&}};//重载C++输入流运算符 使之支持C++IO流直接输入高精度整数istream& operator && (istream &in, BigInt& x){&&&&&&&&in &&&&&&x =&&&&return }//重载C++输出流运算符 使之支持C++IO流直接输出高精度整数ostream& operator && (ostream &out, BigInt& x){&&&&//若为空则输出 0&&&&if(x.num.size() == 0)&&&&{&&&&&&&&out && 0;&&&&}&&&&else&&&&{&&&&&&&&//以数字的正确顺序输出&&&&&&&&for(vector&short&::size_type i(x.num.size() - 1); i & 0; --i)&&&&&&&&{&&&&&&&&&&&&out && x.num[i];&&&&&&&&}&&&&&&&&out && x.num[0];&&&&}&&&&return }
TA的最新馆藏[转]&[转]&[转]&[转]&[转]&[转]&