Skip to content

Representing and Manipulating Information

现代计算机中使用二进制来表示信息，即一个比特（bit），一个比特可以是 0 或者 1。二进制很容易被表示、存储和传输，比如打孔卡上有孔或无孔，导线上的高电平或低电平等。

单个的比特并没有意义，需要将比特组合成一个可以解释（interpretation）的模式。最重要的三种表示是：无符号（unsigned）编码，用于表示非负整数；补码（two's complement）用于表示整数（可以是负数）；浮点数（floating point）用于表示实数。计算机对这些表示都实现了一些算数运算，比如加法、乘法等。

使用有限的比特表示一个整数，可能会发生溢出（overflow），比如四个 32-bit 整数 300、400、500、600 的乘积是 -884,901,888。这与整数运算的性质相悖，多个正数的乘积是一个负数。整数运算也满足常见的代数性质，比如交换律、结合律。

浮点数的运算有不同性质。正数的乘积还是正数，但是可能是无穷大（infinity，）。由于表示精度的有限，可能不满足结合律，比如 (3.14+1e20)-1e20 的结果是 0.0，而 3.14+(1e20-1e20) 的结果是 3.14。

整数和浮点数运算的不同数学性质源于它们的表示方式。整数表示是精确的，但是范围有限，浮点数表示的范围大的多，但是只能近似表示。理解底层的表示，可以帮助我们理解这些运算的性质，写出正确的、可移植的代码。

信息的存储

大多数计算机并不是访问内存中的单个比特，而是将 8 比特构成的块，即一个字节（byte）作为最小的可寻址单元。机器代码将内存视为一个非常大的字节数组，称为虚拟内存（virtual memory）。计算机使用各种机制为程序的各个部分分配和管理存储空间，这种管理是在虚拟内存空间进行的。比如 C 语言中的指针指向的是某块存储空间的第一个字节的虚拟地址。C 编译期将数据类型（type）与指针关联起来，根据类型生成不同的机器代码来访问指针指向的位置。不过实际的机器代码对数据类型一无所知，程序中的各个对象只是一个字节块罢了，程序自身也是一系列字节。

十六进制表示

一个字节由 8 个比特组成，可以表示 个不同的值。二进制表示的范围从 到 ，十进制表示的范围从 到 。前者表示冗余，后者和比特模式的转化非常的复杂。因此引入了十六进制（hexadecimal）表示，一个十六进制数字可以表示 4 个比特，0 到 9 还是表示 0 到 9，A 到 F 表示 10 到 15。对于字母而言，不区分大小写。C 语言中，十六进制数以 0x 开头，比如 0xFF 表示 255。

三种进制的表示如下：

二进制 十六进制 十进制
0000 0 0
0001 1 1
0010 2 2
0011 3 3
0100 4 4
0101 5 5
0110 6 6
0111 7 7
1000 8 8
1001 9 9
1010 A 10
1011 B 11
1100 C 12
1101 D 13
1110 E 14
1111 F 15

十六进制转为二进制很简单，每个十六进制数字对应 4 个比特。反之也非常简单，每四个比特一组，转为一个十六进制数字，如果不是 4 的整数倍，最左边（leftmost）补零。

如果 是 2 的次幂，比如 ，二进制表示是一个 1 后面跟着 n 个 0，如果 ，其中 是 0 到 3 之间的整数， 是一个非负整数，那么十六进制表示就是一个十六进制数字（由 决定， 是 1， 是 2， 是 4， 是 8）后面跟着 个 0。比如 ，因为 。

如果是一般的整数，十进制和十六进制互相转换相对麻烦一点。把十进制 转化成十六进制，除以 16，得到商 和余数 ，余数 就是十六进制表示的最后一个数字，商 再继续重复这个过程。比如下面的例子 

314,156 = 19,634 * 16 + 12 // C
19,634 = 1,227 * 16 + 2 // 2
1,227 = 76 * 16 + 11 // B
76 = 4 * 16 + 12 // C
4 = 0 * 16 + 4 // 4
因此 314,156=0x4BC2C。

十进制转十六进制的过程就是把上述除以 16 的过程反过来。比如 0x7AF 的计算过程是 。

数据大小

每个计算机有一个字长（word size），是指针类型的大小，通常是 32 位或者 64 位，现在绝大部分计算机的字长是 64 位。虚拟地址使用一个字表示，那么虚拟地址空间的大小由字长确定。一个机器的字长是 位，那么地址从 0 到 ，虚拟地址空间的大小是 字节。对于 32 位计算机，地址空间是 4GB；对于 64 位计算机，地址空间是 16EB（ 字节）。

大部分 64 位计算机可以运行为 32 位计算机编译的程序，比如 gcc -m32 program.c，结果是 32 位程序，可以运行在 32 位和 64 位计算机上，gcc -m64 program.c 结果是 64 位程序，只能运行在 64 位计算机上。这里多少位程序指的是编译的程序，不是运行的机器的类型。

计算机和编译期都支持不同长度、不同编码的数，下面是一个典型的 C 语言数据类型及其大小：

数据类型 Signed 数据类型 Unsigned 大小（字节）32 位 大小（字节）64 位
[signed] char unsigned char 1 1
short unsigned short 2 2
int unsigned int 4 4
long unsigned long 4 8
int32_t uint32_t 4 4
int64_t uint64_t 8 8
char* 4 8
float 4 4
double 8 8

这里所谓的典型大小依赖于编译器和计算机，ISO C99 引入了 新的类型，比如 int32_t 和 int64_t，保证了在所有平台上都是 4 字节和 8 字节。

编写可移植程序一个重要方面就是数据类型的大小。C 标准值规定了数据类型长度的下界，没有规定上界。在早期 32 位程序占主流的时候，默认大小和现在移植到 64 位计算机上默认大小不一样，可能会导致一些问题。比如早期使用 int 来存储指针，编译成 64 位程序后，int 还是 4 字节，而指针是 8 字节了，导致出现问题。

寻址和字节序

对于一个跨多个字节的对象，需要约定两件事：对象的地址是什么，在内存中的字节序是什么。对象的地址是指对象在内存中的第一个字节的地址。比如 int x 的地址是 0x100，那么这个 int 占用的字节是 0x100、0x101、0x102 和 0x103。字节序（byte order）是指对象的字节在内存中的排列顺序。大端（big-endian）表示最高有效字节（most significant byte）在最低地址，最低有效字节（least significant byte）在最高地址；小端（little-endian）表示最低有效字节在最低地址，最高有效字节在最高地址。比如 int x=0x12345678，大小端的内存表示如下： 

                0x100   0x101   0x102   0x103
big-endian:     0x12    0x34    0x56    0x78
little-endian:  0x78    0x56    0x34    0x12
大部分的 Intel 机器都是小端，大部分 IBM/Oracle 机器都是大端。这里使用大部分，含义是不绝对，比如 IBM 也生产 Intel 兼容机器，也是小端。近来一些机器是双端（bi-endian），支持两种字节序，一旦选择了操作系统，字节序就固定了。比如 ARM 处理器就是双端机器，广泛应用于智能手机，不过之上的系统 Android 和 iOS 都是小端的。

大部分应用程序的程序员不需要关心字节序，因为编译器和操作系统会处理好这些细节。但是字节序确实引入了一些问题。

第一个问题是当两台机器通过网络传递数据。小端机器发送数据到大端机器，或者反之，程序就需要翻转字节序。为了解决这个问题，两个程序通过网络传递数据，需要约定好字节序。

第二个问题是如何解释整数。比如下面的例子是来自反汇编器（disassembler）的输出，这是一个指令，这里无需关注指令本身，而是需要关注字节序。 

4004d3: 01 05 43 0b 20 00    add    %eax, 0x200b43(%rip)
下一个指令的地址是将 0x200b43 与当前 PC 值相加。指令中四个字节 0x43、0x0b、0x20 和 0x00 是一个 32 位的整数，表示的值就是字节翻转的结果，由于第一个字节是 0，去掉，所以结果是 0x200b43。

第三个问题是当写代码绕过类型系统的时候会出现的问题。C 语言中，类型转换（cast）或者 union 可以实现这一点，以不同的类型来访问同一块内存。对于应用程序员而言，不推荐这么做，但是对于系统编程而言，这就非常有用了。

下面是一段打印二进制的例子。 

void show_bytes(unsigned char *start, int len)
{
    int i;
    for (i = 0; i < len; i++)
    {
        printf("%.2x ", start[i]);
    }

    printf("\n");
}

int main()
{
    int x = 12345;
    show_bytes((unsigned char *)&x, sizeof(int));

    float f = 12345;
    show_bytes((unsigned char *)&f, sizeof(float));

    return 0;
}
输出如下： 
39 30 00 00
00 e4 40 46
整数的 12,345 的十六进制表示是 0x3039，浮点数的 12,345 的十六进制表示是 0x4640e400，可以看到整数和浮点数的表示完全不同。不过展开成二进制之后，有 13 比特是相同的，这不是偶然的，稍后分析两者的表示方式会回到这个例子。 
   0   0   0   0   3   0   3   9
00000000000000000011000000111001
                   *************
          01000110010000001110010000000000
             4   6   4   0   e   4   0   0

字符串表示

C 语言中字符串是一个以空字符（null character，'\0'）结尾的字符数组，每一个字符使用某种标准编码，最常见的是 ASCII 编码。下面的代码输出了字符串中的字节。 

char *s = "12345";
show_bytes((unsigned char *)s, 6);
输出如下： 
31 32 33 34 35 00
字符 '1' 的 ASCII 编码是 0x31，后续字符是连续的。

代码表示

不同的机器使用不同的指令和编码，运行不同操作系统的机器，编码规范可能也不同。二进制代码在不同的机器和操作系统之间很少能够直接移植。

从机器的角度看看，一个程序也不过是一连串的字节罢了。除了调试信息之外，机器对于原本的源代码一无所知。后续我们会详细讨论机器代码的表示和执行。