高精度整数算法(IV) 除法及取余
++++++++++++++++++++++++++++++++++++++++++

除法和取余是两个姐妹运算，二者的运算过程完全一样，不同的只是取哪一个结果而已。它们俩是高精度整数算法中编程难度最高的运算。


BigInt除法运算
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

我们先看看十进制整数除法的竖式运算是怎样的。例如我们要计算54321÷33=1646...3，那么我们首先从被除数54321的最高位5开始寻找第一段比33大的部分，可以找到(54)就比33大，所以就从54开始逐位向后进行部分除法，最终得到结果。

我们的算法要模拟这样一个过程，有一个地方需要按照计算机的习惯来稍微改造一下。就是在第一次部分除法的时候，人眼可以快速地找到第一个大于除数的部分。但计算机可没有这么聪明，这是个小麻烦，对此有两种解决方法。第一种，由于第一段比除数大的部分肯定至少和除数位数相同，至多比除数多一位，所以我们可以根据除数的长度，先取相同长度的一段进行比较，如果不行就再添一位，这样就可以了。第二种方法是我们干脆不要找了，直接从被除数的最高位开始做部分除法，这样无非就是商会多出若干个前导的零来，我们最后把它们去掉就行了。

看上去第二种方法有可能多做好几次比较运算，最后还要去除最高位上的若干个零。但是第二种方法可以让代码变得统一和简洁，而比较运算我们已经知道了，其实运行速度很快的，去除商最高位的前导零采用 ``vector`` 的 ``pop_back()`` 函数，速度也是极快的，所以在实际应用中第二种方法并不比第一种慢多少。这里我们选择第二种方法，在把算法和程序代码理解清楚后，请自行尝试第一种方法。

然后我们把十进制的按位运算扩展为万进制的按节运算就可以了，方法上是完全一致的。请看一下图示的例子：

.. image:: ../../images/315_bigint_div.png

接下来我们来实现 ``BigInt`` 的除法运算，和乘法一样，一共两种，重载函数的原型分别如下：

.. code-block:: c++

   struct BigInt {
           // ...
           BigInt operator/(const BigInt &a) const;
           BigInt &operator/=(const BigInt &a);
           // ...
   };

因为除法和乘法一样，也是不能直接在被除数本身上进行运算的，所以我们也先实现普通的 ``/`` 运算，然后利用它来实现 ``/=`` 运算。

除法的过程相对复杂，特别容易混乱，我们在开始编码之前先还是理一理思路。首先来看看要用到哪些变量：

* 被除数是 ``*this``\ ，它可以直接访问内部成员变量 ``_s``\ ，但由于整个函数是有 ``const`` 后缀修饰的，所以不能修改。
* 除数是形参 ``a``\ ，它是常引用，也不能修改。
* 我们需要一个临时变量 ``BigInt q`` 用于存放商。因为我们知道商的长度不大于被除数的长度，所以我们可以在计算开始前将其设为与被除数相同长度并且全零。
* 我们显然还需要一个临时的变量 ``BigInt part`` 用来存放每一次部分除法的部分被除数。

下面是除法的实现代码：

.. literalinclude:: ../../codes/312_bigint.cpp
   :language: c++
   :lines: 229-253

.. note::

   1. 还记得那个 ``throw`` 命令吗？不记得的话可以回到顺序表这一节去看一看，那里有简单的介绍。
   2. C++所有顺序容器的元素下标都是从0开始计数的，用来指示当前部分除法所处位置的变量 ``i`` 在进入循环前的初始值 ``_s.size()`` 是指向被除数最高节后面的那个位置的。因此在循环的条件表达式里我们使用了前置 ``--`` 运算，这样第一次循环条件判断的时候它已经指向了被除数的最高节，循环也就相应地从最高节开始进行部分除了，同时每一次部分除的商也就顺理成章的由 ``i`` 来指示所在位置，即 ``q._s[i]``\ 。整个过程中 ``i`` 会始终跟随进度准确地指向合适的位置。一直到位置0，也就是最低节也完成了部分除之后，再一次循环条件判断时，\ ``i`` 先完成减一，变成-1，循环便随之结束。
   3. 进入循环前把 ``part`` 设为0，计算过程中每次部分除之后余数就保留在 ``part`` 里，所以当某次部分除是整除时，\ ``part`` 会变成0。
   4. 每一次计算部分除时先把被除数当前位置的节 ``_s[i]`` 移入 ``part`` 的最低节，和前一次的余数拼接成这一次的被除数。这个过程要分为两种情况：\ ``part != 0`` 时应把 ``_s[i]`` 的值插入到 ``part._s`` 的头部；\ ``part == 0`` 时，则应直接令 ``part._s[0] = _s[i]``\ ，否则就会出现一个多余的前导0，这会给后面的运算带来不必要的麻烦。
   5. 部分除 ``part / a`` 本身就是两个 ``BigInt`` 变量的除法，这就出现了用自己来实现自己的问题。所以我们不是真正地去做除法，而是用多次循环减法来模拟除法：循环地做 ``part - a`` 直至 ``part < a``\ ，每减一次，对应的部分商加1，减了多少次就加了多少个1。由于我们事先把 ``q`` 设为了全0，所以这个循环可以保证得到正确的部分商，如果 ``part`` 一开始就小于 ``a`` 的话，这个循环根本不会被执行，部分商也就保持为0。可以看出这个过程是准确而完备的。
   6. 最后不要忘记删除 ``q`` 中多余的前导0。

高精度算法这种本身比较复杂，又涉及许多编程中的语言运用技巧，在阅读的时候务必用几个具体的数字手工模拟运行一下。在看懂之后还要自己手打一遍，测试一下。


BigInt取余运算
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

除法运算搞定之后，取余就自然搞定了。其实我们已经看到了，除法运算时那个用于部分除的临时变量 ``part`` 在整个除法运算结束之后里面存放的就是余数，把它返回出来就OK了，就这么简单！整个过程和除法完全一样。而且我们现在已经不需要计算商了，所以在运算过程中不需要那个保存商的变量 ``q``\ 。另外我们把变量 ``part`` 改名为 ``r``\ ，表示余数（remainder）。

取余运算符重载为成员函数的原型：

.. code-block:: c++

   struct BigInt {
           // ...
           BigInt operator%(const BigInt &a) const;
           BigInt &operator%=(const BigInt &a);
           // ...
   };

取余运算的具体函数定义代码这里就不单独给出了，因为我们接下来将把整个 ``BigInt`` 的代码完整地展示出来，整整四节的成果：

BigInt结构的完整代码
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

.. literalinclude:: ../../codes/312_bigint.cpp
   :language: c++
   :lines: 1-270

.. attention::

   高精度算法是算法编程普及组阶段的难点之一，涉及比较复杂的模拟算法，很容易考虑不周引入bug；涉及比较复杂的C++模板容器应用，对 ``vector`` 容器要有相当的熟悉度；涉及到初步的C++面向对象编程，对成员变量、成员函数、静态成员、构造函数、函数重载、运算符重载等概念要有所了解，虽然还只是用struct来模拟初级阶段的面向对象，但还是有许多概念要理解，有许多固定写法要记住。

   不幸的是，高精度算法几乎是提高组的必考知识，普及组的难度越来越大，也不排除会出现在普及组的可能性。高精度算法难学难掌握，在考试现场很难三次以内完全写对，一定要完全理解并多次动手实验才行。

   幸运的是，在C++语言强大的 ``vector`` 容器、面向对象等高阶技能的加持下，现在写高精度已经比当年用纯C和数组来写简单了许多许多。而且实际的题目中如果要用到高精度算法，是极少要求完整实现所有运算的，而且往往会在数据取值范围方面有一定的限制，使得计算过程可以简化。后面一节我们就将见到这样一个实际的题目。