高精度整数算法(II) 加法与乘法 ++++++++++++++++++++++++++++++++++++++++++ 我们已经搭建好了 ``BigInt`` 的基本框架，实现了数据存储、初始化、赋值和输入输出功能。接下来我们就要逐步实现运算功能了，首先来看最常用也是相对较简单的加法和乘法运算。 实现加法和乘法运算的基本思路是模拟竖式运算的手算过程。我们采用万进制，每一个节看作是万进制整数的一个位，仿照小学阶段学过的竖式加法和乘法运算规则，最低节对齐后由低向高进行运算。 BigInt加法运算 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 十进制下正整数加法的竖式运算规则是最简单的，两个加数最低位对齐，然后开始由低位向高位逐位做加法。每个位上由两个加数该位上的数字以及从低位进位来的数字三者相加，相加之和取其个位数作为该位的结果，如果超过10，则向更高一位进1。最终得到的和的长度可能和两个加数中较大的那个相同，或者多一位。 ``BigInt`` 的万进制正整数加法和上面所描述的十进制情况并没有本质的区别，只是“位”变成了“节”，每个节上相加之和保留低四位，也就是除一万的余数，进位则是最高位，也就是除一万的商，同样进位数最大只可能为一。 要模拟上面这样一个过程并不难。我们在设计 ``BigInt`` 的数据结构时使用了“小端序”存放各节，所以低位对齐是一件自然已经做好的事情，只要将两个加数各自从头到尾的各节相加，取结果，生成进位就可以了。两个加数的节数不同时，较短的那个加数高位上缺失的节视为0。 例如计算99998765432101234567+9999123456789012的过程如下： .. code-block:: none 9999|8765|4321|0123|4567 +) 9999|1234|5678|9012 ------------------------------ 1|0000|8764|5555|5802|3579 下面我们来具体实现加法运算。我们将重载所有的四种加法运算：``+, +=, 前置++, 后置++``，但实际解决问题时往往只需其中一种就够了。 既然我们要同时实现 ``+`` 和 ``+=`` 两种运算，那么按照代码复用的原则，我们可以只对其中一个编写真正的运算程序，而另一个则利用它来完成自己的功能。 ``+`` 和 ``+=`` 两个运算符重载的成员函数原型为： .. code-block:: c++ struct BigInt { // ... BigInt operator+(const BigInt &a) const; BigInt &operator+=(const BigInt &a); // ... }; 二者的共同点是都只接受一个常量引用参数 ``const BigInt &a``\ ，它就是要和自己相加的那个加数。采用常引用确保了这个参数不光可以是 ``BigInt`` 变量，而且可以是任何能被 ``unsigned long long`` 兼容的内置整型变量、常量和字面量。这是因为C++对于常引用形参会在类型不匹配时自动尝试去做类型转换，而我们的 ``BigInt`` 恰好有一个能接受这种类型的构造器，所以C++能够把这些值默默地转为一个 ``BigInt`` 变量再传给形参。 *再次强调，凡是函数参数是派生数据类型的，一定要传引用，如果函数运行时不应该改变参数的值的，一定要修饰成常引用！* .. attention:: 聪明如你，读到这里可能会认为既然这样，那么重载过加法运算符之后我们的 ``BigInt`` 是不是不光能和内置整型数做加法，而且还能和字符串做加法呢？毕竟我们还有一个接受 ``string`` 型参数的构造器。很遗憾，答案是否定的。前一节我们已经看到过了 ``BigInt b = "888";`` 这样的操作会被C++拒绝，理由是不支持这样的类型转换。这里也一样，\ ``b + "888"`` 这样的操作也会被C++以相同的理由拒绝。这是因为字符串本身也是一种派生数据类型，而那种默默完成的隐式类型转换只支持内置数据类型。 再看二者的不同点。第一个不同点是 ``+`` 运算符重载的成员函数在函数参数表后面有一个 ``const`` 的修饰。被这样修饰过的成员函数叫做\ :strong:`常成员函数`\ 。这是成员函数才有的特性，普通的函数是没有这种操作的。这个跟在函数参数表后面的 ``const`` 其实修饰的是隐藏的 ``this`` 指针，即调用者自己，所以常成员函数不允许修改自己成员变量的值。而我们知道，单纯的加法运算确实就是不允许修改任何一个加数的值的。 第二个不同点是 ``+=`` 运算返回一个引用，而 ``+`` 运算则是返回一个值。这是因为单纯的加法运算不在任何一个加数上进行运算，它一定是生成一个临时的 ``BigInt`` 变量来存放运算结果。而临时变量是不可以用引用来返回的，必须返回它的值。``+=`` 运算就不同了，它简单地把参数 ``a`` 加到自己身上，然后以引用方式返回 ``*this`` 就可以了。所以 ``+=`` 运算会比 ``+`` 运算高效一些，因为它的参数和返回值都是引用形式，不会产生数据复制。 那么如果用 ``+=`` 来实现具体的加法运算，然后用它来完成 ``+`` 的功能，这样会不会比反过来做更加高效呢？其实两种方式是一样的。我们来对比一下就知道了： 1. ``+`` 调用 ``+=`` 时，首先要把自己的值复制一个备份出来，然后用这个备份去调用 ``+=``\ ，完成之后再以复制值的方式返回结果，总共做了两次数据复制。 2. ``+=`` 调用 ``+`` 时，普通加法运算结束后以复制值的方式返回结果，然后这个结果要复制给 ``*this``\ ，一样是总共两次数据复制。 所以对于加法运算，这种谁复用谁的选择是没有太大意义的，个人喜好而已。真正的加法运算过程都是一样的。我们这里选择用 ``+=`` 来做真正的加法运算，然后 ``+`` 运算利用 ``+=`` 运算来完成。下面是这两个成员函数的具体代码： .. literalinclude:: ../../codes/312_bigint.cpp :language: c++ :lines: 117-138 .. note:: 核心的加法程序是在 ``+=`` 的函数中实现的，\ ``+`` 函数只是把传入的加数复制一份，然后调用 ``+=`` 把自己的值加到这个复制出来的加数上去，再返回得到的和。这样就确保了两个加数自己不会被改变。 在 ``+=`` 函数中，有一个很隐蔽的细节问题，容易引发非常隐蔽的bug。我们的程序是把传入的加数直接加到自身上去，当遇到 ``a += a`` 这样的把自己加到自己上去这种操作时，传入的那个加数其实就是自己的引用。所以我们在做每一节上的部分加时，必须先加两个节的数值，然后再加从前面过来的进位。否则如果先把进位加上去，那么其实加数 ``a`` 上这个节也是被加了进位的，这样进位数就会被加两遍。 .. admonition:: 练习 理解上面的两个加法运算函数，然后做以下练习：在 ``+`` 函数中实现加法运算，再利用 ``+`` 函数实现 ``+=`` 运算。 接下来我们看看怎么实现 ``++`` 运算。原理上已经非常简单了，``++`` 运算也就是调用 ``+= 1`` 然后返回结果罢了。但是 ``++`` 运算有前置和后置两种，二者的运算符是一样的，为了能够区分前置和后置，二者有不同的重载函数原型，这两个原型比较特殊： .. code-block:: c++ struct BigInt { // ... BigInt &operator++(); // 前置++ BigInt operator++(int); // 后置++ // ... }; 具体实现的代码倒很简单，因为同样可以利用已经实现的 ``+=`` 运算： .. literalinclude:: ../../codes/312_bigint.cpp :language: c++ :lines: 140-147 .. note:: 从它们的代码可以明显看出，前置运算非常高效，它直接在自身做 ``+= 1`` 运算，并且返回自身的引用。我们的 ``+=`` 代码也是没有数据复制的非常高效的，所以前置 ``++`` 整个过程没有产生一次数据复制，直接返回自身的引用。 而后置运算就不同了，因为它要返回的是自己的原值，所以它必须先把自己的原值复制一份才能去做 ``+= 1`` 运算，最后还必须以值的方式返回自己复制下来的原值，所以后置 ``++`` 整个过程发生了两次数据复制。 这就是为什么常有人说前置比后置更快的原因。事实上如果是内置数据类型，比如最常见的 ``int``\ ，两次数据复制造成的时间增量是完全可以忽略不计的。但是对于 ``BigInt`` 这样的可能会数据量很大的自定义数据类型，两次复制确实是会引起一些性能差异的。所以在实际编程时遇到这种场景，尽量用前置运算确实是一个比较好的习惯。 另外，由于前置运算返回的是引用，所以它的返回值是可以被修改的。例如你可以写这样的连续自增运算：\ ``++(++(++i))``\ 。但后置运算返回的是值，所以不能这样连续使用。不过要知道，这样的语句在实际编程中是不提倡的，代码风格要以朴素易懂为先。 BigInt乘法运算 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 模拟竖式整数乘法时，同样先低位对齐，然后从乘数的最低节开始逐节与另一个乘数整体相乘，每次得到的部分积右移相应的节数后加到前一次得到的部分结果上去。 由于我们使用万进制，所以模拟乘法时会有一个非常好用的便利。节与节相乘的乘积不会造成 ``int`` 溢出，不需要引入更大类型的中间变量。结果除万取模就是该节的积，取商就是进位数。两个节都取最大值时，9999×9999=99980001，结果记1进9998。这是节乘会产生的最大进位数。高精乘法运算中最基本的部分运算就是节乘，再加上来自前一次的进位数。根据这个运算规律，我们可以发现一次节乘会产生的进位不超过9998。这就很好地保证了 ``int`` 型在整个高精乘法过程中的有效性，我们可以放心地基于它来模拟竖式乘法。 C++中与乘法有关的运算有两个，普通乘法 ``*`` 和自乘 ``*=``\ ，只要实现了其中一个，另一个就可以利用它来实现。重载这两个运算符的成员函数原型如下： .. code-block:: c++ struct BigInt { // ... BigInt operator*(const BigInt &a) const; BigInt &operator*=(const BigInt &a); // ... }; 那么是不是和加法的情形一样，实现其中哪一个对效率并无影响呢？其实乘法是不一样的。原因是乘法不像加法一样可以两个加数从低位到高位循环一遍就可以完成的。参考竖式乘法的手算过程，如果下面的那个乘数有 :math:`n` 位，那么需要做 :math:`n` 次部分乘法，然后把所有这些部分乘法的结果按规则移位后加起来得到最终的积。所以乘法不能在其中一个乘数上直接完成运算，必须引入一个中间变量来累加每一次部分乘法的结果。 如果我们实现 ``*=`` 运算，因为不能直接改写自身，所以要先把自身的值复制一份出来：\ ``BigInt f1 = *this;``\ ，然后用 ``f1`` 来进行计算，中间结果就直接写进 ``*this`` 中去。但是考虑到有可能出现自己和自己的自乘：\ ``a *= a``\ ，所以其实还需要再复制一份传入的乘数值：\ ``BigInt f2 = a;``\ 。这样即使 ``a`` 就是 ``*this`` 也没有关系了，我们用 ``f1`` 和 ``f2`` 来进行计算，最终结果就在 ``*this`` 中，返回自己的引用就可以了。所以实现 ``*=`` 需要两次数据复制。而 ``*`` 运算可以这样实现：先把自身复制一份，然后用这个复制品去完成 ``*=`` 运算，最后把得到的结果以值的方式返回，这里也有两次数据复制。所以这种方式一共产生了四次数据复制。 如果我们实现 ``*`` 运算，整个计算过程不需要进行数据复制，生成一个临时变量来接收运算结果即可，但是最后要以值的形式返回，所以还是有一次数据复制。\ ``*=`` 运算中则直接用自身去做自乘，然后赋值回自身，返回引用：\ ``return *this = *this * a;``\ 。这里只有一次赋值，即一次数据复制。这种方式一共产生两次数据复制，比前一种方式少一倍！ 所以我们当然选择实现 ``*`` 运算啦： .. literalinclude:: ../../codes/312_bigint.cpp :language: c++ :lines: 149-172 .. note:: 上述这个乘法运算的代码是非常直接地对竖式乘法的模拟，并没有什么特殊之处。和手算唯一的不同是，我们不会把所有部分积全部乘完然后再一起相加，而是乘一次就加一次，这样效率和内存消耗都会好很多。 请务必读懂理解上面的算法，尤其是要搞清楚，部分积相加时的左移是怎样实现的。最后请编写在 ``*=`` 中进行乘法运算的方式，这是必要的练习。