CSAPP-02信息的表示和处理
三种重要的数字表示：
- 无符号（unsigned）编码：大于或等于零的数字；
- 补码（two’s-complement）编码：有符号整数；
- 浮点数（floating-point）编码：实数的科学计数法的以2为基数的版本。
计算机的表示法是用有限数量的位来对一个数字编码，因此，当结果太大以至不能表示时，某些运算就会溢出（overflow）。
浮点数运算有完全不同的数学属性：
- 整数的表示虽然只能编码一个相对较小的数值范围，但是这种表示是精确的；
- 浮点数虽然可以编码一个较大的数值范围，但是这种表示只是近似的。
重点：
- 用几种不同的二进制表示形式来编码数值 –> 对理解机器编程很有必要；
- 操作数字的位级表示，得到几种进行算术运算的方式 –> 对理解编译器产生的机器级代码很重要，编译器会试图优化算术表达式求值的性能；
- 一组核心的数学原理：编码的定义、一些属性（范围、位级表示、算术运算），抽象的观点来分析。
信息存储
大多数计算机使用8位的块（字节，byte）作为最小的可寻址的内存单位，而不是访问内存中单独的位。机器级程序将内存视为一个非常大的字节数组，称为虚拟内存（virtual memory），内存的每个字节都由一个唯一的数字来标识，称为它的地址（address），所有可能地址的集合就称为虚拟地址空间（virtual address space）。虚拟地址空间只是一个展现给机器级程序的概念性映像，实际的实现是将动态随机访问存储器（DRAM）、闪存、磁盘存储器、特殊硬件和操作系统软件结合起来，为程序提供一个看上去统一的字节数组。
布尔代数
C中的位级运算
|就是OR（或）；&就是AND（与）；~就是NOT（取反）；^就是EXCLUSIVE-OR（异或）。
C中的逻辑运算
||对应 OR；&&对应 AND；!对应 NOT。
C中的移位运算
<<左移；>>右移。
整数表示
无符号编码：正整数。
补码：最高位为符号位。当符号位被设置为1时，表示值为负，当设置为0时，值为非负。
- 补码 1000 = -8；
- 补码 0111 = 7。
| 补码的范围是不对称的： | TMin | = | TMax | + 1。一半的位模式（符号位设置位1）表示负数，另一半（符号位设置为0）表示非负。因为0是非负数，也就意味着能表示的整数比负数少了一个。 |
其他两种表示方式：
反码（Ones’ Complement）：和补码的区别是最高位的权不一样。
原码（Sign-Magnitude）：最高有效位是符号位，用来确定剩下的位应该是取负权还是正权。
整数运算
无符号加法
整数加法：
”字长膨胀“：要想完整地表示算术运算地结果，不能对字长做任何限制。一些编程语言如Lisp支持无限精度地运算，允许任意的（内存限制之内）整数运算，但更常见的是，编程语言支持固定精度的运算，因此像”加法“和”乘法“这样的运算不同于它们在整数上的相应运算。
无符号加法：
原理：
说一个算术运算溢出，是指完整的整数结果不能放到数据类型的字长限制中去。
补码加法
原理：
补码的非
无符号乘法
补码乘法
3位无符号和补码乘法示例：
乘以常数
在大多数机器上，整数乘法指令相当慢，需要10个或者更多的时钟周期，然而其他整数运算（例如加法、减法、位运算和移位）只需要1个时钟周期。因此，编译器使用了一项重要的优化，试着用移位和加法运算的组合来代替乘以常数因子的乘法。
首先考虑乘以2的幂的情况，再概括成乘以任意常数。
乘以2的幂
左移一个数值等价于执行一个与2的幂相乘的无符号乘法。
注意，无论是无符号运算还是补码运算，乘以2的幂都可能会导致溢出。结果表明，即使溢出的时候，通过移位得到的结果也是一样的，因为高位会被截断。
乘以任意常数
例如：x * 14。
利用 14 = 2^3 + 2^2 + 2^1，编译器会将乘法重写为 (x«3) + (x«2) + (x«1)，将一个乘法替换为三个移位和两个加法。无论x是无符号的还是反码，甚至当乘法会导致溢出时，两个计算都会得到一样的结果。更好的是，编译器还可以利用属性 14 = 2^4 - 2^1，将乘法重写为 (x«4) - (x«1)，这时只需要两个移位和一个减法。
除以2的幂
在大多数机器上，整数除法要比整数乘法更慢，需要30个或者更多的时钟周期。
除以2的幂也可以用移位运算来实现，只不过用的是右移，而不是左移。无符号和补码分别使用逻辑移位和算术移位来达到目的。
整数除法总是舍入到零。
- 除以2的幂的无符号除法：右移。
- 除以2的幂的补码除法，向下舍入：
- 除以2的幂的补码除法，向上舍入：
浮点数
二进制小数
仅考虑有限长度的编码，那么十进制表示法不能准确的表达像1/3和5/7这样的数。类似，小数的二进制表示法只能表示那些能够被写成 X × 2^y 的数，其他的值只能够被近似地表示。例如1/5可以用十进制小数0.20精确表示，但并不能把它准确地表示为一个二进制小数，增加二进制表示的长度可以提高表示的精度。
IEEE浮点表示
定点表示法不能很有效地表示非常大的数字，例如 5 × 2^100 是 101 后面跟随100个零的位模式来表示。相反，我们希望通过给定 x 和 y 的值，来表示形如 x × 2^y 的数。
IEEE浮点标准用 V=(-1)^s × M × 2^E 的形式来表示一个数：
- 符号（sign）s决定这数是负数（s=1）还是正数（s=0）,而对于数值0的符号位解释作为特殊情况处理。
- 尾数（significand）M是一个二进制小数。
- 阶码（exponent）E的作用是对浮点数加权，这个权重是2的E次幂（可能是负数）。
讲浮点数的位表示划分为三个字段：
- 一个单独的符号位 s 直接编码符号s。
- k 位的阶码字段 exp = [e_(k-1) … e_1 e_0] 编码阶码E。
- n 位小数字段 frac = [f_(n-1) … f_1 f_0] 编码尾数M，但是编码出来的值也依赖于阶码字段的值是否等于0。
单精度和双精度：
- 在单精度浮点格式（C语言中的float）中，s、exp和frac字段分别为 s=1 位、k=8位 和 n=23 位，得到一个32位的表示。
- 在双精度浮点格式（C语言中的double）中，s、exp和frac字段分别为 s=1 位、k=11位 和 n=52 位，得到一个64位的表示。
给定位标识，根据exp的值，被编码的值可以分成三种不同的情况（最后一种情况有两个变种）：
数字示例
舍入
- 向偶数舍入
- 向零舍入
- 向下舍入
- 向上舍入
浮点运算
- 舍入
- 精度问题
- 规则
- 1/-0 = -∞
- 1/+0 = ∞
- 阿贝尔群
- (3.14 + le10) - le10 = 0.0; 因为舍入3.14会丢失；
- 3.14 + (le10 - le10) = 3.14; 作为阿贝尔群，大多数值在浮点加法下都有逆元，x + (-x) = 0;
- 编译器优化
- 代码：
- x=a+b+c;
- y=b+c+d;
- 编译器优化：
- t=b+c;
- x=a+t;
- y=t+d;
- 然而对于x来说，这个计算可能会产生与原始值不同的值（先后计算的舍入问题），编译器会倾向保守，避免任何对功能产生影响的优化。
- 代码：
