补数与减法

“还在这儿，雷欧提斯！上船去，上船去，真好意思！风息在帆顶上，人家都在等你哩。好，我为你祝福！还有几句教训，希望你铭记在记忆之中：不要想到什么就说什么，凡事必须三思而行。对人要和气，可是不要过分狎昵。相知有素的朋友，应该用钢圈箍在你的灵魂上，可是不要对每一个泛泛的新知滥施你的交情。留心避免和你家争吵，可是万一争端已起，就应该让对方知道你不是可以轻侮的。倾听每一个人的意见，可是只对极少人发表你的意见，接受每一个人的批评，可是保留你自己的判断。尽你的财力购置贵重的衣服，可是不要炫新立异，必须富丽而不浮艳，因为服装往往可以表现人格，法国的名流要人，就是在这点上显得最高尚，与众不同。不要向人告贷，也不要借钱给别人，因为债款放了出去，往往不但丢了本钱，而且会失去朋友，向人告贷的结果，容易养成因循懒惰的习惯。尤其要紧的，你必须对你自己忠实，正像有了白昼才有黑夜一样，对自己忠实，才不会对别人欺诈。再会，愿我的祝福使这一番话在你的行事中奏效！”这一段是莎士比亚的《哈姆雷特》中波洛涅斯对儿子雷欧提斯临别时说的话。

我们在小学时都会算下面这道减法题：

   253
 - 176
 -----
   ???

从十位数5借1，求个位数的差:

  2   4  13
- 1   7   6
-----------
  ?   ?   7

从百位数2借1，求十位数的差:

  1  14  13
- 1   7   6
-----------
  ?   7   7

求百位数的差:

  1  14  13
- 1   7   6
-----------
  0   7   7

对于减法，我们先明确几个概念，以253减去176等于77为例，其中253我们称为被减数(minuend)，176是减数(subtrahend)，77是差(difference)。对于减法运算，被减数通常会遇到借位操作。如3减去6时，我们需要从被减数的5借1，并用13减去6，结果为7。此时被减数5被借1，所以我们要用4减去7，同样，我们要从2借1，并用14减去7，结果为7。最后，因为2被借1，只剩下1，1减去1等于0，结果为77。

  被减数
-   减数
--------
      差

那么我们该怎样避免烦琐的借位呢？借位是因为被减数的数字小于减数的数字，所以要避免借位，我们就要规避这种情况。对于被减数253减去减数176，其实我们可以用下面的公式进行等价替换：

253 - 176 = 999 - 176 + 253 - 999

也就是有下面的不借位的减法运算：

  999
- 176
-----
  823

   823
+  253
------
  1076

  1076
-  999
------
   ???

虽然999减去减数176不用借位，但是我们计算到1076减去999时又遇到了借位。这种情况，我们可以用下面的等价公式替换：

1076 - 999 = (1076 - 1000) + 1

也就是：

  1076
- 1000
------
    76
+    1
------
    77

这里用到了补数(complement)的知识，用999减去减数176叫做对数字176求9的补数(nines’ complement)，同样，我们用1000减去176叫做对176求10的补数(ten’s complement)。数字176的9的补数是823，10的补数是824，显然，10的补数，我们可以用9的补数加1得到：

1000 - 176
 = 1 + 999 - 176
 = 999 - 176 + 1
 = 823 + 1
 = 824

对于被减数253减去减数176，我们先求减数176的9的补数823，再将被减数253和823相加得到1076，最后用1076减去1000再加1后得到差77。通过补数，我们避免掉了减法中烦琐的借位操作。

如果是下面这道减法题呢？

  176
- 253
-----
  ???

我们发现被减数小于减数，所以按照减法的运算规则，我们需要把被减数和减数交换后做减法，然后结果取反，也就是求结果的相反数，高级一点叫做加法逆元(additive inverse)。

  176
- 253
-----
  -77

同样，为了不借位做减法运算，我们先求减数253的9的补数746，用补数746和被减数176相加得922，然后用922减去1000，哦，好像那里不对呀？是的，922减去1000遇到了借位，对这种情况，我们只需要对922求9的补数后取反即可，也就是999减去922得到77，再取反得到-77。

那么我们有没有可能不用减法号做减法，也就是用加法做减法呢？

我们知道负数需要一个额外的符号“-”表示，我们的体育老师在教我们数学的时候应该说过，正数其实也有个表示正数的符号“+”，只是平时忽略不写而已。为了用加法做减法，我需要先解决正数和负数的表示问题。

我们先看下整数集合的表示：

… -9999, -9998 … -2, -1, 0, 1, 2 … 9998, 9999 …

这是有无限多个数字的整数的全集，对于早期的机械计算器以及现代的电子计算机(也就是电脑)只能计算有限位的数字。我们从整数中取出3位数字范围的子集为例，介绍一下计算器怎么通过加法做减法的，比如我们选取3位长度的数字的集合:

-999, -998, …, -2, -1, 0, 1, 2, … 998, 999

为了解决正号和负号的符号表示问题，我们从-999到999取正整数集合:

0, 1, 2 … 998, 999

这个包含有1000个数字的正整数集合也可以表示如下：

500, 501, 502 … 998, 999, 0, 1, 2 … 498, 499

我们发现以0为中轴，除了数字500以外，两侧对称的数字互为10的补数。比如501的10的补数是499，502的10的补数是498，998的10的补数是2，999的10的补数是1。如果我们把互为10的补数的两个数字相加，会有如下结果：

   501
+  499
------
  1000

   502
+  498
------
  1000

   998
+    2
------
  1000

   999
+    1
------
  1000

因为我们的集合是3位正整数的集合，也可以说是我们的计算器只能表示3位长度的十进制数字，所以这些互补的数字的和的最高位的1无法表示，可以直接舍弃。从中我们可以看出，3位正整数范围内，我们可以用数字999表示数字1的“加法逆元”，即相反数，也就是用数字999表示数字-1。这就是我们要的负数的表示，即不用正负号符号表示有符号数(signed number)，也就是5到9开头的数表示负数，1到4开头的数表示正数，如下所示：

-500, -499, -498, -497 ...  -3,  -2,  -1, 0, 1, 2, 3 ... 497, 498, 499
 500,  501,  502,  503 ... 997, 998, 999, 0, 1, 2, 3 ... 497, 498, 499

我们的体育老师应该也教过我们，减去一个数等于加上这个数的负数。现在，我们再来看一下我们一开始提到的减法问题。

   253
 - 176
 -----
   ???

我们可以求减数176的9的补数再加1得到减数176的10的补数如下：

  999
- 176
-----
  823
+   1
-----
  824

数字824也就是数字-176在有符号集合中的表示。我们再看下被减数253减去减数176的有符号数的减加法运算：

   253
+  824
------
  1077 

我们把1077的高位的数字1舍弃掉，就可以得到数字77，也就是正数77即被减数253和减数176的差。是不是很神奇？

我们再看下这道减法题：

  176
- 253
-----
  ???

同样，如下运算求减数253的10的补数：

  999
- 253
-----
  746
+   1
-----
  747

我们再看下被减数176减去减数253的有符号数的减加法运算：

  176
+ 747
-----
  923

数字923正是我们数字-77在有符号集合的表示。对于负数77的10的补数，我们可以对其再求10的补数并取反即可得到原来的数字:

  999
- 923
-----
   76
+   1
-----
  -77

到此为止，我们知道在十进制数的减法中，通过9的补数可以避免减法中烦琐的借位运算，通过10的补数表示有符号数，可以将减法运算转换为加法运算。这也是如古老的机械计算器(如基于齿轮的帕斯卡计算器)以及现代电子计算机的有符号数的表示与应用原理。

我们知道3位长度基于10的补数的有符号的十进制数字的集合如下，其中5,6,7,8,9开头的数字是负数：

500,  501,  502,  503 ... 997, 998, 999, 0, 1, 2, 3 ... 497, 498, 499

现在，我们来看下正整数255和自身的加法运算：

  255
+ 255
-----
  510

结果是510，我们知道以数字5开头的表示负数，也就是说两个正数的和是个负数？对510求10的补数并取反可以得到原来的数字-490。是不是很神奇？对的，这种情况我们称之为溢出，严格一点叫做上溢(overflow)，也就是说两个有符号数的运算的结果超出了有符号数集合的上界。

我们再来看一下负数512和自身相加的运算：

   512
+  512
------
  1024

结果是1024，最高位1舍弃，最终的到数字24，我们知道24是一个正数，也就是两个负数相加的结果是个正数？对的，这是另外一种溢出，因为是超出了有符号数集合的下界，我们称之为下溢(underflow)。

总结一下就是两个整数的运算结果超出了数字的表示范围，我们称这种情况为溢出(overflow)。超出上界的情况我们称为上溢(overflow)，超出下界的情况我们称为下溢(underflow)。你没有看错，单词“overflow”既可以表示两种溢出情况，也可以专门表示上溢。

讲完了十进制数的有符号数表示以及加减法的运算，接下来，让我们一起看一下二进制数在电子计算机中的表示和运算。

对于被减数253减去减数176，我们有下面对应的8位二进制数的运算：

  1111 1101
- 1011 0000
-----------
  ???? ????

为了不使用借位做减法运算，我们用二进制数1111-1111减去减数1011-0000，也就是求减数1011-0000的1的补数(one’s complement):

  1111 1111
- 1011 0000
-----------
  0100 1111

用1的补数0100-1111和被减数1111-1101相加：

    0100 1111
+   1111 1101
-------------
  1 0100 1100

然后用1-0100-1100减去(1111-1111 + 0000-0001)即减去1-0000-0000再加0000-0001，即：

  1 0100 1100
- 1 0000 0000
-------------
  0 0100 1100
+ 0 0000 0001
-------------
  0 0100 1101

结果是0100-1101，也就是十进制数的77。

上述的二进制数的减法中用到了1的补数的知识，我们也有二进制数的2的补数(two’s complement)，比如对于数字253的二进制数1111-1101的2的补数可以用1-0000-0000减去1111-1101计算。当然，为了避免借位减法，我们可以计算数字1111-1101的1的补数再加0000-0001即可：

  1 0000 0000
-   1111 1101
-------------
    ???? ????

等价于

    1111 1111
-   1111 1101
-------------
    0000 0010
+   0000 0001
-------------
    0000 0011

对于二进制数的1的补数，只需要将1转换为0，0转换为1，所以二进制的1的补数又叫做反码(inverse)。二进制数的2的补数只需要用1的补数加1。二进制数的2的补数又叫做补码(two’s complement)。而原始的二进制数也称为原码(true code)。

显然，反码的反码是原码，那么补码的补码是什么呢？还是原码。比如对于原码1111-1101的补码0000-0011求补码运算：

    1111 1111
-   0000 0011
-------------
    1111 1100
+   0000 0001
-------------
    1111 1101

二进制数的反码和补码在逻辑电路中实现起来非常简单，对于8位二进制数的反码运算，只需要用到一个8位反相器(inverter)。

对于被减数176减去减数253，我们有下面对应的8位二进制数的运算：

  1011 0000
- 1111 1101
-----------
  ???? ????

首先，求减数1111-1101的1的补数：

  1111 1111
- 1111 1101
-----------
  0000 0010

对1的补数和被减数做加法运算：

  0000 0010
+ 1011 0000
-----------
  1011 0010

然后对二进制数1011-0010求1的补数：

  1111 1111
- 1011 0010
-----------
  0100 1101

结果是0100-1101，也就是十进制数的77，再取反，即数字-77。

到此，我们讲完了二进制数字不用借位的减法运算。接下来我们探讨一下二进制数字的有符号数的表示。

我们知道8位二进制数字的范围是0到255。这256个数字也可以如下表示：

1000-0000, 1000-0001, 1000-0010 ... 1111-1111, 0000-0000, 0000-0001 ... 0111-1110, 0111-1111

我们发现，除了数字1000-0000外，在数字0000-0000两侧对称的数字互为2的补数。我们可以用1开头的8位二进制数表示负数，以0开头的8位二进制数表示正数：

二进制数	十进制数
1000-0000	-128
1000-0001	-127
1000-0010	-126
. . .
1111-1110	-2
1111-1111	-1
0000-0000	0
0000-0001	1
0000-0010	2
. . .
0111-1110	126
0111-1111	127

也就是最高位表示符号位，1表示负数，0表示正数，8位有符号数的范围是-128到127。

我们看一个十进制数的被减数76减去减数53的二进制运算：

  76
- 53
----
  ??

等价于

  0100 1100
- 0011 0101
-----------
  ???? ????

首先，计算减数53也就是0011-0101的有符号数的数字，对于二进制数也就是求其补码，而补码是反码加1：

  1111 1111
- 0011 0101
-----------
  1100 1010
+ 0000 0001
-----------
  1100 1011

再做补码1100-1011和被减数的加法运算：

    1100 1011
+   0100 1100
-------------
  1 0001 0111 

舍弃结果中最高位的数字1得0001-0111，即十进制数的23。

我们再看被减数为53减去减数76的对应的二进制运算：

  53
- 76
----
  ??

等价于

  0011 0101
- 0100 1100
-----------
  ???? ????

求减数0100-1100的补码：

  1111 1111
- 0100 1100
-----------
  1011 0011
+ 0000 0001
-----------
  1011 0100

将补码1011-0100和被减数0011-0101做加法运算：

  1011 0100
- 0011 0101
-----------
  1110 1001

我们看到结果1110-1001的最高位是1，说明这是一个负数。因为被减数53小于减数76，这也是我们期望的结果。

对负数1110-1001做补码运算，求其原码：

  1111 1111
- 1110 1001
-----------
  0001 0110
+ 0000 0001
-----------
  0001 0111

结果二进制数0001-0111是十进制数的23，因为是负数，所以最终结果是-23。

现在，我们来看一下有符号二进制数的溢出问题。

以8位有符号二进制数为例，我们看下十进制数124和16的加法运算：

  124
+  16
-----
  140

等价于

  0111 1100
+ 0001 0000
-----------
  1000 1100

我们看到两个正数124和16的加法的和是1000-1100，最高位是1表示是负数？对的，这就是说8位有符号二进制数不能够表示更大的数字140，产生了上溢。

下面我们看8位二进制有符号数的下溢的例子，求十进制数-128和-127的和：

  -128
+ -127
------
  -255

等价于

    1000 0000
+   1000 0001
-------------
  1 0000 0001

舍弃最高位的1，运算的结果为0000-0001。因为最高位是0，所以是个正数。两个负数相加的结果是个负数？对的，这是就是说8位二进制数不能够表示更小的数字-255，产生了下溢。

通过二进制的反码，我们避免了二进制数减法的借位操作，通过补码表示二进制的有符号数，我们将减法转换成了加法，所以电子计算机中的算术运算实际上都是在做加法运算。

参考

https://en.wikipedia.org/wiki/Method_of_complements
https://en.wikipedia.org/wiki/Two%27s_complement
https://en.wikipedia.org/wiki/Ones%27_complement
https://en.wikipedia.org/wiki/Integer_overflow
https://en.wikipedia.org/wiki/Signed_number_representations