第二章：信息的表示和处理

csapp
loading...

信息的表示和处理

现代计算机存储和处理的信息以二值信号表示。这些微不足道的二进制数字，或者称为位（bit）, 形成了数字革命的基础。大家熟悉并使用了 1000 多年的十进制（以 10 为基数）起源于印度，在 12 世纪被阿拉伯数学家改进，并在 13 世纪被意大利数学家 Leonardo Pisano（大约公元 1170—1250，更为大家所熟知的名字是 Fibonacci）带到西方。对于有 10 个手指的人类来说，使用十进制表示法是很自然的事情，但是当构造存储和处理信息的机器时，二进制值工作得更好。二值信号能够很容易地被表示、存储和传输，例如，可以表示为穿孔卡片上有洞或无洞、导线上的高电压或低电压，或者顺时针或逆时针的磁场。对二值信号进行存储和执行计算的电子电路非常简单和可靠，制造商能够在一个单独的硅片上集成数百万甚至数十亿个这样的电路。

孤立地讲，单个的位不是非常有用。然而，当把位组合在一起，再加上某种解释 （interpretation），即赋予不同的可能位模式以含意，我们就能够表示任何有限集合的元素。比如，使用一个二进制数字系统，我们能够用位组来编码非负数。通过使用标准的字符码，我们能够对文档中的字母和符号进行编码。在本章中，我们将讨论这两种编码，以及负数表示和实数近似值的编码。

2.1 信息存储

大多数计算机使用 8 位的块，或者字节（byte），作为最小的可寻址的内存单位，而不是访问内存中单独的位。机器级程序将内存视为一个非常大的字节数组，称为虚拟内存（virtual memory）。内存的每个字节都由一个唯一的数字来标识，称为它的地址（address），所有可能地址的集合就称为虚拟地址空间（virtual address space）。顾名思义，这个虚拟地址空间只是一个展现给机器级程序的概念性映像。实际的实现（见第 9 章）是将动态随机访问存储器（DRAM）、闪存、磁盘存储器、特殊硬件和操作系统软件结合起来，为程序提供一个看上去统一的字节数组。

2.1.1 十六进制表示法

1个字节由8个位组成，在二进制表示法中，每一个位的值可能有两种状态，0或者1。当这8个位全为0，表示一个字节的最小值。当这8个位全为1时，表示最大值。用十进制来表示，一个字节的取值范围就在0~255之间。我们把这种按照一位一位表示数据的方式称为位模式。使用二进制表示法比较冗长，而十进制表示法与位模式之间的转换又比较麻烦。因此，我们引入十六进制数来表示位模式。
我们熟悉的十进制，是由数字0~9组成的。对于十六进制数，则是由数字0~9和字母A~F来表示16个可能的数值。

2.1.2 字数据大小

每台计算机都有一个字长（word size），指明指针数据的标称大小（nominal size）。因为虚拟地址是以这样的一个字来编码的，所以字长决定的最重要的系统参数就是虚拟地址空间的最大大小。也就是说，对于一个字长为w位的机器而言，虚拟地址的范围为0~2ʷ -1，程序最多访问2ʷ 个字节。

大多数64位机器也可以运行为32位机器编译的程序，这是一种向后兼容。

2.1.3 寻址和字节顺序

对于跨越多字节的程序对象，我们必须建立两个规则：这个对象的地址是什么，以及在内存中如何排列这些字节。多字节对象的地址是什么？在几乎所有的机器上，多字节对象都被存储为连续的字节序列，对象的地址为所使用字节中最小的地址。例如。假设一个类型为int的变量x的地址为0x100，也就是说，地址表达式&x的值为0x100，那么，x的4个字节将被存储在存储器0x100,0x101,0x102和0x103位置。

某些机器选择在存储器中按照从最低有效字节到最高有效字节顺序存储对象，而另一些机器则按照从最高有效字节到最低有效字节顺序存储。前一种规则—最低有效字节在最前面的方式称为小端法。后一种规则—最高有效字节在最前面的方式称为大端法。

举个例子。假设变量X类型为int，位于地址0x100处，它的十六进制值为0x01234567。地址范围为0x100-0x103的字节。其排列顺序依赖于机器类型

1
2
3
        0x100            0x101          0x102           0x103
大端法    01               23              45             67
小端法    67               45              23             01

2.1.4 表示字符串

C语言中字符串被编码为一个以null(值为0)字符串的字符数组。每个字符都由某个标准编码表示。最常见的是ASCII字符码。在使用ASCII码作为字符码的任何系统上都将得到相同的结果。与字节顺序和字大小规则无关。因而，文本数据比二进制数据具有更强的平台独立性。

2.1.5 表示代码

考虑下面的C函数

1
2
3
int sum(int x, int y) {
    return x + y;
}

当我们在示例机器上编译时，生产如下字节表示的机器代码：

1
2
3
4
Linux: 55 89 e5 8b 45 0c 03 45 08 89 ec 5d c3
NT: 55 89 e5 8b 45 0c 03 45 08 89 ec 5d c3
Sun: 81 C3 E0 08 90 02 00 09
Alpha: 00 00 30 42 01 80 FA 6B

我们发现指令的编码是不同的。不同的机器类型使用的不同且不兼容的指令和编码方式。即使是完全一样的进程运行在不同的操作系统上也会有不同的编码规则。因此二进制代码是不兼容的。二进制代码很少能在不同的机器和操作系统组合之间移植。
计算机系统的一个基本概念就是，从机器的角度来看，程序仅仅只是字节序列，机器没有关于原始程序的任何信息，除了可能有些用来帮助调试的辅助表以外。

2.1.6 布尔代数简介

二进制值是计算机编码，存储和操作信息的核心。所以，围绕数值0和1的研究已演化出了丰富的数学知识体系。这起源于1850年前后乔治.布尔的工作。因此也称为布尔代数。布尔注意到通过将逻辑值TRUE(真)和FALSE(假)编码为二进制1和0，能够设计出一种代数，以研究逻辑推理的基本原则。

最简单的布尔代数是在二元集合{0,1}基础上定义。如图定义了这种布尔代数的几种运算。我们用来表示这些运算的符号是和C语言的低级运算使用的符号相匹配的。

2.1.7 C语言中的位级运算

C语言的一个很有用的特性就是它支持按位布尔运算。事实上，我们在布尔运算中使用的那些符号就是C语言所使用的：|就是OR(或)，&就是AND(与)，~就是NOT（取反），而^就是EXCLUSIVE-OR(异或)。这些运算能运用到任何“整型”的数据类型上，如下图所示。

正如示例说明的哪有，确定一个位级表达式的结果最好的方法，就是将十六进制的参数扩展成二进制并执行二进制运算，然后在转换回十六进制。

2.1.8 C语言中的逻辑运算

C语言还提供了一组逻辑运算符||、&&和！，分别对应命题逻辑中的OR、AND和NOT运算。逻辑运算很容易和位级运算相混淆，但它们的功能是完全不同的。逻辑运算认为所有非零的参数都表示TRUE，而参数0表示FALSE。它们返回1或者0，分别表示结果的TRUE和FALSE。以下是一些表达式求值的示例。

可以观察到，安危运算只有在特殊的情况下，也就是参数被限制为0或者1时，才和与其对应的逻辑运算具有相同的行为。

逻辑运算&&和||与它们对应的位级运算符&和|之间第二个重要的区别是，如果对第一个参数求值，就能确定表达式的结果，那么逻辑运算符就不会对第二个参数求值。

2.1.9

C语言标准并没有明确定义对于有符号数应该使用那种类型的右移-算术右移或右移可以，不幸的地，这就意味着任何假设一种或者另一种右移形式的代码都可能会遇到植性问题。然而，实际上，几乎所有的编译器/机器组合都对有符号的数使用算术右移，程序员也都假设会使用这种右移。另一方面，对于无符号数，右移必须是逻辑的。

2.2 整数表示

在本节中，我们描述用位来编码整数的两种不同的方式：一种只能表示非负数，而一种能够表示负数、零和正数。

2.2.1 整型数据类型

C语言支持多种整形数据类型–表示有限的整数。每种类型都能用关键字来指定大小，这些关键字包括 char、short、long,同时还可以指示被表示的数字是非负数（生明为unsigned）, 或者可能是负数（默认）。
C语言标准定义了每种数据类型必须能够表示的最小的取值范围。

2.2.2 无符号数的编码

2.2.3 补码编码

  • 反码
    最高位为符号位，0表示正数，1表示负数。
    正数的反码等于本身，负数的反码除符号位外，各位取反：

X = 0b11 (3)，四比特表示原码 = 0011(3)，对应反码为 = 0011(3) ；
X = - 0b11(-3) ，四比特表示原码 = 1011(11)，对应反码为 = 1100(12) ；

  • 补码

最高位为符号位，0表示正数，1表示负数。
正数的补码等于本身，负数的补码等于反码+1

X = 0b11 (3)，四比特表示原码 = 0011(3)，对应反码为 = 0011(3) ，补码为 = 0011(3)；
X = - 0b11(-3) ，四比特表示原码 = 1011(11)，对应反码为 = 1100(12)，补码为1101(13) ；

2.2.4 有符号和无符号数之间的转换

C语言允许在各种不同的数字数据类型之间做强制类型转换。对于大多数C语言的实现，处理同样字长的有符号数和无符号数直接相互转换的一般规则是：数值可能会改变，但是位模式不变。

2.2.5 C语言种的有符号数于无符号数

C语言支持所有整形数据类型的有符号和无符号运算。尽管C语言标准没有指定有符号数要采用某种表示，但是几乎所有的机器都使用补码。通常大多数数字都莫问时有符号的。
C语言允许无符号数和有符号数之间的转换。虽然C标准没有精确规定应如何进行这种转换，单大多数系统都遵循的原则时底层的位表示保持不变。

2.2.6 扩展一个数字的位表示

一个常见的运算时在不同字长的整数之间转换，同时又保持数值不变。当然，当目标数据类型太小以至于不能表示想要的值时，这根本时不可能的。然而，从一个较小的数据类型转换到一个较大的类型，应该总是可能的。
要将一个无符号数转换位一个更大的数据类型，我们只要简单地在表示开头添加0。这种运算被称为零扩展。
要将一个补码数字转换为一个更大的数据类型，可以植性一个符号扩展，在表示中添加最高有效位的值。
As an example, consider the following code:

1
2
3
4
5
6
7
8
9
10
11
12
short sx = val; /* -12345 */
unsigned short usx = sx; /* 53191 */
int x = sx; /* -12345 */
unsigned ux = usx; /* 53191 */5
printf("sx = %d:\t", sx);
show_bytes((byte_pointer) &sx, sizeof(short));
printf("usx = %u:\t", usx);
show_bytes((byte_pointer) &usx, sizeof(unsigned short));
printf("x = %d:\t", x);
show_bytes((byte_pointer) &x, sizeof(int));
printf("ux = %u:\t", ux);
show_bytes((byte_pointer) &ux, sizeof(unsigned));
1
2
3
4
sx = -12345: cf c7
usx = 53191: cf c7
x = -12345: ff ff cf c7
ux = 53191: 00 00 cf c7

可以看出，尽管-12345的补码表示和53191的无符号表示在16位字长时是相同的，但是在32为字长是却是不同的。特别地，-12345的十六进制表示为0xffffcfc7,而53191的十六进制表示为0x0000CFC7，前者使用的是符号扩展–最开头加了16位，都是最高有效位1，表示为十六进制就是0xFFFF。后者开头使用16个0来扩展，表示为16进制就是0x0000。

2.2.7 截断数字

假设我们不用额外的位来扩展一个数字，而是减少表示一个数字的位数。例如下面代码种这种情况：

1
2
3
int x = 53191;
short sx = (short) x; // -12345
int y = sx ;          // -12345

当我们把x强制类型转换位short时，我们就将32位的int截断为了16位的short int. 就像前面所看见的，这个16位的位模式就是-12345的补码表示。当我们把它强制类型转换为int 时，符号扩展把最高位16位设置为1，从而生成-12345的32位补码表示。

2.2.8 关于有符号数与无符号数的建议

就像我们看到的那样，有符号数到无符号数的隐式强制类型转换导致了某些非直观的行为。而这些非直观的特性经常导致程序错误，并且这种包含隐式强制类型转换的细微差别的错误很难被发现。因为这种强制类型转换是在代码中没有明确指示下发生的，程序员往往经常忽视了它的影响。
当我们想要把字仅仅看做是位的集合而没有任何数字意义是，无符号数值是非常有用的，例如，往一个字中放入描述各种布尔条件的标记时，就是这样。地址自然地就是无符号的，所以系统程序员发现无符号类型是很有帮助的。当实现模运算和多精度运算的数学包时，数字时由数组来表示的，无符号值也会非常有用。

2.3 整数运算

许多刚入门的程序员非常惊奇地发现，两个正数相加会得出一个负数，而比较表达式x<y和比较表达式x-y<0会产生不同的结果。这些属性时由于计算机运算的有限性造成的。理解计算机运算的细微之处能够帮助程序员编写更可靠的代码。

2.3.1 无符号加法

考虑两个非负整数x和y ,满足0<=x,y<2的w次方。每个数都能表示为w位无符号数字。然而，如果计算它们的和，我们就有一个可能的范围0<=x+y<=2的w+1次方-2，表示这个和可能需要w+1位。如果保持和为一个w+1位的数字，并且把它加上另外一个数值，我们可能需要w+2个位，以此类推。这种持续的“字长膨胀”意味着，要想完整地表示算术运算的结果，我们不能对字长做任何限制。

原理：无符号数加法

左边的和:x+y映射到右边的无符号 w 位的和 x+y。正常情况下：x+y的值保持不变，而溢出情况则是该和数减去 2^w^ 的结果。

推导：无符号数加法:

一般而言，我们可以看到，如果 x+y<2^w^ 和的 w+1 位表示中的最高位会等于 0, 因此丢弃它不会改变这个数值。另一方面，如果 2^w^<=x+y<2^w+1^ 和的 w+1 位表示中的最高位会等于 1，因此丢弃它就相当于从和中减去了 2^w^

2.3.2 补码加法

对于补码加法，我们必须确定当结果太大或者太小时，应该做些什么。

原理：补码加法

其中，左边的和 x+y 的取值范围为 -2^w^ <= x+y <= 2^w^-2, 右边显示的是该和数截断为 w 位补码的结果。当和 x+y 超过:2^w^-2，我们说发生了正溢出。在这种情况下，截断的结果是从和数中减去 2^w^ 当和 x+y 小于 -2^w^, 我们说发生了负溢出。在这种情况下，截断的结果是把和数加上 2^w^ 两个数的 w 位补码之和与无符号之和有完全相同的位级表示。实际上，大多数计算机使用同样的机器指令来执行无符号或者有符号加法。

2.3.4 补码乘法

原理：无符号数乘法

2.3.5 补码乘法

2.3.6 乘以常数

2.3.7 除以 2 的幂

2.4 浮点数

2.4.1 二进制小数

由二进制数转换成十进制数的基本做法是，把二进制数首先写成加权系数展开式，然后按十进制加法规则求和。这种做法称为”按权相加”法。

例如把二进制数 110.11 转换成十进制数。

2.4.2 浮点数标准

直到1985年，IEEE 组织推出了浮点数标准，就是我们经常听到的 IEEE754 浮点数标准，这个标准统一了浮点数的表示形式，并提供了 2 种浮点格式：

  • 单精度浮点数 float：32 位，符号位 S 占 1 bit，指数 E 占 8 bit，尾数 M 占 23 bit
  • 双精度浮点数 float：64 位，符号位 S 占 1 bit，指数 E 占 11 bit，尾数 M 占 52 bit

各部分作用：

  • 符号（S）：1位二进制位，0表示正数，1表示负数
  • 阶码部分（E）：根据不同的精度E的位数不同（参照下图float与double的区别），表示小数点向右移动的位数。E>0 表示向右移动，E<0表示向左移动。
  • 尾数部分(M）：根据不同的精度M的位数不同参照下图float与double的区别），是浮点数的二进制表示。需要注意的是这里尾数部分为
    ，所以遇到类似0.125这样的小数，其二进制表示为
    ，这时就需要将小数点右移1位才符合要求。

特殊情况：

  • 指数 E 非全 0 且非全 1：规格化数字，按上面的规则正常计算
  • 指数 E 全 0，尾数非 0：非规格化数，尾数隐藏位不再是 1，而是 0(M = 0.xxxxx)，这样可以表示 0 和很小的数
  • 指数 E 全 1，尾数全 0：正无穷大/负无穷大（正负取决于 S 符号位）
  • 指数 E 全 1，尾数非 0：NaN(Not a Number)