如何教会计算机算术??加减篇

1+1等于几？

这个问题困扰了人们很多年。

有人说，一加一等于1，因为两个麦芽糖黏在一起还是一个麦芽糖。

有人说，一加一等于2，因为双击计算器.exe，输入1+1，输出结果是2。

有人说……

……我编不下去了。

那么各位小朋友大朋友早上中午晚上好。今天我们要来教会一台计算机如何进行加减法。

就是这么简单。

咦？其实不简单吗？

零、让我们从零开始

假设你的老妈在厨房大吼：“崽啊，快来吃饭！菜都要凉辣！”但是你此时没有办法迅速赶到餐桌，因为你正在忙着偷偷用老妈的支付宝购买那个游戏6！你的手边只有餐厅吊灯的神秘开关，你要怎么像老妈传达信息呢？

很简单！控制灯的亮起即可！我们将点亮的灯泡视为True（或者更简单地：1），熄灭的灯泡视为False（或者0），这样，你就可以高效地传递信息！

随后你毅然决然地关闭了餐厅的灯。

坏结局，你的老妈并不知道高深莫测的计算机组成原理，从她的视角来看……

小崽子又欠揍了（抄起衣服架子）。

怎么办，世界末日就在眼前！但是别慌，因为老妈还有10秒才会破门而入，在这么充裕的时间内足以我们开启下一章节了。

一、数字在计算机中的表达

1. 二进制

现在，想象你手中拿的是一根电线，没错，就是连着餐厅吊灯的那条电线，回想一下，你是怎么通过电线进行信号传输的呢？

那就是：通电代表1，未通电代表0。

但是这只能表达两种状态啊，这个世界不是非黑即白的，如果我们需要表达四种状态怎么办？

简单，再加上一根电线。

现在我们可以通过控制两根电线来表达00，01，10，11这四种状态，那给它们起个编号吧！

00代表0；01代表1；10代表01+01，进一位，是2；11就是10+01是3；

没错，这就是二进制表示数据。

在计算机中，我们普遍使用二进制来计算基础运算，这其实是个很显而易见的道理，如果使用十进制，我们需要针对十种不同的状态设计十个不同的电路，而二进制就很简单了，用一根简单的电线，通电代表1，没通电代表0。

二进制的转换

那么假如给你一串随机的二进制数：010110，我们怎么知道它对应的是多少呢？

我们先来看看十进制数。

随便取一个十进制数：21367，它可以很直观地被拆成

$$2\times10^4+1\times10^3+3\times10^2+6\times10^1+7\times10^0=21367$$

那么很直观地我们能想到，对于r进制的数21367，我们可以表达成

$$2\times r^4+1\times r^3+3\times r^2+6\times r^1+7\times r^0=21367_r$$

更通用地，对于r进制的数$K_nK_{n-1}K_{n-2}...K_1K_0$，可以表达为

$$K_nr^n+K_{n-1}r^{n-1}+K_{n-2}r^{n-2}+...+K_1r^1+K_0r^0$$

感觉晕头转向？我们直接拿这个二进制数010110为例：

$$010110 = 0\times2^5+1\times2^4+0\times2^3+1\times2^2+1\times2^1+0\times2^0$$

于是它所对应的十进制数就是：$2^4+2^2+2^1=16+4+2=22$

怎么样，是不是很简单？

十六进制数

你一定听说过这么个名词：32位操作系统和64位操作系统。

没错，32位操作系统代表着，对于int整形的变量，一共有32个比特用来存储这么一个数。

也就是说，整形二进制数的长度最长可以有32位。

好多！那么程序员在调试的时候总不能用手指头指着屏幕上的0和1一个一个数过去吧？

于是我们在此引入十六进制数。

我们规定，$A$代表$10$，$B$代表$11$，$C$代表$12$，以此类推，$F$代表$15$。

那么完整的16进制个位数便是：$0123456789ABCDEF$

你惊人的注意力一定注意到了，这刚好对应4位2进制数！

于是，我们可以将一个很长的二进制数01101011聚合为两个十六进制数6B

2. 二进制数的编码表示

机器数

现在想必你已经能够熟练的使用二进制数进行加减法了，那我们来想想这么一个情况。

假设一个计算机的寄存器中，只有8个位置，即只能存8个0或1，我们该如何存正数和负数呢？

很简单，拿出第一个位置，规定：

第一个位置存0，代表这是一个正数；存1，代表这是一个负数。

那么我们能表达的最小数字便是：11111111即$-127$

最大数是：01111111即127

但是接下来的问题头疼了，我们怎么对他们进行运算？

原码vs补码

我们知道，为了尽可能简化CPU内部部件以实现资源的最大化利用，我们的CPU基础部件只能进行加法运算。

那么对于两个正数，我们很好计算，比如$1+1$：

$$1+1=0000\ 0001+0000\ 0001 = 0000\ 0010$$

我们尝试把它变大一点：

$$127+3=0111\ 1111+0000\ 0011= 1000\ 0010$$

多出来了一位！然而很可惜，我们计算机只能存8个bit，所以多出来的1我们虽然放在符号位，但这是不对的，去除符号位的计算结果就是

$$000\ 0010 = 2$$

这就是计算过程中发生了溢出。导致计算结果和实际结果不一致。

但是你又用惊人的注意力发现了：计算结果是2……这刚好就是……？！

$$130\bmod 128=2$$

没错，我们这样子计算，刚好就是在将计算结果对$256$进行模运算。那我们是不是可以巧妙地利用这一特性，通过加法来实现减法呢？

比如说我们有两个数：$50$和$30$，我们需要计算$50-30$

既然在这个计算机中，我们计算的结果都是

$$(A+B) \bmod 128$$

那$50-30$就可以看作

$$\begin{aligned} [50+(-30)]\bmod 128 &=[50+(-30\bmod 128)]\bmod 128\\ &=[50+98]\bmod 128\\ &=148\bmod 128\\ &=20 \end{aligned}$$

哇！天才！台下观众欣喜若狂！

对于二进制数来说，我们怎么表达它呢？

我们在此引入补码的概念。

$-30$的二进制原码是：1001 1110

现在我们除了符号位以外，全部给他取反得到反码：1110 0001

再给它末位加上一，就可以得到补码：1110 0010。

对于正数，我们则规定补码就是其本身。

那么对于$50-30$，我们可以在运算时使用$[50]_{补}+[-30]_{补}$，对于这个计算就变成了

$$0011 \ 0010 + 1110\ 0010 = 1\ 0001\ 0100$$

丢弃溢出的最高位，我们得到0001 0100也就是$20$。

补码的其他好处

如果使用原码，我们会发现一个很尴尬的情况：0有两种表示方法。

即1000 0000表示-0，0000 0000表示+0。

但在补码中，我们可以规定1000 0000表示$-128$，这样就比原码能多存一个数字！表示范围也扩展为$-128$~$127$。

有符号数vs无符号数

以上的带符号的数我们称为有符号数。它们在计算机中以补码形式存储。

但是对于一些其他需求，我们不需要带符号的数，那么我们在计算机中就直接以原码的形式存储，并且不带符号位。

例如在一个8位操作系统中，你使用

unsigned int i = 129;

那么它存的就直接是1000 0001。由于不需要存符号位，无符号数在8bit机器上的存储范围就是0~255。

二、加减法的运算电路

在计算机中，传统的运算器由算术逻辑单元ALU、移位器、状态寄存器PSW和通用寄存器组等组成。

但是我们先别管那么多，首先我们来看ALU。ALU的核心部件是加法器。

1. 一位全加器

我们回忆一下手写运算。

当我们计算$1011101+0101100$时，用竖式来计算就是

$$\begin{array}{r} 1011101 \\ +\,0101100 \\ \hline 10001001 \end{array}$$

也就是，对每一位数单独进行加法运算，如果加和结果≧2，则向高位进1。

同样地，计算机进行加法运算也是这种思路。我们先试想一个最简单的加法电路：一位全加器。

在进行一个单位的加法时，我们需要处理三个输入：加数$A_i$、加数$B_i$、来自低位的进位$C_{i-1}$。它也会产生两个输出：加和结果的本位$S_i$和想高位的进位$C_i$。

我们先来分析一下如何计算$S_i$：

• 当$A_i$与$B_i$相同，它们俩的加和结果的本位肯定是0。毕竟$0+0=0$，$1+1=10$。
• $A_i$与$B_i$不同是，它们的加和结果肯定是1。

根据这一思路，计算二进制$A_i+B_i$可以用逻辑电路XOR表示，即$A_i \oplus B_i$。

现在我们把进位$C_i$用同样的思路放进这个加法式中：若$(A_i \oplus B_i)$和$C_i$相同则为0，$(A_i \oplus B_i)$和$C_i$不同则为1。即计算可以用$(A_i \oplus B_i) \oplus C_i$来表示，那么就有：

$$S_i = A_i \oplus B_i \oplus C_{i-1}$$

我们接下来看进位$C_i$：

• 当$A_i$和$B_i$均为1，则产生进位。毕竟$1+1=10$。
• 当$A_i$和$B_i$只有一个为1时：
  • 若上一位运算的进位$C_{i-1}$是1，则产生进位。
  • 如果$C_{i-1}$是0，那$1+0=1$肯定不产生进位。

从结果上来讲，就是：$A_i$为1且$B_i$为1，或，$A_i$和$B_i$相异 且 $C_i$为1。

整理成逻辑表达式就是：

$$C_i=A_iB_i+(A_i \oplus B)C_{i-1}$$

那么一位全加器的逻辑结构就如下图所示。

我们把它封装起来，仅对外保留输入输出，那它的逻辑符号表示为：

2. 串行进位加法器

将$n$个全加器级联就可以构成$n$位串行进位加法器（又称行波进位加法器），如下图所示

将它们这样子串在一起，就可以轻松实现两个二进制数的加法。

我们把它封装成一个整体，就得到了传统的加法器。

3. 带标志加法器

对于$n$位加法器来说，除了得到运算结果外，我们经常需要知道计算过程中是否发生了溢出、结果正负性、结果是否为零等等信息。

我们要求加法器能生成以下标志位：

• $OF$：溢出标志，为1表示溢出，0表示未溢出。$OF=C_n \oplus C_{n-1}$
• $SF$：符号标志，等于结果的最高有效位，1表示负，0表示正。$SF=S_{n-1}$
• $ZF$：零标志，1表示加减运算的结果为$0$。在所有位均为0时设置为1。
• $CF$：进位/借位标志，用于判断无符号数的加减运算是否发生溢出。1表示溢出，0表示未溢出。

加法器的符号就可以表示为：

溢出的判别方法

我们知道，补码的加减法运算仅在同号相加或异号相减的情况下可能溢出。这在直观上很好理解，因为两个同号数相减时，结果的绝对值肯定会小于减数或被减数的绝对值。

在8bit机器中，当运算结果超出127时，它会回到-128。例如$127+3=-126$。我们依此可以设计出一个非常直观的判断方法：当两个数的符号相同时，若计算结果的符号和它们不同，则发生了溢出。

1）采用一位符号位

设参与运算的两个数的符号位分别为$A_i$和$B_i$，运算结果的符号位是$S_i$，可得溢出逻辑表达式：

$$V=A_iB_i\overline{S_i}+\overline{A_i}\overline{B_i}S_i$$

2）采用一位符号位并结合进位

• 如果两个数是正数，那它的符号位都是0，肯定不会向后进位。
  • 此时如果次高位未向它进位，说明符号没有改变，符号位仍然是0。
  • 此时次高位向它进了一位，那符号位就变成1了，符号改变，发生溢出。
• 两数为负数时同理，它们符号位都是1，必会向后进一位，且相加后本位是0。
  • 如果次高位向它进1，则符号位还是1，未溢出。
  • 若次高位未向它进位，则符号位0，符号改变，发生溢出。

总结一下，如果最高位和次高位发生的进位不同，则溢出。

换言之，假设计算后符号位产生的进位是$C_n$，次高位（数值的最高位）产生的进位是$C_{n-1}$，若$C_n$与$C_{n-1}$不同，则表示溢出。

$$V=C_{i} \oplus C_{i-1}$$

三、加减运算电路

Finally! 大的要来了！但是在这之前我们要了解一个小插曲。

1. MUX多路选择器

在加减法电路中，我们需要一个二选一多路选择器MUX，用它来控制进行加法还是减法。

思路很简单，如果是减法，则给减数取相反数。也就是

$$X-Y \rightarrow X+(-Y)$$

我们同时给MUX输入$Y$和$\overline{Y}$，并给其一个信号Sub

• 如果Sub为0，则说明进行加法，MUX选择$Y$输出
• 如果Sub是1，进行减法，MUX选择$\overline{Y}$输出

$\overline{Y}$是$Y$的反相。如果$Y=1010$，则$\overline{Y}=0101$。

2. 运算电路

我们把MUX接到加法器的一端，就有了如下电路：

在计算机中，有符号数和无符号数的加减运算，均采用这样的同一套电路实现。它的输入端包括连个$n$位操作数$X$和$Y$，还有一个控制信号$Sub$。

控制信号$Sub$不仅决定选择哪一路数据进入加法器，在执行减法时（$Sub$为1）作为最低位的进位输入。

现在大功告成了，我们来一步一步解析加减法运算时的工作原理。

加法运算

• $X$直接被输入到加法器中
• $Sub$为0，所以MUX选择$Y$输入到加法器中
• 加法器直接运算$X+Y+C_{in}$，并输出$n$位结果$F$和进位输出$C_{out}$，并生成状态标志位

值得注意的是，如果$X$和$Y$是无符号数，那么结果$F=(X+Y)\mod2^n$，如果$X+Y\ge2^n$，就会产生进位$C_{out}=1$，就表示发生无符号溢出。

减法运算

• $X$直接被输入到加法器中
• $Sub$为1，所以MUX选择$\overline{Y}$输入到加法器
• 加法器运算$X+\overline{Y}+C_{in}$，也就是$X+\overline{Y}+1$

如果此时我们在计算有符号数的减法，那么$[Y]_补$取反再+1刚好就是$[-Y]_补$，所做的运算就等同于$X+(-Y)$。

另外，如果计算的是无符号数减法，我们规定溢出标志OF是$C_{out}$取反。即$OF=\overline{C_{out}}$。这一点和无符号数加法正好相反。

因为运算等价于$X-Y+2^n$，那么

• $X\ge Y$时，$X-Y+2^n \ge 2^n$，有进位。
• $X< Y$时，$X-Y+2^n < 2^n$，无进位$C_{out}=0$，此时$OF=\overline{C_{out}}=1$，表示溢出。

尾声

老妈推门而入，怒目圆瞪地盯着你的电脑屏幕，但此时你打开的是三叶的博客！

原来你在学习二进制加减法，她满意地点点头，这个人博客写的还可以的，你记得把他的RSS添加到订阅里。