专栏名称: 码农翻身

工作15年的前IBM架构师分享好玩有趣的编程知识和职场的经验教训，不容错过。

张大胖的加法器

码农翻身 · 公众号 · 程序员 · 2016-12-28 20:01

正文

加法器

热爱编程的张大胖在大学时最烦的一门课之一就是《数字电路》，他一直觉得和编程没什么关系。

有一次课程设计是实现一个加法器，大胖使用逻辑电路，费了九牛二虎之力才实现了4位的加法。

这4个二进制位能表达的数有16个，从0 到15 ：

大胖用他的加法器计算了一下 8+3 ：

8+3 = 1000 + 0011 = 1011 = 11

还不错，再计算一下 9+7 ：

9+8 = 1001 + 1000= 0001

怎么变成了1 ？奥，我这儿只有4位，能支持的最大数字就是 15 ，而9+8的结果是 10001 （十进制16），计算结果溢出，最高位的1被丢弃了！

其实这也符合要求，大胖顺利的交了作业。

用加法来表示减法

可是下一次课还是课程设计，老师竟然要求在这个加法器上实现减法，这可把大胖给难住了，在加法器上实现减法，真是个变态的需求。

遇到了问题，张大胖自然会“跪求”好基友，电脑高手Bill。

Bill 说： “这个要求一点都不变态，用加法器同时实现加法和减法，能极大的节省CPU的电路设计。 ”

“你就说该怎么实现吧”

Bill说：“我先给你说一下原理，在你定义的4位二进制中，一共可以表达16个数，我们引入一个‘补数 '的概念，例如 3的补数是 13， 4的补数是12， 5 的补数是11，当你计算7减去3 的时候，可以变成 7加上3 的补数，即 7 + 13 ”

“可是7+13 是20 ，但是7-3 等于4 啊”

“20其实已经超出你4位二进制能表达的16个数了，已经溢出了，对吧，所以20还得减去16 ，就是4 了。你用二进制算一下。”

7-3 = 0111- 0011 = 0111 + 1101（二进制13） = 10100

10101已经溢出了，去掉最高位是 0100 ，就是十进制4 了。

“果然不错” 张大胖说 “这让我想到了钟表，现在是7点，我想让它回到4点，有两种办法，一种方法是让时针后退 3 格，另外一种方法是让时针前进9格，前进到12点的时候，其实就相当于溢出了，舍弃掉。 "

Bill 说， "看来你已经Get了，数学上有个词叫做求模，说的就是这个运算，还以时钟为例"

向后退3格： 7 - 3 = 4

向前进9格： (7 + 9) mod 12 = 4

向前进21格： (7+9+12) mod 12 = 4

向前进33格： (7+9+12+12) mod 12 = 4

.....

“这是一种以进为退的策略” Bill 接着说 " 用这种办法就把减法变成了加法"

“但是我怎么得到所谓的补数呢？从3 怎么得到13 呢”

“这很简单，对于二进制， 前辈们想出了一个异常简单，又特别适合计算机的算法，对二进制数的所有位取反，然后加1 ”

“神奇啊，前辈们竟能想出这么巧妙的办法！”

“这就是所谓的补码了” Bill总结道

负数的表示

Bill 问道： “刚才咱们说的都是整数的加减法，负数你考虑了没有啊？大胖？”

“我也刚刚想到，现在我知道 7-3 可以换算成 7+ 13 了，如果是3 - 7 呢？ ”

“负数一引入，系统就变得更复杂了，首先你得用一个标志位来表示整数还是负数吧： ”

（表格1）

张大胖说： “明白了，最高位的0 表示正数， 1 表示负数，真正有效的数字只剩下3位了， 正数的范围是从1 到7 ，负数的范围从 -1到-7 ，不过这里出现了两个零！一个正0 ，一个负0 ，这不妥吧。”

“先别急，之前说到减法可以变成加法，秘密就是用补码，例如8-3 相当于8+(-3)的补码，那我们完全可以把表格1中的负数用补码表示， 然后把那个负0 特别当做 -8来处理： ”

Bill 接着说： “按照上面的表格，现在我们来计算一下 7-4 , 7是 0111， -4是 1100， 注意我们把符号位也算进去了，两者相加：

“让我试试4-7, ” 张大胖说， 4是0100 ， -7是1001，两者相加：

“妙啊” 张大胖不禁赞叹起来， “把负数用补码表示，不但减法变加法，连符号位都可以参与运算了！”

“ 是啊，我们通过补码能极大的简化电路的设计，你一定要记住，在计算机内部，是使用补码来表示二进制数，如果是一个正数，补码就是它本身，如果是个负数，需要把除了符号位之外的二进制数进行取反加一的操作"

"此外，我想你也能总结出来，你这个4位的系统如果只表示无符号数(没有负数的话) ，它的范围是[0 , 2 ^ 4] ，即[0, 16] ；

如果要想表达有符号数(负数和整数)，它的范围就是[-2^3, 2^3-1] , 即[-8, 7] 。在高级编程语言像C, Java ，你经常会看数据类型的取值范围，你应该明白其中的原理了。 ”

（完）

码农翻身相关历史文章推荐：

Java EE

Spring本质系列(1) -- 依赖注入

Spring本质系列(2) -- AOP

Http 历险记（上）

Http 历险记（下）—Struts的秘密

计算机网络

操作系统

数据库

你看到的只是冰山一角，更多精彩文章，尽在“码农翻身” 微信公众号，回复消息"m"或"目录" 查看更多文章

有心得想和大家分享？欢迎投稿！我的联系方式：微信：liuxinlehan QQ: 3340792577

公众号：码农翻身

“码农翻身”公众号由工作15年的前IBM架构师创建，分享编程和职场的经验教训。