1. 计算机中数的表示¶

1.1. 为什么计算机用二进制计数¶

人类的计数方式通常是“逢十进一”，称为十进制（Decimal），大概因为人有十个手指，所以十进制是最自然的计数方式，很多民族的语言文字中都有十个数字，而阿拉伯数字0~9是目前最广泛采用的。

计算机是用数字电路搭成的，数字电路中只有1和0两种状态，所以对计算机来说二进制（Binary）是最自然的计数方式。根据“逢二进一”的原则，十进制的1、2、3、4分别对应二进制的1、10、11、100。二进制的一位数字称为一个位（bit） [1] ，三个bit能够表示的最大的二进制数是111，也就是十进制的7。不管用哪种计数方式，数的大小并没有变，十进制的1+1等于2，二进制的1+1等于10，二进制10和十进制2的大小是相等的。计算机采用如下的逻辑电路计算两个bit的加法：

1-bit Full Adder

图的上半部分（出自Wikipedia）的电路称为一位全加器（1-bit Full Adder），图的下半部分是一些逻辑电路符号的图例。我们首先解释这些图例，逻辑电路由门电路（Gate）和导线（Wire）组成，同一条导线上在某一时刻的电压值只能是高和低两种状态之一，分别用1和0表示。如果两条导线短接在一起则它们的电压值相同，在接点处画一个黑点，如果接点处没有画黑点则表示这两条线并没有短接在一起，只是在画图时无法避免交叉而已。导线的电压值进入门电路的输入端，经过逻辑运算后在门电路的输出端输出运算结果的电压值，任何复杂的加减乘除运算都可以分解成简单的逻辑运算。AND、OR和NOT运算在 布尔代数 中讲过了，这三种逻辑运算分别用与门、或门和反相器（Inverter）实现。另外几种逻辑运算在这里补充一下。异或（XOR，eXclusive OR）运算的真值表如下：

异或运算用一句话概括就是：两个操作数相同则结果为0，两个操作数不同则结果为1。与非（NAND）和或非（NOR）运算就是在与、或运算的基础上取反：

如果把与门、或门和反相器组合来实现NAND和NOR运算，则电路过于复杂了，因此逻辑电路中通常有专用的与非门和或非门。现在我们看看上图中的AND、OR、XOR是怎么实现两个bit的加法的。A、B是两个加数，C_in 是低位传上来的进位（Carry），相当于三个加数求和，三个加数都是0则结果为0，三个加数都是1则结果为11，即输出位S是1，产生的进位C_out 也是1。下面根据加法的规则用真值表列出所有可能的情况：

请读者自己验算上面的电路图是否正确实现了这个真值表。如果把很多个一位全加器串接起来，就成了多位加法器，如下图所示（该图出自Wikipedia）：

4-bit Ripple Carry Adder

图中的一位全加器用方框表示，上一级全加器的C_out 连接到下一级全加器的C_in ，让进位像涟漪一样一级一级传开，所以叫做Ripple Carry Adder，这样就可以把两个4 bit二进制数A₃A₂A₁A₀ 和B₃B₂B₁B₀ 加起来了。在这里介绍Ripple Carry Adder只是为了让读者理解计算机是如何通过逻辑运算来做算术运算的，实际上这种加法器效率很低，只能加完一位再加下一位，更实用、更复杂的加法器可以多个位一起计算，有兴趣的读者可参考 [数字逻辑基础] 的5.4节。

1.2. 不同进制之间的换算¶

在十进制中，个位的1代表10⁰=1，十位的1代表10¹=10，百位的1代表10²=100，所以

123=1×10²+2×10¹+3×10⁰

同理，在二进制中，个位的1代表2⁰=1，十位的1代表2¹=2，百位的1代表2²=4，所以

(A₃A₂A₁A₀)₂=A₃×2³+A₂×2²+A₁×2¹+A₀×2⁰

如果二进制和十进制数出现在同一个等式中，为了区别我们用(A₃A₂A₁A₀)₂ 这种形式表示A₃A₂A₁A₀ 是二进制数，每个数字只能是0或1，其他没有套括号加下标的数仍表示十进制数。对于(A₃A₂A₁A₀)₂ 这样一个二进制数，最左边的A₃ 位称为最高位（MSB，Most Significant Bit），最右边的A₀ 位称为最低位（LSB，Least Significant Bit）。以后我们遵循这样的惯例：假设一个数是32位的，则LSB称为第0位而不是第1位（这一位上的1表示2⁰ ），MSB称为第31位（这一位上的1表示2³¹ ）。上式就是从二进制到十进制的换算公式。作为练习，请读者算一下(1011)₂ 和(1111)₂ 换算成十进制分别是多少。

下面来看十进制怎么换算成二进制。我们知道

13=1×2³+1×2²+0×2¹+1×2⁰

所以13换算成二进制应该是(1101)₂ 。问题是怎么把13分解成等号右边的形式呢？注意到等号右边可以写成

13=(((0×2+1₃)×2+1₂)×2+0₁)×2+1₀

我们将13反复除以2取余数就可以提取出上式中的1101四个数字，为了让读者更容易看清楚是哪个1和哪个0，上式和下式中对应的数字都加了下标：

13÷2=6...1₀

6÷2=3...0₁

3÷2=1...1₂

1÷2=0...1₃

把这四步得到的余数按相反的顺序排列就是13的二进制表示，因此这种方法称为除二反序取余法。

计算机用二进制表示数，程序员也必须习惯使用二进制，但二进制写起来太啰嗦了，所以通常将二进制数分成每三位一组或者每四位一组，每组用一个数字表示。比如把(10100011)₂ 从最低位开始每三位分成一组，即(10,100,011)₂ ，然后把每组写成一个0~7的数字，就是(243)₈ ，这种表示法的特点是逢八进一，称为八进制（Octal）。类似地，我们也可以把(10100011)₂ 按每四位分成一组，即(1010,0011)₂ ，然后把每组写成一个数字，这个数的低位是3，高位已经大于9了，我们规定用字母A~F表示10~15，则这个数可以写成(A3)₁₆ ，每一位数字的取值范围是0~F，逢十六进一，称为十六进制（Hexadecimal）。所以，八进制、十六进制是程序员为了书写二进制方便而发明的简便写法，就像草书和正楷的关系一样。

习题

1. 二进制小数可以这样定义：

   (0.A_-1A_-2A_-3...)₂=A_-1×2^-1+A_-2×2^-2+A_-3×2^-3+...

   这个定义同时也是从二进制小数到十进制小数的换算公式。从本节讲的十进制转二进制的推导过程出发类比一下，十进制小数换算成二进制小数应该怎么算？

2. 思考一下，八进制（或十六进制）与十进制之间如何相互换算？

1.3. 整数的加减运算¶

我们已经了解了计算机中正整数如何表示，加法如何计算，那么负数如何表示，减法又如何计算呢？本节讨论这些问题。为了书写方便，本节举的例子都是8位二进制数的计算，实际计算机做整数加减运算的操作数可以是8位、16位、32位或64位的。

1.3.3. 2’s Complement表示法¶

上一节以8位二进制数为例介绍了1’s Complement表示法，我们在此基础上稍加修改，得到2’s Complement表示法：

1. 0和正数的补码就是它本身，取值范围是0~01111111（0~127）。
2. 负数的补码是在1’s Complement表示法的基础上再加1，取值范围是10000000~11111111（-128~-1）。
3. 0和正数补码的最高位都是0，负数补码的最高位都是1，所以最高位仍可以看作符号位。
4. 如果是减法运算，先改写成加法运算，然后把各加数取补码后相加，忽略计算结果最高位的进位 [3] ，计算结果也是补码表示的。

[3]	读者如果对“忽略计算结果最高位的进位”这个步骤放心不下，仍可以分几种情况自行验证：两个正数相加；两个负数相加；一正一负相加得正；一正一负相加得负；任何数加0结果不变（这个显然，因为0现在只有一种补码表示就是0）。

目前绝大多数计算机都采用这种补码表示法。为什么称为“2的补码”呢？我们看一个例子，用8位二进制数来表示-4的补码是这样算的：

11111111-00000100+1=100000000-00000100=2⁸-4

同理，如果用32位二进制数来表示-4的补码，应该等于2³²-4。

采用2’s Complement表示法，8位二进制数可以表示的取值范围是-128~127，如果计算结果超出这个范围就会产生溢出，例如：

有符号数加法溢出

如何判定产生了溢出呢？我们还是分几种情况讨论：如果两个正数相加溢出，结果一定是负数；如果两个负数相加溢出，结果一定是正数；一正一负相加，无论结果是正是负都不可能溢出。

如何判定溢出

从上图可以得出结论：在相加过程中最高位产生的进位和次高位产生的进位如果相同则表示没有溢出，如果不同则表示有溢出。在逻辑电路中可以把这两个进位连接到一个异或门，把异或门的输出连接到溢出标志。

1.3.4. 有符号数和无符号数¶

前面几节我们用8位二进制数表示正数和负数，讲了三种表示法，每种表示法对应一种计算规则，取值范围也略有不同，这称为有符号数（Signed Number）；如果直接用8位二进制数表示0~255，这称为无符号数（Unsigned Number）。其实计算机做加法时并不区分操作数是有符号数还是无符号数，计算过程都一样，比如上一节的例子也可以看作无符号数的加法：

无符号数加法进位

如果把这两个操作数看作有符号数-126和-8相加，计算结果是错的，因为产生了溢出；但如果看作无符号数130和248相加，计算结果是122进1，也就是122+256，这个结果是对的。计算机的加法器在做完计算之后，根据最高位产生的进位设置进位标志（Carry Flag），同时根据最高位和次高位产生的进位的异或设置溢出标志。至于这个加法到底是有符号数加法还是无符号数加法则取决于程序怎么理解了，如果程序把它理解成有符号数加法，下一步就要检查溢出标志，如果程序把它理解成无符号数加法，下一步就要检查进位标志。

通常计算机在做算术运算之后还可能设置另外两个标志：如果计算结果的所有bit都是零则设置零标志（Zero Flag），如果计算结果的最高位是1则设置负数标志（Negative Flag或Sign Flag）。如果程序把计算结果理解成有符号数，也可以检查负数标志判断结果是正是负。

1.4. 浮点数¶

浮点数在计算机中的表示是基于科学计数法（Scientific Notation）的，我们知道32767这个数用科学计数法可以写成3.2767×10⁴ ，3.2767称为尾数（Mantissa，或者叫Significand），4称为指数（Exponent）。浮点数在计算机中的表示与此类似，只不过基数（Radix）是2而不是10。下面我们用一个简单的模型来解释浮点数的基本概念。我们的模型由三部分组成：符号位、指数部分（表示2的多少次方）和尾数部分（小数点前面总是0，尾数部分只表示小数点后的数字）。

一种浮点数格式

如果要表示17这个数，我们知道17=17.0×100=0.17×10² ，类似地，17=(10001)₂×2⁰=(0.10001)₂×2⁵ ，这样就可以表示为：

17的浮点数表示

如果我们要表示0.25就遇到新的困难了，因为0.25=1×2^-2=(0.1)₂×2^-1 ，而我们的模型中指数部分没有规定如何表示负数。我们可以在指数部分规定一个符号位，然而更广泛采用的办法是使用偏移的指数（Biased Exponent）。规定一个偏移值，比如16，实际的指数要加上这个偏移值再填写到指数部分，这样比16大的就表示正指数，比16小的就表示负指数。要表示0.25，指数部分应该填16-1=15：

0.25的偏移指数浮点数表示

现在还有一个问题需要解决：每个浮点数的表示都不唯一，例如17=(0.10001)₂×2⁵=(0.010001)₂×2⁶ ，这样给计算机处理增加了复杂性。为了解决这个问题，我们规定尾数部分的最高位必须是1，也就是说尾数必须以0.1开头，对指数做相应的调整，这称为正规化（Normalize）。由于尾数部分的最高位必须是1，这个1就不必保存了，可以节省出一位来用于提高精度，我们说最高位的1是隐含的（Implied）。这样17就只有一种表示方法了，指数部分应该是16+5=21=(10101)₂ ，尾数部分去掉最高位的1是0001：

17的正规化尾数浮点数表示

两个浮点数相加，首先把小数点对齐然后相加：

浮点数相加

由于浮点数表示的精度有限，计算结果末尾的10两位被舍去了。做浮点运算时要注意精度损失（Significance Loss）的问题，有时计算顺序不同也会导致不同的结果。比如：

11.0010000+0.00000001+0.00000001=11.0010000+0.00000001=11.0010000

后面加的两个很小的数全被舍去了，没有对计算结果产生任何影响。但如果调一下计算顺序它们就能影响到计算结果了：

0.00000001+0.00000001+11.0010000=0.00000010+11.0010000=11.0010001

再比如128.25=(10000000.01)₂ ，需要10个有效位，而我们的模型中尾数部分是8位，算上隐含的最高位1一共有9个有效位，那么128.25的浮点数表示只能舍去末尾的1，表示成(10000000.0)₂ ，其实跟128相等了。

整数运算会产生溢出，浮点运算也会产生溢出，浮点运算的溢出也分上溢和下溢两种，但和整数运算的定义不同。假设整数采用8位2’s Complement表示法，取值范围是-128~127，如果计算结果是-130则称为下溢，计算结果是130则称为上溢。假设按本节介绍的浮点数表示法，取值范围是-(0.111111111)₂×2¹⁵~(0.111111111)₂×2¹⁵ ，如果计算结果超出这个范围则称为上溢；如果计算结果未超出这个范围但绝对值太小了，在-(0.1)₂×2^-16~(0.1)₂×2^-16 之间，那么也同样无法表示，称为下溢。

浮点数是一个相当复杂的话题，不同平台的浮点数表示和浮点运算在实现上也有较大差异，本节只是通过这个简单的模型介绍一些基本概念而不深入讨论，理解了这些基本概念有助于你理解浮点数标准，目前业界广泛采用的浮点数标准是由IEEE（Institute of Electrical and Electronics Engineers）制定的IEEE 754。

在 布尔代数 讲过浮点数不能做精确比较，现在读者应该知道为什么不能精确比较了：首先，浮点数的精度有限；其次，浮点数是用二进制的科学计数法表示的，通常不能精确地表示十进制数的小数部分。本节前面举例的时候总是用十进制的0.25，如果换成十进制的0.1就没法精确地用二进制小数来表示了。我们把 布尔代数 的例子拿过来再研究一下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <stdio.h>

int main(void)
{
        double a = 0.3 - 0.2;
        double b = 0.2 - 0.1;
        if (a == b)
               printf("Equal\n");
        else
               printf("Unequal\n");

        printf("a=%.18f\n", a);
        printf("b=%.18f\n", b);
        return 0;
}

其中 printf 的转换说明 %.18f 表示打印时保留小数点后18位的精度。运行结果是:

Unequal
a=0.099999999999999978
b=0.100000000000000006

最后讨论一个细节问题。我们知道，定义全局变量时如果没有Initializer就用0初始化，定义数组时如果Initializer中提供的元素不够那么剩下的元素也用0初始化。例如：

1
2
3

int i;
double d;
double a[10] = { 1.0 };

“用0初始化”的意思是变量 i 、变量 d 和数组元素 a[1]~a[9] 的所有字节都用0填充，或者说所有bit都是0。无论是用Sign and Magnitude表示法、1’s Complement表示法还是2’s Complement表示法，一个整数的所有bit是0都表示0值，但一个浮点数的所有bit是0一定表示0值吗？严格来说不一定，某种平台可能会规定一个浮点数的所有bit是0并不表示0值，但 [C99Rationale] 第6.7.8节提到：

As far as the committee knows, all machines treat all bits zero as a representation of floating-point zero. But, all bits zero might not be the canonical representation of zero.

因此在绝大多数平台上，一个浮点数的所有bit是0就表示0值。