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

我们生活在比特组成的世界

视频解说

导读

你可能会有疑惑：为什么作者要花那么多那么大的篇幅（中文版22-108页）来介绍大家（仿佛）都已经理解的二进制系统呢？实际上我认为第二章写的非常好，当你阅读了本书的第二章之后，也许会发现，你所谓的（懂）只是你的一厢情愿而已，数值系统远没有你想象的那么简单，比如当初美国宾夕法尼亚大学的ENIAC计算机使用的是十进制编码，后来为什么二进制补码被广泛采用（这实际上不符合人类的 “直觉”）？

为什么现在大部分系统的一个字节是8个比特？你是不是觉得这是理所当然的？加州伯克利分校的CS61C的课堂上就有“傻”学生问了这个问题，Krste教授回答了这个问题（出现在第3节课的01:02:42）：最终决定一个字节大小是8个比特的，是1964年出现的大名鼎鼎的 IBM System/360，当时IBM为System/360设计了一套8位EBCDIC编码，涵盖了数字、大小写字母和大部分常用符号，同时又兼容广泛用于打孔卡的6位BCDIC编码，System/360很成功，也奠定了字符存储单位采用8位长度的基础，这就是1字节=8位的由来。

历史上很多由于软件缺陷而引发的灾难都与开发者没有充分重视或者测试数值系统有关，比如NASA的火星探测器失联，阿丽亚娜5号火箭爆炸等，如果你开发的是关键系统，那么可能由于你缺乏相关知识而造成重大损失甚至人员伤亡！

这里给大家举一个1996年阿丽亚娜5号火箭爆炸的例子，欧洲航天局为此付出了数亿美元的损失，阿丽亚娜5号在飞行程序开始后仅约40秒，在约3700m的高度，发射器偏离其飞行路线，破裂爆炸，事故相关报告的链接在这里，追溯到的主要原因是软件缺陷，点火开始后37秒钟完全失去了引导和姿态信息，原因是控制惯性导航系统的计算机向箭载计算机发送了一个无效数据，表明将一个64位浮点数转换成16位有符号整数时，产生了溢出（溢出值测量的是火箭的水平速率），这比早先的阿丽亚娜4号火箭所能达到的速度高出了5倍，设计Ariane 4火箭软件的时候，确定水平速率决不会超出一个16位数的表示范围。不幸的是，他们在阿丽亚娜5号火箭的系统中简单地重用了这一部分，而没有检查它所基于的假设，最终导致悲剧发生。

再举一个真实的例子，纽约时报曾经报道，波音 787 的电力控制系统在 248 天电力不中断的状况下会自动关机（这可能发生在飞行途中），为此 FAA (美国联邦航空管理局) 告知航空公司，他们必须每隔 120 天进行一次维护重启，这显然是治标不治本的办法，我们来探究一下其中的真正原因：

美国卡内基梅隆大学 (CMU) 的 Phil Koopman 教授指出，这其实是 integer overflow 问题，也就是所谓的整型溢出问题，原文链接在这里，我们简单小结一下，报告指出的248天为：248 days * 24 hours/day * 60 minute/hour * 60 seconds/minute = 21427200秒，等效于2142720000（以1/100秒来计算），十六进制表示就是：0x7Fb75000 ，而最大的32位正整型是0x7FFFFFFF，248天看起来非常接近该限制，实际上，0x7FFFFFFF = 2147483647 /（24 * 60 * 60）= 24855/100 = 248.55天，因此，实际上崩溃会在248.55天之后发生，也就是说，使用了32位的有符号整型来记录时间（记录的单位是10ms），然后遇到溢出。

距离我们最近的则是波音737-MAX事件，波音737-MAX导致狮航和埃航两次空难共346人丧生，调查认为两次失事原因均与737-MAX的 “机动特性增强系统” 迫使机头向下导致飞机失速有关，该机型被全球禁飞，由于波音737-MAX停飞事件造成大批订单被取消以及737-MAX系列的减产，波音的主要竞争对手空中客车公司在2019年超过波音成为当年全球最大飞机制造商。

数值系统

历史故事

香农于1938年在MIT发表了硕士论文 “A Symbolic Analysis of Relay and Switching Circuits”《继电器与开关电路的符号分析》，它被誉为“可能是本世纪最重要、最著名的硕士学位论文”，在这篇论文中，香农证明了布尔代数和二进制算术可以简化当时在电话交换系统中广泛应用的机电继电器的设计，然后，香农扩展了这个概念，证明了基于机电继电器的电路能用于模拟和解决布尔代数问题，用电子开关模拟布尔逻辑运算是现代电子计算机的基本思路，香农的工作成为数字电路设计的理论基石。 1948年，香农再次发表了划时代的论文《通信的数学原理》，证明了信息是可以被量化的，并阐述了如何在保证准确率的前提下用数字编码对信息进行压缩和传输，奠定了现代信息论的基础。

除了学术研究，香农还爱好杂耍、骑独轮脚踏车和下棋，学过开飞机和爵士单簧管，精彩的斜杠人生！

原码

我们知道，数值具有正负两种符号，但是计算机仅由0和1两种状态构建而成，因此并没有专门用来表示正负号的原生方式，我们凭直觉设计就是挪用其中的一位来表示正负号，简单起见，如果我们用3位表达一个数值，这样的编码系统实际上能够表达的范围将会是:

-(2^2 - 1) = -3, -2, -1, -0, +0, +1, +2, +(2^2 - 1) = +3

上述以符号与值编码的方式，称为 [ 原码 ]， IBM 7090 这类早期的二进制计算机就是使用这种编码方式。

因此这种编码方式早期确实已经被实际应用在太空探索领域，但是它有一些显然的缺点，比如：首先，0的表示不唯一，出现了-0和+0，其次（也是更重要的原因）它需要单独的硬件电路来确定正负号。

反码

聪明的人们想出了另外一种编码方式：即一个负数的二进制形式改为其绝对值部分按位逐位反转，称为 [ 一补码 ] (ones’ complement)，举例来说，如果我们用3位表达一个数值，十进制数值 -2 用反码表示是 101 (就是 +2 的逐位反转)，对应到数字逻辑电路就是按位反转，说白了就是一个反相器，因此，一补码也被称为 [ 反码 ]。

反码还涉及 [ 循环进位] 的问题，比如我们来看看10进制的 (−1) 加上10进制的 (+2) 使用反码怎么运算。

           二进制    十进制
        11111110     -1
     +  00000010     +2
    ............    ...
      1 00000000      0   <-- 错误结果
               1     +1   <-- 加上进位
    ............    ...
        00000001      1   <-- 正确结果

反码的一个显著优点就是正数和负数的加法都一样运算，所以不需要单独判断符号的电路，但是，0的表示还是不唯一，出现了-0和+0

补码

无论是 [ 原码 ] 还是 [ 反码 ] 都有各自的缺点，于是补码闪耀登场，现代硬件广泛使用补码。思考：它究竟有哪些优点？

浮点数

在六、七十年代，各家计算机公司的各个型号的计算机，有着千差万别的浮点数表示，却没有一个业界通用的标准。这给数据交换、计算机协同工作造成了极大不便。IEEE的浮点数专业小组于七十年代末期开始酝酿浮点数的标准。在1980年，英特尔公司推出了8087浮点数协处理器，其浮点数表示法及定义的运算具有足够的合理性、先进性，被IEEE采用作为浮点数的标准IEEE-754，于1985年发布。而在此前，这一标准的内容已在八十年代初期被各计算机公司广泛采用，成了事实上的业界工业标准。加州大学伯克利分校的数值计算与计算机科学教授William Kahan被誉为“浮点数之父”，并因此获得1989年的图灵奖。

915KB

ieee-754-2008.pdf

pdf

学习方式

CMU教授的视频教程 - Lecture2：Bits，Bytes and Intergers

CMU教授的视频教程 - Lecture3：Bits，Bytes and Intergers (Cont.)

重点提示：无符号 vs 有符号，整型溢出问题，比特操作 ( &， |， ~， ^ ) vs 逻辑操作 (&&， ||， !)

相关练习：视频中出现了以下C语言问题（仔细来看看），书中也有类似的题目 ( p75：练习题2.44)

Brian Kernighan（K&R中的K，也是AWK的作者之一）在谈论编程风格的时候举了一个比特操作的例子：

字节序 (大小端 )：什么时候你需要关心大小端？例如网络数据的发送/接收格式，阅读反汇编的时候等

// Demo_2:观察字节序的一个简单例子
typedef unsigned char *pointer;

void show_bytes(pointer start, size_t len){
    size_t i;
    for (i = 0; i < len; i++)
    printf("%p\t0x%.2x\n",start+i, start[i]);
    printf("\n");
}

int main(){
    int a = 0x01234567;
    show_bytes((pointer) &a, sizeof(int));
}

// 输出结果(Linux x86-64)
Demo$ gcc -o chp2 chp2.c ; ./chp2
0x7ffc837a0b3c	0x67
0x7ffc837a0b3d	0x45
0x7ffc837a0b3e	0x23
0x7ffc837a0b3f	0x01

CMU教授的视频教程 - Lecture4：Floating Point，计算机结构的伟大思想 - P17：浮点数运算 (40:00开始~)

台湾元智大学计算机组成原理：浮点数-1，台湾元智大学计算机组成原理：浮点数-2 （中文讲解很清楚）

PS. 一个很有意思的介绍浮点数的网站：https://0.30000000000000004.com

重点提示：本质就是我们如何使用二进制来表达一个很大或者很小的数 (类似科学计数法，但是编码上有显著的区别)，由于二进制的数值系统在表达能力上存在一定的限制 (位数的限制)，我们实际上没有办法表示所有的数，因此浮点数的设计需要认真的权衡和折中，既要考虑能够表达的范围，也要考虑表达的精度，最好还能够(从硬件设计角度来说)简单直接地比较两个浮点数的大小，因此浮点数的设计可能比你想象的要复杂的多，假如今天由你来设计一个新的浮点数标准，你会怎么设计？你可能会觉得这没有意义，如果你这么想，那就错了，请看看谷歌为什么要花费力气来设计自己的BFloat16，详情请参考：Google BFloat16

IEEE-754浮点数表示法，如果用一张可视化视图来表示的话，就像下面这样，设计的还是比较优雅的：

+0 和 -0？+∞ 和 -∞？1.0/0.0 = −1.0/−0.0 = +∞, 1.0/−0.0 = −∞，NaN (Not a Number) => 不是一个数，那是什么鬼 ? 请你考虑 ∞ - ∞，∞ × 0，它们的计算结果会是什么？

// Demo_3
#include <assert.h>

int main(){
    assert(+0. == -0.);      // 断言成功
    assert(1.0/+0. == 1.0/-0.); // 断言失败
    return 0;
}

编码方式：如下图所示（此处仅以32位浮点数为例）：

特别注意：浮点数加法和乘法不满足结合律，也不满足乘法对加法的分配律，以下举例说明：

(3.14+1e10)-1e10 = 0, 3.14+(1e10-1e10) = 3.14，(1e20 *1e20) * 1e-20= inf, 1e20 * (1e20 * 1e-20)= 1e20

1e20 * (1e20 - 1e20)= 0.0, 1e20 * 1e20 - 1e20 * 1e20 = NaN

这些特殊的数学性质对于科学计算程序员和编译器的优化限制都具有重要意义，举例如下：

x = a + b + c;
y = b + c + d;

// 编译器可能试图通过产生下列代码来省去一个浮点加法
t = b + c;
x = a + t;
y = t + d;
// 但是对x来说，这个计算可能会产生于原始值不同的值,因为它使用了加法运算的不同结合方式

重点示例

例1: 带符号数产生意外结果的例子。这个例子会造成无限循环，因为sizeof会返回unsigned int 类型，由此带来的结果是，i - sizeof(char)这个表达式的求值结果将会是 unsigned int (隐式转换 !!)，无符号数 0 减 1 会变成 0xFFFFFFFF，从而产生无限循环，有时候你需要特别留心这种不经意的错误 !

// Demo_4
int n = 10, i; 
for (i = n - 1 ; i - sizeof(char) >= 0; i--)
    printf("i: 0x%x\n",i);

if (-1 > 0U)                     // 神奇的算术!! 
    printf("You Surprised me!\n");

例2: 以下是2002年的freeBSD内核的部分代码，其中包含了漏洞，假设恶意人员将负值作为maxlen传入这个函数，有发生什么情况？

#define KSIZE 1024
char kbuf[KSIZE];
/* Copy at most maxlen bytes from kernel region to user buffer */
int copy_from_kernel(void *user_dest, int maxlen) {
    int len = KSIZE < maxlen ? KSIZE : maxlen;
    memcpy(user_dest, kbuf, len);
    return len;
}

/* Declaration of library function memcpy */
void *memcpy(void *dest, void *src, size_t n);

/* Malicious Usage */
void getstuff() {
    char mybuf[MSIZE];
    copy_from_kernel(mybuf, -512);
}

类似的，请参照书本 p69：XOR库中的乘法溢出漏洞，思考对应的解决方案 (p70：练习题2.37)

例3 (拓展): 给定一个有序的整型数组，请编程实现二分查找算法。

高德纳在《计算机程序设计的艺术》指出，虽然早在1946年就有人将二分查找的方法公诸于世，但直到1962年才有人写出没有bug的二分查找程序，可见，写一个安全的代码并不容易，你是不是一不小心就写出像下面这样的二分查找代码了？

int binary_search(int a[], int len, int key){
    int low = 0; 
    int high = len - 1; 

    while ( low <= high ) {
        int mid = (low + high)/2;   // 提示：这里有溢出Bug！
        if (a[mid] == key) {
            return mid;
        }
        if (key < a[mid]) {
            high = mid - 1;
        }else{
            low = mid + 1;
        }
    }
    return -1;
}

例4 (拓展): 浮点数运算

// 有问题的版本 
#include <stdio.h>
int main() {
    float sum = 0.0f;
    for (int i = 0; i < 10000; i++) sum += i + 1;
      printf("Sum: %f\n", sum);
    return 0;
}
// 1 + 2 + 3 + … + 10000 = 10000 * (10000 + 1) / 2 = 50005000 ?

// 修正的版本
#include <stdio.h>
int main() {
    float sum = 0.0f, corr = 0.0f; /* corrective value for rounding error */
    for (int i = 0; i < 10000; i++) {
      float y = (i + 1) - corr; /* add the correction to specific item */
      float t = sum + y; /* bits might be lost */
      corr = (t - sum) - y; /* recover lost bits */
      sum = t;
    }
    printf("Sum: %f\n", sum);
    return 0;
}

例5 (拓展): 信息的处理（你会如何删除一个单向链表的一个结点，假设节点必定在list之中）

Linus Torvalds 2016年TED采访，14:26开始，拿出两个单向链表操作为例，说明了什么是有品位的程序。

// 初学者版本
void remove_list_node(List *list, Node *target)
{
    Node *prev = NULL;
    Node *cur = list->head;
    // Walk the list
    while (cur != target) {
        prev = cur;
        cur = cur->next;
    }
    // Remove the target by updating the head or the previous node.
    if (!prev)
        list->head = target->next;
    else
        prev->next = target->next;
}

// 有品位的版本，消除特例，简单优雅的代码
void remove_list_node(List *list, Node *target)
{
    // The "indirect" pointer points to the *address*
    // of the thing we'll update.
    Node **indirect = &list->head;
    // Walk the list, looking for the thing that 
    // points to the node we want to remove.
    while (*indirect != target)
        indirect = &(*indirect)->next;
    *indirect = target->next;
}

作业解答

练习题 2.58: 写一个函数返回所使用机器的大小端类型，示例代码如下：

// 示例代码
#include <stdio.h>

int is_little_endian(void){
    union w
    {
      int a;
      char b;
    }c;
    c.a = 1;
    return (c.b == 1); // 小端返回TRUE,大端返回FALSE
}

int main(int argc, char *argv[]) {
    if(is_little_endian())
        printf("Little Endian\n");
    return 0;
}

// 测试环境 Ubuntu 14.04 (x86-64)
rock@rock-virtual-machine:~/CSAPP3e$ ./test 
Little Endian

实验解读（Data Lab ）

实验目的：理解C语言数据类型的位级表示形式，以及数据进行位级操作的行为

实验相关说明以及数值表示的复习课（CMU的助教讲解）：Data Lab实验说明 + 数值表示的复习

当你顺利完成了所有的题目之后期待的结果是这样的：

11KB

bits.c

千万不要小瞧了这个实验，希望你能够站在“比特级”来理解二进制数值系统 (It’s all just bits)！

我们可以举出很多例子（Linux内核中有很多"魔法操作"都是利用位操作完成的），侯捷先生说「源码面前，了无秘密」，真是这样？让我们来看看 Apple的strlen函数实现，或者看看 glibc的strlen函数实现

// 这可能是你的写strlen版本，看起来很精简，但是没有效率！
unsigned int strlen(const char *s) {
    char *p = s;
    while (*p != ’\0’) p++;
    return (p - s);
}

如果你觉得意犹未尽，请参看这个有意思的网页：位运算的奇技淫巧：Bit Twiddling Hacks

延伸阅读

数值系统还有一个重要的议题，就是安全性（信息安全与功能安全），它已经成为了日益突出的问题。

旁路攻击

旁路攻击(side channel attack)是指基于从计算机系统的实现中获得的信息的任何攻击，而不是基于算法本身的弱点，比如定时信息，功耗，电磁泄漏甚至声音都可以提供额外的信息来源，被 “黑客” 加以利用，说白了就是以「旁敲侧击」的方式进行攻击。

近些年的熔断Meltdown漏洞，幽灵Spectre漏洞（两者都是利用现代CPU设计的“漏洞”，例如乱序执行，预测执行，CPU缓存等特性），以及 Row Hammer （利用DRAM的物理漏洞）等都是利用旁路攻击的例子。

这里举一个Timing Attack的例子，为了简化说明，我们考虑以下C函数，这个函数用于比较用户的输入字符串和存放在系统某处的密码是否一致，输入的字符串与密码完全一致才能获得系统权限，否则系统就报错，然后允许用户（过一段时间后）重新输入，这里有什么风险？假如我们有办法精确记录这个函数执行所耗费的时间，那不就可以大概知道在哪个字符出现了不匹配吗？这样的话密码破解的难度将大幅降低。

int memcmp(const void *s1, const void *s2, size_t n) {
    if (n != 0) {
        const unsigned char *p1 = s1, *p2 = s2;
        do {
            if (*p1++ != *p2++)
                return ((*--p1) - (*--p2));
        } while (--n != 0);
    }
    return (0);
}

实际上涉及密码学和处理敏感信息的程序应该引入常数时间的实现，如果我们想要实现一个对整数取绝对值的函数abs，以下的C示例代码，请注意它本身并不保证是常数时间的，但是如果你去看它在x86-64平台上优化之后的汇编代码，可以看出它是没有分支的，按常数时间实现的，比较安全高效。

// 求一个数的绝对值: 1.有分支情况下CPU执行的指令数量不同 2.注意传入整型最小负值的情况
int abs(int num) {
    return num < 0 ? -num : num;
}

// x86-64 某一个优化版本：注意这里没有分支，3条汇编指令
abs:
    mov    eax,edi  // 参数保存到eax
    neg    eax      // 求出它的相反数
    cmovs  eax,edi  // 如果符号位=1（即参数是正数）, 原来的参数存入eax
    ret

// 你也可以用C语言手写没有分支的版本，例如（仅供参考）
#include <stdint.h>
int32_t abs(int32_t num){
    int32_t mask = (num >> 31);
    return ((num + mask) ^ mask);
}

未定义行为

关于这个话题，LLVM 之父 Chris Lattner 写了一个系列的文章 “What Every C Programmer Should Know About Undefined Behavior”: Part-I，Part-II，Part-III，John Regehr 也写过一个系列文章 "A Guide to Undefined Behavior in C and C++"： Part-I，Part-II，Part-III，它们都值得一看，可以避免你掉进坑里！

Undefined Behavior（行为未定义在C语言规范中） --- 本质上来说任何事都可能发生！

// Demo_5：Undefined Behavior
#include <limits.h>
#include <stdio.h>

int main (void)
{
  printf ("%d\n", (INT_MAX+1) < 0); // 不保证是INT_MIN
  printf ("%d\n", (1 << 32) == 1);  // 不保证移位结果是1
  return 0;
}

Unspecified Behavior（行为依赖编译器和平台的实现）

// Demo_6：Unspecified Behavior
int f() {
  printf("f()\n");
  return 1;
}

int g() {
  printf("g()\n");
  return 2;
}

int sum(int i, int j) {
  return i + j;
}

int main() {
  return sum(f(), g()); 
}

// 观察不同的编译器的输出

C语言char类型是signed char还是unsigned char？不一定，取决于编译器（甚至可以在编译时决定）。

参照GNU gcc中的说明：https://gcc.gnu.org/onlinedocs/gcc/C-Dialect-Options.html （unsigned-char）

代码检查工具

静态检查工具：静态代码分析是指无需运行被测代码，通过词法分析、语法分析、控制流、数据流分析等技术对程序代码进行扫描，找出代码隐藏的错误和缺陷，比如未初始化，越界，死循环，代码不可达等，在整个软件开发生命周期中，30% 至 70% 的代码逻辑设计和编码缺陷是可以通过静态代码分析来发现和修复的，比如 Cppcheck（开源免费），Coverity，Klocwork（商业收费）...

动态检查工具，比如 Valgrind，它是用于构建动态分析工具的探测框架，它包括一个工具集，每个工具执行某种类型的调试、分析或类似的任务，以帮助完善你的程序，比如memory check，Cache miss check ...

PS. 一般会把上述的静态/动态检查工具整合到类似 Jenkins 这样的持续集成（CI）工具之中，代码一有改动就会触发其运行，然后直接观察和分析结果。