第二章 信息的表示和处理

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

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

        我们研究三种最重要的数字表示。无符号（unsigned）编码基于传统的二进制表示法，表示大于或者等于零的数字。补码（two`s-complement）编码是表示有符号整数的最常见的方式，有符号整数就是可以为正或者为负的数字。浮点数（floating-point）编码是表示实数的科学计数法的以2为基数的版本。计算机用这些不同的表示方法实现算术运算，例如加法和乘法，类似于对应的整数和实数运算。

        计算机的表示法是用有限数量的位来对一个数字编码，因此，当结果太大以至不能表示时，某些运算就会溢出（overflow）。溢出会导致某些令人吃惊的后果。例如，在今天的大多数计算机上（使用32位来表示数据类型int），计算表达式200*300*400*500会得出结果-884901888.这违背了整数运算的特性，计算一组正数的乘积不应产生一个负的结果。

        另一方面，整数的计算机运算满足人们所熟知的真正整数运算的许多性质。例如，利用乘法的结合律和交换律，计算下面任何一个C表达式，都会得出结果-884901888：

        （500*400）*（300*200）

        （（500*400）*300）*200

        （（200*500）*300）*400

        400*（200*（300*500））

        计算机可能没有产生期望的结果，但是至少它是一致的！

        浮点数运算有完全不同的数学属性。虽然溢出会产生特殊的值+∞，但是一组正数的乘积总是正的。由于表示的精度有限，浮点运算是不可结合的。例如，在大多数机器上，C表达式（3.14+1e20）-1e20求得的值会是0.0，而3.14+（1e20-1e20）求得的值会是3.14。整数运算和浮点数运算会有不同的数学属性是因为它们处理数字表示有限性的方式不同——整数的表示虽然只能编码一个相对较小的数值范围，但是这种表示是精确地；而浮点数虽然可以编码一个较大的数值范围，但是这种表示只是近似的。

        通过研究数字的实际表示，我们能够了解可以表示的值的范围和不同算术运算的属性。为了使编写的程序能在全部数值范围内正确工作，而且具有可以跨越不同机器、操作系统和编译器组合的可移植性，了解这种属性是非常重要的。后面我们会讲到大量计算机安全漏洞都是由于计算机算术运算的微妙细节引发的。在早期，当人们碰巧触发了程序漏洞，只会给人们带来一些不便，但是现在，由众多黑客企图利用他们能找到的任何漏洞，不经过授权就进入他人的系统。这就要求程序员有更多的责任和义务，去了解他们的程序如何工作，以及如何被迫产生不良的行为。

        计算机用几种不同的二进制表示形式来编码数值。随着第三章进入机器级编程，你需要熟悉这些表示方式。在本章中，我们描述这些编码，并且教你如何退出数字的表示。

        通过直接操作数字的位级表示，我们得到了几种进行算术运算的方式。理解这些技术对于理解编译器产生的机器级代码是很重要的，编译器会试图优化算术表达式求值的性能。

        我们对这部分内容的处理事基于一组核心的数学原理的。从编码的基本定义开始，然后得出一些属性，例如可表示的数字的范围、它们的位级表示以及算术运算的属性。我们相信从这些一个抽象的观点来分析这些内容，对你来说是很重要的，因为程序员需要对计算机运算与更为人熟悉的整数和实数运算之间的关系有清晰的理解。

旁注：怎样阅读本章

        本章我们研究在计算机上如何表示数字和其他形式数据的基本属性，以及计算机对这些数据执行操作的属性。这就要求我们深入研究数学语言，编写公式和方程式，以及展示重要属性的推导。

        为了帮助你阅读，这部分内容安排如下：首先给出以数学形式表示的属性，作为原理。然后，用例子和非形式化的讨论来解释这个原理。我们建议你反复阅读原理描述和它的示例与讨论，直到你对该属性的说明内容及其重要性有了牢固的直觉。对于更加复杂的属性，还会提供推导，其结构看上去将会像一个数学证明。虽然最终你应该尝试理解这些推导，但在第一次阅读时你可以跳过它们。

        我们也鼓励你在阅读正文的过程中完成练习题，这会促使你主动学习，帮助你理论联系实际。有了这些例题和练习题作为背景知识，再返回推导，你将发现理解起来会容易许多。同时，请放心，掌握好高中代数知识的人都具备理解这些内容所需要的数学技能。

        C++编程建立在C语言基础之上，它们使用完全相同的数字表示和运算。本章中关于C的所有内容对于C++都有效。另一方面，Java语言创造了一套新的数字表示和运算标准。C标准的设计允许多种实现方式，而Java标准在数据的格式和编码上是非常精确具体的。本章中多处着重介绍了Java支持的表示和运算。

旁注：C编程语言的演变

        前面提到过，C编程语言是贝尔实验室的Dennis Ritchie最早开发出来的，目的是和Unix操作系统一起使用（Unix也是贝尔实验室开发的）。在那个时候，大多数系统程序，例如操作系统，为了访问不同数据类型的低级表示，都必须大量使用汇编代码。比如说，像malloc库函数提供的内存分配功能，用当时的其他高级语言是无法编写的。

        Brian Kernighan 和Dennis Ritchie的著作的第1版记录了最初贝尔实验室的C语言版本。随着时间推移，经过多个标准化组织的努力，C语言也在不断地演变。1989年，美国国家标准学会下的一个工作组推出了ANSI C标准，对最初的贝尔实验室的C语言做了重大修改。ANSI C与贝尔实验室的C有了很大的不同，尤其是函数声明的方式。Brian Kernighan和Dennis Ritchie在著作的第2版中描述了ANSI C，这本书至今被公认为关于C语言最好的参考手册之一。

        国际标准化组织接替了对C语言进行标准化的任务，在1990年推出了一个几乎和ANCI C一样的版本，称为“ISO C90”。该组织在1999年又对C语言做了更新，推出了“ISO C99”。在这一版中，引入了一些新的数据类型，对使用不符合英语语言字符的文本字符串提供了支持。更新的版本2011年得到批准，称为“ISO C11”，其中再次添加了更多的数据类型和特性。最近增加的大多数内容都可以向后兼容，这意味着根据早起标准（至少可以回溯到ISO C90）编写的程序按新标准编译时会有同样的行为。

        GNU编译器套装（GNU Compiler Collection，GCC）可以基于不同的命令行选项，依照多个不同版本的C语言规则来编译程序，如图2-1所示。

比如，根据ISO C11来编译程序prog.c，我们就使用命令行：

linux> gcc -std=c11 prog.c

编译选项-ansi和-std=c89的用法是一样的——会根据ANSI或者ISO C90标准来编译程序。（C90有时也称为“C89”，这是因为它的标准化工作时从1989年开始的。）编译选项-std=c99会让编译器按照ISO C99的规则进行编译。

        本书中，没有指定任何编译选项时，程序会按照基于ISO C90的C语言版本进行编译，但是也包括一些C99、C11的特性，一些C++的特性，还有一些与GCC相关的特性。GNU项目正在开发一个结合了ISO C11和其他一些特性的版本，可以通过命令行选项-std=gnu11来指定。今后，这个版本会成为默认的版本。