《编码》读书笔记 —— 计算机世界中的减法

上一篇提到过计算机只会做加法。减法在计算机的实现比较加法复杂一些,因为减法有借位的情况。下面从十进制的减法开始说起,然后延伸到二进制中的减法。

十进制中的减法

在十进制减法中,比如253 - 176,如果按照常规思路来做减法,肯定会涉及到借位,但是如果想通过一连串的逻辑门来实现这个借位的逻辑基本不可能。所以这里换一种思路,避免在减法中借位,具体原理就是利用在减法后面加一个数减一个数结果不变,具体这个数是什么和进制有关

比如上面253 - 176做减法的过程如下:

  1. 用999减去减数176(999-176 = 823):由于操作数是三位数,所以这里用了999,如果是四位则用9999。以此类推,从一串9中减去一个数叫做对9求补数。这样做的好处就是无论减数是多少,计算对9的补数都不需要借位。
  2. 将计算减数对9的补数与原来的被减数相加:(823 + 253 = 1076)
  3. 将结果加1,并减去1000。(1076 + 1 - 1000 )= 77注意,这里两个数的第一位都是1,所以可以看做就是1077舍去第一位就是作为的结果

通过上面的步骤我们没有通过借位而得到了正确的结果。其实原理很简单,式子的变化过程如下:

1. 253 - 176 
2. 253 - 176 + 1000 - 1000
3. 253 - 176 + 999 + 1 - 1000
4. 253 + (999 - 176) + 1 - 1000

最终结果是我们用两个减法和两个加法来替代一个减法,在这个过程中避免了繁琐的借位。

如果被减数小于减数又不一样,比如176 - 253。基本思路就是将减数与被减速交换执行减法,然后给结果取一个反。计算步骤如下:

  1. 用999减去253,计算出对9的补数。999 - 253 = 746
  2. 把该数对9的补数与被减速相加。176 + 746 = 922
  3. 这部和之前不同,因为加1减去1000还是小减大。这里改为直接减去999,因为之前加了个999。但是这里还是负数,把减数与被减速交交换,用999减去922等于77,和预期结果一样。
1. 176 - 253
2. 176 - 253 + 999 - 999
3. - (999 - ((999 - 253)+ 176) )

最后需要加个负号。通过上面的步骤同样避免了借位

二进制中的减法

上面253 - 176对应到二进制的减法就是11111101 - 10110000。思路和十进制一样。用多个减法与加法来避免借位的情况。十进制中9做减法不用借位,二进制中1做减法不用借位。最后都需要减去最开始在末尾加的数(十进制是十的倍数,二进制是二的倍数)

  1. 第一步用255(1111 1111)减去减数。1111 1111 - 1011 0000 = 0100 1111:十进制中是在一串9中减去,结果为9的补数,二进制中减数是从一串1中减去的,结果为1的补数。对在求1的补数时,并不需要减法。只需要将原来二进制数中的1变为0,0变为1即可。因此对1求补数也叫取反码。是否联想到了反向器的作用
  2. 将减数对1的补数与被减数相加:1111 1101 + 0100 1111 = 1010 0110 0
  3. 将上面所得结果加1:1010 0110 0 + 1 = 1010 0110 1。这里为什么要加1,因为之间用的1111 11111 和后面减去的256(1000 000 0)相差1。得保证加的和减去的一样。
  4. 减去256(1000 0000 0):1010 0110 1 - 1000 0000 0= 1001101换算为十进制就是77。注意,这里两个数的第一位都是1,所以可以看做就是1010 0110 0舍去第一位就是作为的结果

注意为什么这里用255(1111 1111)。想一想十进制为什么用一串9,因为9是十进制中最大的了,用它来做减法不会出现借位的情况。二进制也一样,用1来充当临时的加减数,同样也不会出现借位的情况。

如果出现了在二进制中出现了被减数小于减数呢。

同样用176 - 253举例子

  1. 用1111 1111减去减数,得到对应的补数。0000 0010。
  2. 将减数对1的补数与被减数相加:1011 0000 +0000 0010 = 1011 0010
  3. 改成在减数小于被减数的时候我们通过将结果加1再减去1000 0000 0实现的。但是这里无法在不借位的情况实现,所以先用1111 1111减去1011 0010等于0100 1101。这里又取了一次反,但这个时候结果为77,而真正答案是-77

到这里计算机中实现减法的方法介绍完了,接下来就是讲讲在逻辑电路中怎么实现。

减法电路的实现

在二进制的减法中,取补码是一个非常重要的过程。可以简单的用八个反向器实现。但是我们是做一台既可以做加法也能做减法的机器。因此需要让电流控制取反。可以通过异或门实现。联想一下异或门的真值表

当一侧输入为1的时候,刚好输出结果取反。对应电流如下:

八个异或门合并起来的器件叫做求补器。符号如下:



这里输入为0则把数据直接输出,为1才取反。

将一个求补器,一个8位二进制加法器和一个异或门做如下连接。

注意这里有是三个信号都标识为SUB,代表加/减转换开关。当信号为0的时候就是做加法,为1就是做减法。

说各个SUB的含义

  • 上边的SUB:决定是否取反,为0做加法不取反,为1做减法要取反。
  • 右边的SUB:决定进位输入,做减法是需要将CI设为1,结合做减法的过程理解,比如上面的例子是将256拆分为了1加255的。在做加法时,CI为0。
  • 左边的SUB:决定是否溢出,做减法时,如果减数小于被减数,这时加法器的CO输出为1。这表示减法的最后一步减去1000 00000。也就是减数要大于被减数结果为负数。现在还不能表示负数,左边的SUB仅仅在加法器的CO输出为0时才会亮起。

虽然现在还没有解决减法如何实现的问题。得解决负数在二进制中如何表示。

表示负数

在十进制中表示负数的方法如下:
...-1000, -999 ,... -1, 0, 1, 999, 1000
好处在于能表示所有的正数和负数。将0视为无限延伸序列的重点,正数沿着一个方向,负数沿着一个方向。

但是我们并不需要无限大或者无限小的数,比如我们一开始就知道这个数的范围。

一个简单的例子,假如你的余额宝(这里不计算几分钱)最多不超过5000,同时你可以透支5000。意思就是你的余额宝账号应该是在-5000到4999之间。所以这里用到的最大的数为4999,从5000到9999的四位位数就可以表示负数。

比如用5000表示-5000,5001表示-4999, ...., 9999表示-1,0001表示1, 0002 表示2,4999表示4999。

-5000,-4999,-4998,...,-1,1,2,4998,4999
5000, 5001, 5002,...,9999,0001,0002,...,4998,4999
这就形成了一个循环排序,最小负数5000看起来像最大正数4999的延续。这里的9999是比0小1的数。加上1得到10000。由于处理的是四位数,这个结果实际上就是0000.

这种方式叫做10的补数表示法。(为了简化问题这里用三位数了)将三位负数转为10的补数,再用999减去他再加1。也就是10求补数就是对9求补数在加1。比如-255对10求补,用999减去255加1得到745。这个745就表示-255

利用10的补数,不再用到减法,所有的步骤全部用加法进行。

同样的可以把这种机制运用到二进制中,被称作为2的补数。这里以8位二进制位例,范围是0000 0000 到1111 1111。对应十进制中的0到255。如果还想表示负数,则以1开头的每个八位数都表示一个负数。


现在表述数的范围是-128到127,最高位作为符号位,1表示负数,0表示正数。

为了求2的补数,需要先计算1的补数然后再加1。这个步骤和求10的补数一样。等价于将每一位取反然后加1。

比如125二进制位0111 1101,为了表示-125对2的补数。先取反,得到1000 0010,然后加1得到1000 0011,可以根据上表用同样的步骤每一位取反然后加一可以将数值还原。

现在可以自由的将正数和负数相加了,将-127和124等价的二进制相加。1000 0001 + 0111 1100等于1111 1101等于十进制的-3。

注意:涉及到上溢和下溢的情况,比如125+125= 1111 1010由于最高位为1,结果表示负数了。相当于十进制-6了。

一般来讲,在加法中。两个操作数符号相同,而结果符号与操作数的符号不同,这样的加法无效。

看到现在,有些同学是否已经知道了大学老师讲的溢出是什么意思了吧。二进制可以有符号或者无符号。无符号8位二级制表示范围0到255。有符号的8位二进制表示范围是-128到127。所以当给你一个二进制问你代表十进制多少的时候,一定要确定是否有符号。

写在最后

至此,计算中二进制的加法与减法的实现介绍完毕了。当初看似复杂的东西,多看几遍也就不复杂了。探索计算机底层仍在继续......

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 202,905评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,140评论 2 379
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 149,791评论 0 335
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,483评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,476评论 5 364
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,516评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,905评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,560评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,778评论 1 296
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,557评论 2 319
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,635评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,338评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,925评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,898评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,142评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,818评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,347评论 2 342