Question

加法器

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

有一次课程设计是实现一个加法器， 大胖使用逻辑电路， 费了九牛二虎之力才实现了 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 ，你经常会看数据类型的取值范围， 你应该明白其中的原理了。 ”