CS:APP学习笔记之信息的表示和处理（二）
本文记录《深入理解计算机系统》第3版中第2章信息的表示和处理的一些知识点。
第2章 信息的表示和处理
信息存储
32 or 64位程序
大多数 64 位机器也可以运行为 32 位机器编译的程序，这是一种向后兼容。因此，举例来说，当程序用如下伪指令编译后
gcc -m32 prog.c
该程序就可以在 32 位或 64 位机器上正确运行。另一方面，若程序用下述伪指令编译
gcc -m64 prog.c
那就只能在 64 位机器上运行。
因此，将程序称为“ 32 位程序”或“ 64 位程序”时，区别在于该程序是如何编译的，而不是其运行的机器类型。
大端法和小端法
最低有效字节在最前面的方式，称为小端法（little endian） 。最高有效字节在最前面的方式，称为大端法（big endian）。假设变量 x 的类型为int，位于地址 0x100 处，它的十六进制值为 0x01234567 。地址范围 0x100 ～ 0x103 的字节顺序依赖于机器的类型：
逻辑右移与算术右移
一般而言，机器支持两种形式的右移：逻辑右移和算术右移。逻辑右移在左端补个 0 。算术右移是在左端补个最高有效位的值。
C 语言标准并没有明确定义对于有符号数应该使用哪种类型的右移一一算术右移或者逻辑右移都可以。不幸地，这就意味着任何假设一种或者另一种右移形式的代码都可能会遇到可移植性问题。然而，实际上，几乎所有的编译器/机器组合都对有符号数使用算术右移，且许多程序员也都假设机器会使用这种右移。另一方面，对于无符号数，右移必须是逻辑的。
整数表示
64位整型取值范围
编码方式
不同数值类型编码方式是不一样的，尤其是无符号整数和有符号整数之间
无符号整数编码
无符号整数用无符号整数编码，无符号数编码定义如下：
对向量\(\vec{x} = [x_{w-1}, x_{w-2}, \cdots, x_{0}]\):
\[ B2U_{w}(\vec{x}) \doteq \sum_{i=0}^{w-1} x_{i} 2^{i} \]
\(B2U_{4}([1111]) = 1\cdot 2^3 + 1\cdot 2^2 + 1\cdot 2^1 + 1\cdot 2^0 = 8 + 4 + 2 + 1 = 15\)
\(w\)位的无符号整数最大值为\(U\max_w \doteq \sum_{i=0}^{w-1} 2^{i} = 2^w -1\)。
补码编码
最常见的有符号数的计算机表示方式就是补码形式（Two’s complement）。在这个定义中，将字的最高有效位解释为负权。补码编码的定义如下：
对向量\(\vec{x} = [x_{w-1}, x_{w-2}, \cdots, x_{0}]\):
\[ B2T_{w}(\vec{x}) \doteq - x_{w-1}2^{w-1} + \sum_{i=0}^{w-2} x_{i} 2^{i} \]
最高有效位\(x_{w-1}\)称为符号位。
\(B2T_{4}([1111]) = -1\cdot 2^3 + 1\cdot 2^2 + 1\cdot 2^1 + 1\cdot 2^0 = -8 + 4 + 2 + 1 = -1\)
\(w\)位的有符号整数最小值为\(T\min_w \doteq -2^{w-1}\)，最大值为\(T\max_w \doteq \sum_{i=0}^{w-2} 2^{i} = 2^{w-1} -1\)。
反码和原码
有符号数还有另外两种标准表示方法（现代机器基本不用这两种）。
反码（Ones’ Complement）：除了最高有效位的权是\(-(2^{w-1} - 1)\)而不是\(-2^{w-1}\)，和补码相同：
\[ B2O_{w}(\vec{x}) \doteq - x_{w-1}(2^{w-1} - 1) + \sum_{i=0}^{w-2} x_{i} 2^{i} \]
原码（Sign-Magnitude）：最高有效位是符号位，用来确定剩下的位应该取负权还是正权：
\[ B2S_{w}(\vec{x}) \doteq - 1^{x^{w-1}} + \sum_{i=0}^{w-2} x_{i} 2^{i} \]
这两种表示方法都有一个奇怪的属性，那就是对于数字 0 有两种不同的编码方式。这两种表示方法，把[ 00…0 ]都解释为+ 0 。而值-0 在原码中表示为[10…0 ]，在反码中表示为[ 11…1]。虽然过去生产过基于反码表示的机器，但是几乎所有的现代机器都使用补码。
注意补码（Two’s Complement）和反码（Ones’ complement）的名称中的撇号的位置是不同的（理解这个英文的区别能更好的理解补码和反码）。术语补码来源于这样一个情况，对于非负数\(x\)，用\(2^w - x\)来计算\(-x\)的表示。术语反码来源于这样一个属性，用\([ 111\cdots1] - x\)来计算\(-x\)的反码表示。
整数计算
无符号数的逆元
对满足\(0 \leq x < 2^w\)的任意\(x\)，其\(w\)位的无符号逆元\(- _{w}^{u}x\) 由下式给出：
\[ - _{w}^{u}x = \left\{ \begin{array}{ll} x, & x = 0 \\ 2^w - x, & x > 0 \end{array} \right. \]
意思就是任何一个数，都能找到另外一个数让他们两加起来的位全为0。
补码的非
对满足 \(TMin_w \leq x \leq TMax_w\)的\(x\)，其补码的非 \(- _{w}^{t}x\)由下式给出：
\[ - _{w}^{t}x = \left\{ \begin{array}{ll} TMin_w, & x = TMin_w \\ -x, & x > TMin_w \end{array} \right. \]
意思就是任何一个数，都能找到另外一个数让他们两加起来的位全为0。
对C来说，任何一个数都满足 -x = ~x + 1。
浮点数
IEEE浮点表示
IEEE 浮点标准用\(V = (-1) ^{s} \times M \times 2^E\)的形式来表示一个数:
- 符号 (sign) \(s\)决定这数是负数。
- 尾数 (significand) \(M\) 是一个二进制小数，它的范围是\(1 \sim 2-\epsilon\)，或者是 \(0 \sim 1 - \epsilon\) 。
- 阶码（exponent）\(E\) 的作用是对浮点数加权，这个权重是 2 的 \(E\) 次幂（可能是负数）。
将浮点数的位表示划分为三个字段，分别对这些值进行编码：
- 一个单独的符号位\(s\)；
- \(k\)位的阶码字段\(exp = e_{k-1}\cdots e_{1}e_{0}\)编码阶码\(E\)；
- \(n\)位小数字段\(frac = f_{n-1}\cdots f_{1} f_{0}\)编码尾数\(M\)， 编码出来的值也依赖于阶码字段的值是否等于0。
两种最常见的格式如下图。在单精度浮点格式（ float）中，
\(s\)、 \(exp\) 和 \(frac\) 字段分别为 1 位、 8 位和 23
位，得到一个 32 位的表示。在双精度浮点格式（ double)
中，\(s\)、 \(exp\) 和 \(frac\) 字段分别为 1 位、11 位和 52
位，得到一个 64 位的表示。
给定位表示，根据\(exp\)的值，被编码的值可以分为三种不同的情况（最后一种情况有两个变种）。下图说明了对单精度格式的情况。
情况1：规格化的值
这是最普遍的情况。当 \(exp\) 的位模式既不全为 0 （数值 0 ），也不全为 1 （单精度数值为255 ，双精度数值为 2047 ）时，都属于这类情况。在这种情况中，阶码字段被解释为以偏置（ biased ）形式表示的有符号整数。也就是说，阶码的值是 \(E=e—Bias\) ，其中 \(e\) 是无符号数，其位表示为\(e_{k-1}\cdots e_{1}e_{0}\) ，而\(Bias\)是一个等于\(2^{k-1} - 1\)（单精度是 127 ，双精度是 1023 ）的偏置值。由此产生指数的取值范围，对于单精度是\(-126 \sim +127\) ，而对于双精度是\(-1022\sim+1023\) 。
小数字段\(frac\) 被解释为描述小数值\(f\)，其中 \(0 \leq f < 1\) ，其二进制表示为\(0.f_{n-1}\cdots f_{1} f_{0}\)，也就是二进制小数点在最高有效位的左边。尾数定义为 \(M = 1 + f\)。有时，这种方式也叫做隐含的以 1 开头的 (implied leading 1) 表示，因为可以把 \(M\) 看成一个二进制表达式为 \(1.f_{n-1}f_{n-2}\cdots f_{0}\) 的数字。既然我们总是能够调整阶码 \(E\) ，使得尾数 \(M\) 在范围 \(1 \leq M < 2\) 之中（假设没有溢出），那么这种表示方法是一种轻松获得一个额外精度位的技巧。既然第一位总是等于 1 ，那么就不需要显式地表示它。
情况2：非规格化的值
当阶码域为全 0 时，所表示的数是非规格化形式。这种情况下，阶码值是 \(E = 1 - Bias\) ，而尾数的值是\(M = f\)，也就是小数字段的值，不包含隐含的开头的 1 。
非规格化数有两个用途。首先，它们提供了一种表示数值 0 的方法，因为使用规格化数，我们必须总是使\(M \geq 1\)，因此就不能表示 0 。实际上，\(+0.0\)的浮点表示的位模式为全 0 ：符号位是 0 ，阶码字段全为 0 （表明是一个非规格化值），而小数域也全为 0 ，这就得到\(M = f = 0\)。令人奇怪的是，当符号位为 1 ，而其他域全为 0 时，得到值\(-0.0\) 。根据IEEE浮点格式，值\(+0.0\)和\(-0.0\)在某些方面被认为是不同的，而在其他方面是相同的。
非规格化数另外一个功能是表示那些非常接近于\(0.0\)的数。它们提供了一种属性，称为逐渐溢出 (gradual underflow) ，其中，可能的数值分布均匀地接近于\(0.0\)。
情况3：特殊值
最后一类数值是当指阶码全为 1 的时候出现的。当小数域全为 0 时，得到的值表示无穷。当\(s = 0\)时是\(+\infty\)，\(s = 1\)时是\(-\infty\)。当我们把两个非常大的数相乘，或者除以零，无穷能够表示溢出的结果。当小数域为非零时，结果值被称为 “NaN ”，即“不是一个数 (Not a Number) ”的缩写。一些运算的结果不能是实数或无穷，就会返回这样的 NaN 值，比如当计算\(\sqrt{-1}\)或\(\infty - \infty\)时。在某些应用中，表示未初始化的数据时，它们也很有用处。