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

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

   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