高精度整数算法(III) 减法与比较
++++++++++++++++++++++++++++++++++++++++++

“类补码”的减法运算
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

首先我们来看看减法运算。算术上的减法竖式运算本身是比较简单的，相信大家都非常熟悉。现在将其扩展到万进制，只是把十进制的位扩展成了万进制的节，把基从十变成了万而已。举一个简单的例子：100000001-11111，列出竖式计算如下：

.. code-block:: none

         1|0000|0001
   -)         1|1111
   -----------------
           9998|8890

减数和被减数低位对齐，然后从低到高对应的各节做部分减，最终得到两者之差。当对应的节上减数大于被减数时，被减节要向更高的节借一个1，也就是被减节的数值加上一个基（一万）。被借的节数值则相应减一，如果被借的节本身是0，那么它进一步向它的更高一节借1，于是它变成一万，减1后变成9999。如此循环直至借到一个1为止。

这是通常的正整数竖式相减的规则。但是存在一个严重的问题，即如果是小数减大数怎么办？按照数学的规则，小数减大数的差为负数，其绝对值等于大数减小数的差。例如1-9=-8。但是如果我们尝试用竖式减法去计算小数减大数，就会发现这种算术运算方法行不通，原因是一定会出现借位而且确实借不到！这就是正整数减法要解决的最大的问题。

在实际应用中，根据解决问题的需要，常见两种方式来处理正整数减法中小数减大数的问题。

1. 有些问题实际上要求的是两个数之间的差异值，也就是说它不关心谁大谁小，只关心二者差多少。这种情况常见于求距离一类的问题，它们很容易处理，在计算之前判断一下两个数的大小，然后用大的那个去减小的那个就可以了。这种解决方法其实不需要在减法运算中去实现，算法程序在进行减法之前先进行大小判断即可。

2. 另一种常见处理方法是采用类似C++对内置无符号整型数小减大的处理，计算出一种类似补码的差，我叫它“类补码”的差。下面我们将详细讲解这种方法。

先请试一下这样一段简单的程序：

.. code-block:: c++

   #include <iostream>
   
   int main()
   {
           unsigned int a = 10, b = 100, c = a - b;
           std::cout << c << std::endl;
   
           return 0;
   }

运行后得到的结果是4294967206！什么鬼？其实这个差就是真正的差-90，不过是用所谓二进制补码来表示的。-90的32位补码如果视为正数就是2\ :superscript:`32`-90=4294967206。关于补码的详细知识在学习算法编程的初期可以不用深究，有兴趣可以去查阅计算机原理的相关资料。现在我们要了解的是补码是怎样产生出来的，高精度减法怎样模仿它，以及得到的“类补码”的差可以怎样用。

我们先来看计算机的二进制补码是怎样产生的。在计算机内部，每一种整数都有规定的位数，\ ``char`` 占8位、\ ``short`` 是16位，目前常见的64位操作系统下 ``int`` 占据32位、\ ``long long`` 则是64位。在小数减大数的时候，必然会发生借位借不到的情况，即一直向高位不断去借，但直到超过位数限制还是借不到。这时计算机会做一件看上去相当不负责任的事情：假装借到了！它会在超过自己长度限制之外的地方凭空借到一个1！让我们来看看前面这个例子在计算机内部是怎样计算的：

.. code-block:: none

      00000000|00000000|00000000|00001010       ( 10的32位二进制码，即a在内存中的实际样子)
   -) 00000000|00000000|00000000|01100100       (100的32位二进制码，即b在内存中的实际样子)
   --------------------------------------
      11111111|11111111|11111111|10100110       (-90的32位二进制补码，如果看成正数，就是4294967206)
     ^                             ^  ^
     |                             |  | 这次借位在第4位上借到了1，第4位变成0
     |<----------------------------| 这次借位会一直不断向高位延伸，但实际上所有高位全为0，根本借不到
     | 最后借位一直持续到第32位还是借不到，于是假装从第33位借到了，尽管实际上根本没有第33位！

那么这样的一种补码有什么用呢？其实在计算机内部所有数都有规定位数的情况下，这个奇怪的差和它对应的负数在进行加法运算时效果是一样的。比如刚才这个例子，我们本来应该得到的差是-90，但是计算机给了我们一个4294967206=2\ :superscript:`32`-90，虽然看起来差异非常大，但是可以看出它们是有联系的。假设我们要计算的是10-100+200，那我们能不能用得到的这个超级大的正数继续运算下去呢？在现实世界里当然是不行的，但是在计算机世界里却是可行的，不信来看：

.. code-block:: none

      11111111|11111111|11111111|10100110       (4294967206)
   +) 00000000|00000000|00000000|11001000       (200)
   --------------------------------------
    1 00000000|00000000|00000000|01101110       (110，受int长度限制，只能保留32位，结果得到110)
    ^                            ^
    |<---------------------------| 这里发生的进位，会一直向前推进直到第33位
    | 这次进位抵达第33位，超出了int的32位限制，所以被抛弃，计算结束

大家可以去修改一下上面这个小程序试一试，是不是很神奇？我们把减90变成了加4294967206，而且用无符号数完成了带负号的运算。这就是现代计算机都采用补码来表示整数的原因，它可以把减法变成加法，把CPU的基本运算统一为二进制加法。

如果使用没有长度限制的十进制数，比如还是计算10-100，也要得到一个可以代替-90的正数“类补码”差。我们的方法是给被减数加上一个特殊的补数再进行计算。参考二进制的情形，计算机其实是假装在最高位之前又补了一位1。所以我们现在也假装给被减数在更高位上补一个1。具体要补在哪一位上呢？因为我们现在没有特定的总位数限制，所以我们就以减数的位数为依据，把被减数补到恰好比减数多一位，最高位为1，其余位补0。在我们这个例子里，减数100是一个三位数，所以我们把被减数补成四位数。按照规则，就是给被减数加上补数1000变成1010。计算变成1010-100=910，得到的结果910恰等于补数1000加上真正的差-90。

这个结果假如要用于进一步的计算，那么在后续运算时减去那个补数1000就可以当成-90使用，例如910+200-1000=110，得到的结果就是10-100+200=110的正确结果。因此这种“类补码”有和真正的二进制补码类似的性质和功能，但还是有不同之处。

.. admonition:: 思考

   1. 计算机内部采用二进制补码进行减法运算，和我们设计的针对无长度限制十进制数的类补码减法运算有什么不同之处？
   2. 如果在计算“类补码”减法 :math:`a-b` 之前没有判断 :math:`a` 和 :math:`b` 的大小，有没有办法在做完减法之后根据差判断是否发生了小数减大数？
   3. 如果发生了小数减大数，怎样得到减法过程中加进去的补数。


接下来我们就要把上面描述的“类补码”减法扩展到万进制的 ``BigInt`` 来实现我们的高精度减法了。


BigInt减法运算
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

``BigInt`` 实现上面所说的“类补码”减法运算，只不过是把十进制扩展到万进制，范围为0-9的十进制位变成范围为0-9999的万进制节而已，其他的运算规则都是完全一样的。但是要编成简洁高效的程序，还需要一些小小的技巧。

首先我们来看小数减大数的情况，例如要计算9-99999999，真正的结果应该是-99999990。“类补码”的减法则这样计算：减数长度为2节，被减数1节，所以先把被减数补为2节，再添上数值为1的更高一节，然后进行计算：

.. code-block:: none

         1|0000|0009    (加上去的补数为100000000)
   -)      9999|9999
   -----------------
         0|0000|0010    (结果为10，即补数加上真正的差：100000000-99999990=10)

加上补数之后，被减数一定大于减数，不可能出现借位借不到的情况。程序使用 ``vector<int>`` 容器存放各个节，容器不会因为最高节的值变成0而自动删除它的，所以计算结束后要手动删除添上去的最后那个节。另外，在删去添上去的最高节之后，剩余的得数中可能还存在最高节为0的情况，比如本例中就有一个。接下来要把得数中为0的最高节都删除掉，就能得到“伪补码”的差值了。

然后是一个编程技巧上的处理。按照我们目前的算法，在进行减法之前先要判断减数和被减数的大小，如果减数更大那么要对被减数进行补数的预处理，得到结果之后要对结果进行去除多余节的后续处理。所以我们的程序结果可能是这样的：

.. code-block:: c++

   if (a < b) {
           // 对a进行补数预处理
   }
   c = a - b;
   if (a < b) {
           // 对c进行去除多余节的后续处理
   }

怎么看怎么别扭，对不对？何况我们现在还不会比较 ``BigInt`` 型数据的大小呢！怎么办？

其实我们可以不管三七二十一，对所有被减数进行补数处理的。如果被减数大于等于减数，那么被减数的节数至少和减数相同，但我们不管，我们也给它补上一个更高节，数值为1。由于被减数本身就不比减数小，所以补上去的这个节反正也是白补，最终也不会用到它。计算结束，补上去的那个节一定是原封不动地还保留在那里，所以我们依旧参照小减大的情形，对结果进行多余节的删除就可以了。

例如99999-99990，先把被减数补成100099999，然后计算：

.. code-block:: none

         1|0009|9999    (加上去的补数为100000000)
   -)         9|9990
   -----------------
         1|0000|0009    (对这个结果做后续处理就可以得到真正的结果9)

最后的删除多余节的过程也是一模一样的，先把添上去的那个节无条件删掉，然后再从高到低删除值为0的节即可。这里千万要记住，结果有可能为0，所以从高到低删除值为0的节时要确保至少留下最低节！

下面我们就要开始动手写代码了，首先是减法相关的四个运算符的重载函数原型，和加法的形式完全相同：

.. code-block:: c++

   struct BigInt {
           // ...
           BigInt &operator-=(const BigInt &a);
           BigInt operator-(const BigInt &a) const;
           BigInt &operator--();           // 前置--
           BigInt operator--(int);         // 后置--
           // ...
   };

出于和加法时相同的原因，我们先实现 ``-=`` 运算，因为减法可以一次循环做完，所以可以直接修改被减数来进行计算，这种方式可以减少数据复制的次数。实现的代码很直观，预处理和后续处理是类似操作的典型写法，中间的减法运算是直观模拟竖式减法。由于进行了补数，所以不用担心会出现借位借不到，只需要循环向高处去寻找第一个能借到的节就可以了。至于其他三种运算的代码和加法的情形完全一致。请认真阅读和理解这些代码。

.. literalinclude:: ../../codes/312_bigint.cpp
   :language: c++
   :lines: 174-208

.. note::

   这个“伪补码”减法的程序是比较朴实地模拟了竖式减法运算的，整个结构很容易理解，预处理和结尾处理的部分也不难看懂。比较复杂一点的是实现借位的循环，这里对循环变量的操控是重点，很容易搞错。在读这类循环结构程序的时候，最好的办法是编一些简单的数值用纸笔模拟运行一下，列个表格一步一步地跟踪每次循环时所有变量值的变动情况。

BigInt比较运算
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

比较大小的逻辑运算，对于任何数据类型来说都是极其重要的。如果不能进行大小比较，这种数据类型就会有很多功能无法使用。比如我们现在就可以说，如果 ``BigInt`` 类型不支持比较大小，那么对于刚刚实现的“伪补码”减法，我们就无法判断是不是发生了小数减大数，因为这需要比较计算结果和被减数的大小。假如我们不用“伪补码”减法，而是简单的取绝对值呢？那就更加不可能了，因为要取绝对值就必须事先比较减数和被减数的大小。

另外，比较运算还有以下一些必不可缺的理由：

1. 通常来说只有实现了比较运算，这个数据类型才能用做循环控制变量，例如最常见的 ``for (i = 0; i < 100; ++i)`` 或者 ``while (i != 0)`` 这样的循环控制，都需要用到比较运算。

2. C++最大的福利，\ ``algorithm`` 库中提供的排序函数 ``sort()``\ ，要求被排序的数据类型必须支持 ``<`` 比较运算。

可见为一个自定义数据类型实现大小比较运算有多么重要，接下来我们就来完成这一步骤。我们很快就可以发现，比起加减乘除，实现比较运算是多么的轻松愉快。

C++共有六种比较运算：\ ``<, >, <=, >=, ==, !=``\ 。以成员函数形式重载它们的函数原型如下：

.. code-block:: c++

   struct BigInt {
           // ...
           bool operator<(const BigInt &a) const;
           bool operator>(const BigInt &a) const;
           bool operator<=(const BigInt &a) const;
           bool operator>=(const BigInt &a) const;
           bool operator==(const BigInt &a) const;
           bool operator!=(const BigInt &a) const;
           // ...
   };

根据比较运算相互之间的关系，理论上我们只需要实现其中一种，就可以利用它来完成其余五种。具体的方法是这样的，假设我们会判断是否 :math:`a \lt b`\ ，那么：

* :math:`a \gt b \iff b \lt a`
* :math:`a \le b \iff a \not\gt b \iff b \not\lt a`
* :math:`a \ge b \iff a \not\lt b`
* :math:`a = b \iff (a \ge b)\text{ and }(b \ge a) \iff (a \not\lt b)\text{ and }(b \not\lt a)`
* :math:`a \neq b \iff (a \lt b)\text{ or }(b \lt a)`

要实现 ``BigInt`` 的小于比较是很简单的，其方法和通常的两个正整数比较大小完全一样：先看两个数的长度是否相同，如果不同那么大小已分；如果相同那么从高位到低位逐位进行比较，找到第一个不同的位，这一位谁小，谁就是小，如果一直找到最低一位都没有分出大小，那么二者相等。\ ``BigInt`` 只不过是把位变成了节而已。

但是在这里我们建议除了实现 ``<`` 之外，最低限度应该再实现 ``==`` 运算，然后 ``!=`` 就可以很简单地利用 ``==`` 来实现。因为如果要依赖 ``<`` 来构造 ``==`` 和 ``!=`` 的话，需要进行两次 ``<`` 运算，这就非常浪费了。

更何况 ``BigInt`` 是用 ``vector<int>`` 来构建的，而 ``vector<int>`` 天生就支持用 ``==`` 和 ``!=`` 来检查两个向量的内容是否完全一致。所以 ``BigInt`` 的这两个比较运算我们就干脆直接比较 ``vector<int> _s`` 了，简单到难以置信并且速度更快。

下面是所有六个比较运算的实现代码：

.. literalinclude:: ../../codes/312_bigint.cpp
   :language: c++
   :lines: 211-227

.. note::

   这几个运算的代码简单到几乎没什么可解释的。但是这里却有一个问题：为什么 ``<, >, <=, >=`` 这几个比较运算不像 ``==`` 和 ``!=`` 那样直接比较 ``vector<int> _s`` 呢？这个问题请结合 ``vector`` 容器内容比较的规则和 ``BigInt`` 的数据结构思考一下，找出答案。