一、信息存储

计算机并不访问内存中的单个位，而是使用8位或字节块作为最小的可寻址内存单元。机器级别的程序将内存视为一个非常大的字节数组，称为虚拟内存。内存的每个字节都由一个唯一的数字标识，称为其地址，所有可能的地址集称为虚拟地址空间。如其名称所示，这个虚拟地址空间只是呈现给机器级程序的概念性映像。实际实现是很复杂的，涉及到随机存储器，磁盘存储以及操作系统和一些特殊硬件的配合。

1.1 十六进制表示法

一个字节由8位组成。在二进制表示法中，其值的范围是

0000000

0

2

00000000_2

000000002​到

1111111

1

2

11111111_2

111111112​。当视为十进制整数时，其值的范围为

0

10

0_{10}

010​到

25

5

10

255_{10}

25510​。二进制表示法太冗长了，而十进制表示法与二进制的转换非常繁琐。取而代之的是，我们将二进制改写成以16为基数的数字，或者十六进制数。十六进制（或简称“hex”）使用数字“0”到“9”以及字符“A”到“F”来表示16个可能的值。图2.2显示了与16个十六进制数字相关的十进制和二进制值。以十六进制编写，单个字节的值可以从

0

0

16

00_{16}

0016​到

F

F

16

FF_{16}

FF16​。

在C语言中，以0x或0X开头的数字常量被解释为十六进制。字符“A”到“F”可以用大写或小写书写。例如，我们可以将数字FA1D37B16写成0xFA1D37B，也可以写成0xfa1d37b，甚至可以混合使用大小写，例如0xFA1d37B。

1.2 字（word）

每台计算机都有一个指示数据大小的标准-字（word），它表示整数和指针数据的标准大小。虚拟地址是由字编码的，由字大小决定的最重要的系统参数是虚拟地址空间的最大大小。也就是说，对于具有w位字大小的机器，虚拟地址的范围从0到

2

w

−

1

2^w−1

2w−1，使程序最多可以访问

2

w

2^w

2w字节。

今天大多数个人电脑的字大小为32位。这将虚拟地址空间限制为4GB（写入4GB），即略高于

4

×

1

0

9

4\times10^9

4×109字节。这对于大多数应用程序来说足够使用了，但计算机技术不断发展，许多大型应用程序需要更大的存储空间。因此，随着存储成本的降低，具有64位字长的高端机器正变得越来越常见。随着硬件成本的下降，即使是台式机和笔记本电脑也会切换到64位字号，因此我们将考虑w位字号的一般情况，以及w=32和w=64的特殊情况。

1.3 数据大小

计算机和编译器支持用多种数据类型类编码数据，例如多种长度的整数及浮点数等。许多机器为这些数据类型都设定了特定的机器指令，例如我们可以以2、4及8字节的长度处理整数。C语言也为整型和浮点数据提供了多种数据格式，如下图所示：

从上图可以看出，指针数据（用char *表示）的长度就是机器支持的完整字的长度。

我们在编写程序时应该尽量使得它们可以在不同的机器和编译器之间正确移植。可移植性的一个方面是使程序对不同数据类型的确切大小不敏感。C标准在不同数据类型的数值范围上设置了下限，但是没有上限。自从1980年左右32位机器成为标准以来，许多程序都是按照图2.3中列出的字大小的分配来编写的。由于64位机器的可用性不断提高，许多隐藏的字长依赖项将在将这些程序迁移到新机器时出现bug。例如，许多程序员假设声明为int类型的程序对象可以用来存储指针。这在大多数32位机器上运行良好，但在64位机器上会导致问题。

1.4 寻址及两种编址方式

在几乎所有的机器中，多字节对象都按字节顺序连续存储，并且对象的地址就是这些连续字节的最小地址。例如，假设int类型的变量x具有地址0x100，那么x的4个字节将存储在内存位置0x100、0x101、0x102和0x103中。

字节顺序有两种常见的规定。考虑可以表示为

[

x

w

−

1

，

x

w

−

2

，

…

，

x

1

，

x

0

]

[x_{w−1}，x_{w−2}，…，x_1，x_0]

[xw−1​，xw−2​，…，x1​，x0​]的w位整数，其中

x

w

−

1

x_{w−1}

xw−1​是最高有效位，

x

0

x_0

x0​是最低有效位。假设

w

w

w是8的倍数，这些位可以按字节进行分组，最高有效字节具有位

[

x

w

−

1

，

x

w

−

2

，

…

，

x

w

−

8

]

[x_{w−1}，x_{w−2}，…，x_{w−8}]

[xw−1​，xw−2​，…，xw−8​]，最低有效字节具有位

[

x

7

，

x

6

，

…

，

x

0

]

[x_7，x_6，…，x_0]

[x7​，x6​，…，x0​]，其他字节具有中间的位。有些机器选择对象存储在内存中的顺序是从最低有效字节到最高有效字节，而另一些机器则是从最高有效字节到最低有效字节。将最低有效字节放在第一位的约定称为小端编址（little endian）。大多数与英特尔兼容的机器都遵循这一惯例。将最高有效字节放在第一位的约定称为大端编址（big endian）。IBM和Sun Microsystems的大多数机器都遵循这一惯例。请注意，我们说的是“大多数”。这些约定并不绝对。例如，IBM和Sun都生产使用英特尔兼容处理器的机器，因此都是小端编址。最近的许多微处理器都是双端的，这意味着它们可以被配置成小端或大端机器。

假设变量x类型为int，其内存地址为0x100，数值为0x1234567。大端编址和小端编址的表示方法如下所示：

对于大多数程序员来说，大端编址和小端编址都是不可见的，因为这两种方式都会给出相同的运算结果。然而有的情况需要进行区分。第一种是二进制数据在不同机器之间通过网络进行通信，一个常见的问题是小端机产生的数据被发送到大端机（反之亦然）导致字中的字节与接收程序的顺序相反。为避免此类问题，为网络应用程序编写的代码必须遵循字节排序的既定约定，以确保发送计算机将其内部表示形式转换为网络标准，而接收计算机将网络标准转换为其内部表示形式。

字节排序变得重要的第二种情况是查看表示整数数据的字节序列。这通常发生在检查机器级程序时。例如，以下行出现在一个文件中，该文件给出了英特尔IA32处理器的机器级代码的文本表示形式：

80483bd: 01 05 64 94 04 08 add %eax,0x8049464

上面这行由反汇编器生成，01 05 64 94 04 08是字节级别的指令表示，这个指令表示将一个字大小的数据和存储在内存地址0x8049464处的数据相加。我们取指令的后四个字节64 94 04 08，将它们按反序书写，可以得到08 04 94 64。去掉开头的0，我们可以得到值0x8049464，这就是在上面那行指令最右边的值。在读取为小端机器生成的机器级程序表示时，字节以相反的顺序出现是一种常见的情况。写入字节序列的最自然的方法是将编号（地址）最低的字节放在左边，将编号最高的字节放在右边，但这与通常的写入数字的方法相反（最有效的数字放在左边，最小的数字放在右边）。

字节顺序变得可见的第三种情况是编写绕过正常类型系统的程序。在C语言中，这可以通过使用强制转换（cast）来完成，以允许根据创建对象的不同数据类型引用对象。对于大多数应用程序编程来说，这样的编码技巧是非常不受欢迎的，但是对于系统级编程来说，它们可能非常有用，甚至是必要的。

图2.4显示了使用强制转换来访问和打印不同程序对象的字节表示的C代码。我们使用typedef将数据类型byte_pointer定义为指向类型为“unsigned char”的对象的指针。这样的字节指针引用一个字节序列，其中每个字节被认为是一个非负整数。第一个例程show_bytes是由字节指针和字节计数器指示的字节序列的地址。它以十六进制打印单个字节。C格式化指令“%.2x”指示应以至少两位数字的十六进制格式打印整数。

过程show_int、show_float和show_pointer演示如何使用过程show_bytes分别打印int、float和void类型的C程序对象的字节表示。注意，它们只是传递给show_bytes一个指针&x以及一个长度做为参数，同时这个指针会被强制转换为“unsigned char”类型。此强制转换向编译器表明，程序应将指针视为指向字节序列，而不是指向原始数据类型的对象。然后，该指针将指向对象占用的最低字节地址。

这些过程都使用了C语言中的sizeof操作复来决定对象使用的字节数。通常来讲，表达式sizeof(T)会返回需要存储类型T所需的字节数。

我们在几个不同的机器上运行了图2.5所示的代码，给出了图2.6所示的结果。使用的机器如下所示：

代码如图所示：

结果如下所示：

从上面可以看出，参数12345具有十六进制表示0x00003039。对于int数据，除了字节排序之外，所有机器的结果都是相同的。特别是，我们可以看到，最低有效字节值0x39首先在Linux32、Windows和Linux64上打印，表示小端机器，最后在Sun上打印，表示大端机器。类似地，除了字节顺序之外，浮点数据的字节是相同的。另一方面，指针值完全不同。不同的机器/操作系统配置使用不同的存储分配约定。需要注意的一个特性是，Linux 32、Windows和Sun机器使用4字节地址，而Linux 64机器使用8字节地址。

注意，尽管浮点和整数数据都对数值12345进行编码，但它们的字节模式非常不同：0x00003039表示整数，0x4640E400表示浮点。通常，这两种格式使用不同的编码方案。如果我们将这些十六进制模式展开为二进制形式并适当地移动它们，我们会发现一个由13个匹配位组成的序列，由星号序列表示，如下所示：

我们会在后面介绍这一特点。

练习

---

假设我们通过如下的方式调用show_bytes：

int val=0x87654321;
byte_pointer val=(byte_pointer)&val;
show_bytes(valp,1);	/A/
show_bytes(valp,2);	/B/
show_bytes(valp,3);	/C/

写出大端编址和小端
指示littleendian计算机和big endian计算机上的每次调用将打印以下哪些值：

答案：

小端编址：

• 78
• 78 56
• 78 56 34

大端编址：

• 12
• 12 34
• 12 34 56

1.5 字符串的表示

C中的字符串由以null（值为0）字符结尾的字符数组的形式进行编码。每个字符都由某种标准编码格式表示，最常见的是ASCII字符码。因此，如果我们用参数“12345”和6（包括终止字符）运行例程show_bytes，我们得到的结果是31 32 33 34 35 00。注意十进制数字x的ASCII代码恰好是0x3x，并且终止字节具有十六进制表示0x00。我们在任何使用ASCII作为其字符码的系统上都会得到相同的结果，这与字节顺序和字长约定无关。因此，文本数据比二进制数据更独立于平台。

1.6 代码的表示

考虑如下的C函数：

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

当在如下的机器上运行时，我们可以分别得到如下的代码的机器码：

Linux 		32: 55 89 e5 8b 45 0c 03 45 08 c9 c3
Windows: 	55 89 e5 8b 45 0c 03 45 08 5d c3
Sun: 		81 c3 e0 08 90 02 00 09
Linux 64: 	55 48 89 e5 89 7d fc 89 75 f8 03 45 fc c9 c3

这里我们可以发现指令编码是不同的。不同的机器类型使用不同且不兼容的指令和编码。即使是运行不同操作系统的相同处理器，其编码约定也存在差异，不具有二进制兼容性。二进制代码很少能跨机器和操作系统的不同组合进行移植。

计算机系统的一个基本概念是，从机器的角度来看，程序只是一个字节序列。机器没有关于原始源程序的信息，除了维护一些辅助表以帮助调试之外。

1.7 布尔运算

下面展示了几个基本的布尔运算：

这些单位的运算也可以拓展开，进行位向量的布尔运算：

对于位向量的一个用途是代表有限集，我们可以用一个位向量

[

a

w

−

1

,

.

.

.

,

a

1

,

a

0

]

[a_{w-1},...,a_1,a_0]

[aw−1​,...,a1​,a0​]编码一个子集

A

⊆

{

0

,

1

,

.

.

.

,

w

−

1

}

A\sube\{0,1,...,w-1\}

A⊆{0,1,...,w−1}。例如，位向量

a

=

[

01101001

]

a=[01101001]

a=[01101001]可以编码为集合

A

=

{

0

,

3

,

5

,

6

}

A=\{0,3,5,6\}

A={0,3,5,6}，位向量

b

=

[

01010101

]

b=[01010101]

b=[01010101]可以编码为集合

B

=

{

0

,

2

,

4

,

6

}

B=\{0,2,4,6\}

B={0,2,4,6}。在这种编码方式下，布尔运算|和&分别对应集合的交集和并集，~对应集合的补集。这样在我们上面的例子中，

a

&

b

a\&b

a&b就会生成

[

01000001

]

[01000001]

[01000001]位向量，代表

A

∩

B

=

{

0

,

6

}

A\cap B=\{0,6\}

A∩B={0,6}

1.8 C语言中的位运算

C语言的一个有用的特性就是它支持位运算，而且刚才我们介绍的位运算符就是C语言所使用的。如下就是对char型数据进行的位运算：

练习：

---

如下的程序可以交换两个变量的值：

假设初始值如下，写出程序执行的每一步后x和y所指向的值：

答案：

步骤	*x	*y
1	a	a^b
2	b	a^b
3	b	a

---

答案：

• x&0xFF
• x^~0xFF
• x|0xFF

1.9 C语言中的逻辑运算

C语言还提供了一组逻辑运算符||，&&和！，对应着逻辑运算中的或、与和非。在逻辑运算中，任何非0值都被当作真值，而所有的0值都被判定为假。逻辑运算的结果会返回1或者0，代表真或假。下面是几个逻辑运算的例子：

逻辑运算的另一个重要特征是，如果第一个操作数就可以决定运算结果，那么机器执行逻辑运算时不会计算后面的指令。例如a&&5/a，如果a为0，那么运算结果会直接返回0，不会出现计算5/0的情况。

1.10 C语言中的移位运算

C语言提供了一些移位运算符。对于一个拥有位表示

[

x

n

−

1

,

x

n

−

2

,

.

.

.

,

x

0

]

[x_{n-1},x_{n-2},...,x_0]

[xn−1​,xn−2​,...,x0​]的整数x，C运算x<<k会产生一个位运算表示为

[

x

n

−

k

−

1

,

x

n

−

k

−

2

,

.

.

.

,

x

0

,

.

.

.

.

,

0

]

[x_{n-k-1},x_{n-k-2},...,x_0,....,0]

[xn−k−1​,xn−k−2​,...,x0​,....,0]的结果。这时x左移了k位，右方以0进行填充。

右移操作相对于左移有一些区别，因为机器支持两种类型的右移：逻辑右移和算术右移。逻辑右移在空缺位上补0，得到的结果是

[

0

,

.

.

.

,

0

,

x

n

−

1

,

x

n

−

2

,

.

.

.

,

x

k

]

[0,...,0,x_{n-1},x_{n-2},...,x_k]

[0,...,0,xn−1​,xn−2​,...,xk​]。算术右移在空缺位填补最高有效位置，得到的结果是

[

x

n

−

1

,

.

.

.

,

x

n

−

1

,

x

n

−

2

,

.

.

.

,

x

k

]

[x_{n-1},...,x_{n-1},x_{n-2},...,x_k]

[xn−1​,...,xn−1​,xn−2​,...,xk​]。

下面的例子展示了对同样的八位数据进行各种移位运算后得到的结果：

C标准没有精确定义应该使用哪种类型的右移。对于无符号数据（即用无符号限定符声明的整数对象），右移位必须是逻辑的。对于有符号数据（默认值），可以使用算术移位或逻辑移位,这可能会遇到可移植性问题。然而，在实践中，几乎所有的编译器/机器组合都对有符号数据使用算术右移，并且许多程序员都认为是这样。

Java语言精确定义了我们要使用哪种右移方式，x>>k代表执行算术右移，x>>>k代表执行逻辑右移。