CSAPP 02 - 二进制

  计算机是二进制的世界。

基础

  所谓二进制，简单来说就是只用 0 和 1 来表示所有的信息。与二进制密切相关的还有八进制和十六进制。尤其是十六进制，在计算机中应用十分广泛。

  计算机使用字节作为最小的可寻址的内存单位。机器级程序将内存视为一个很大的字节数组，内存中每个字节都由一个唯一的数字来标识，称为它的地址。

寻址和端序

  对于一个跨越多字节的程序对象，有以下两个核心问题要解决：

1. 寻址：规定一个多字节对象的地址就是其使用字节中最小的地址。
2. 存储：几乎所有的计算机中，对象都被储存为连续的字节序列。

  即使是连续储存字节序列，也有端序问题，有两种基础的端序：小端序和大端序。对于四字节整数 0x01234567，两种端序的储存排列如下：

  大多数 Intel 兼容机只使用小端序，一些处理器如 PowerPC 和 MIPS 使用大端序。现在许多新的机器支持双端法。但是注意：一旦选择了特定的操作系统，字节顺序也就固定下来了。

字符串

  C 语言中的字符串编码为一个以 NULL (0) 结尾的字符数组。

  字符串的储存没有端序问题，因而，文本数据比二进制数据具有更强的平台独立性。

整数

布尔代数

  针对 0 和 1 两个数字，定义下列四种运算：

Operator	Meaning	Usage
~	NOT	~1 = 0
&	AND	1 & 1 = 1
|	OR	1 | 0 = 1
^	EXCLUSIVE OR	1 ^ 0 = 1

  将运算扩展到 w 位上：对于多位的二进制数字执行布尔运算，即对其每个位分别执行布尔运算。有几条常用的规律：

1. & 和 | 的分配律

a & (b | c) = (a & b) | (a & c)
a | (b & c) = (a | b) & (a | c)

2. ^ 0 和 ^ 1

0 ^ a =  a
1 ^ a = ~b

3. ^ 的技巧

  注意：连续的 ^ 运算可以交换顺序，所以有下列性质。

(a ^ b) ^ a = b

位级运算

  C 语言中还有一组逻辑运算符：||，&& 和 !，逻辑运算表达式的结果只有两种：True (1) 或 False (0)。对于一个数而言，值为非 0 则代表 True，否则为 False。

移位运算

  对于一个 w 位的二进制数 x，将其看作一个位向量，表示为：x = [x_w-1, x_w-2, …, x₀]

1. 左移操作

  x 左移 k 位：丢弃其最高的 k 位，并在右端补上 k 个 0：[x_w-k-1, x_w-k-2, …, x₀, 0, …, 0]

2. 右移操作

• 逻辑右移 (无符号数)：和左移正好相反，丢弃最低的 k 位，在左端补上 k 个 0。
• 算术右移 (有符号数)：丢弃最低 k 位，在左端补上 k 个最高有效位的值，即：[x_w-1, …, x_w-1, x_w-2, …, x_k]。

  几乎所有的编译器机器组合都对有符号数使用算术右移操作。

无符号数

  无符号数只能表示大于等于 0 的数字，其使用原码编码：

范围

  一个 w 位的无符号数，其最大值的位向量表示为 [1, 1, …, 1]。即 Umin = 0，Umax = 2^w - 1。

  并且 B2U_w 和 U2B_w 是一个双射，即对于一个确定位数的无符号数，其二进制表示和十进制表示是唯一对应的。

扩展

  无符号数的扩展称作零扩展。将一个 w 位的无符号数扩展为一个 k 位 (k > w) 的无符号数，即在原来位向量的左端添加 k - w 个 0 得到新的无符号数。

src: [Xw-1, ..., X0]
new: [0, ..., 0, Xw-1, ..., X0]

U2T

  一个 w 位的无符号数转换为一个 w 位的有符号数，就是简单地重新解释即可，数学规律对应如下：

  对于提升转换即，一个 w 位的无符号数转换位一个大于 w 位 (k) 的有符号数：

1. 首先进行零扩展得到一个新的无符号数。

2. 然后重新解释。

  对于提升而言，转换后的有符号数显然是一个等于原数字的正数。

截断

  一个 w 位的无符号数截断为一个 k 位 (k < w) 的无符号数，即删除前 w - k 位，然后重新解释即可。

B2Uk([Xk-1, ..., X0]) = B2Uw([Xw-1, ..., X0]) mod 2^k

加减

  两个 w 位的无符号数加法，结果可能需要 w + 1 位来表示，此时会发生溢出。

  对于两个无符号数 x 和 y，他们的加法结果 z 发生溢出的条件是：z < x || z < y。

  对于减法，应将减数转换为无符号数的逆元后再执行加法：

有符号数

  有符号能表示 0，负数和正数，其使用补码编码：

范围

  一个 w 位的有符号数，其最小值的位向量表示为 [1, 0, …, 0]，最大值的位向量表示为 [0, 1, …, 1]。即 Tmin = 2^(w-1)。Tmax = 2^(w-1) - 1。

  并且 B2T_w 和 T2B_w 是一个双射，即对于一个确定位数的有符号数，其二进制表示和十进制表示是唯一对应的。

扩展

  有符号数的扩展称作符号扩展。将一个 w 位的有符号数扩展为一个 k 位 (k > w) 的有符号数，即在原来位向量的左端添加 k - w 个最高有效位得到新的有符号数。

src: [Xw-1, ..., X0]
new: [Xw-1, ..., Xw-1, ..., X0]

T2U

  一个 w 位的有符号数转换为一个 w 位的无符号数，也是简单地重新解释即可，数学规律对应如下：

  对于提升转换即，一个 w 位的有符号数转换位一个大于 w 位 (k) 的无符号数：

1. 首先进行符号扩展得到一个新的有符号数。

2. 然后重新解释。

  对于提升而言，如果原有符号数是一个正数，那么符号扩展的结果也是一个正数，最后得到的也是相等的正数。

截断

  一个 w 位的有符号数截断为一个 k 位 (k < w) 的有符号数，即删除前 w - k 位，然后重新解释即可。

B2Tk([Xk-1, ..., X0]) = U2Tk( B2Uw([Xw-1, ..., X0]) mod 2^k )

  因为和无符号数的截断过程一致，可以先将其当作无符号数截断，然后再解释为有符号数。

加减

  有符号数加法和无符号数具有相同的位级表示，可以将有符号数看作无符号数来运算，将结果再转化回来。

  有符号数的加法运算可能有两种溢出，正溢出和负溢出。

  对于两个 w 位的有符号数 x 和 y，他们加法结果 z 发生溢出的条件是：

1. 正溢出：x > 0 && y > 0 but z < 0
2. 负溢出：x < 0 && y < 0 but z > 0

  有符号数的减法运算同样使用逆元完成，由于有符号数的范围不对称，采用溢出的方式来定义 Tmin 的逆元：

乘除运算

  对于两种整数的乘法而言，他们的位级表示都是一样的，并且：两个 w 位的整数相乘，结果可能需要 2w 位来表示，所以运算结果会进行低位截断。

  对于无符号数乘法结果的取值：

  对于有符号数乘法结果的取值：

  乘法有两种特殊情况可以特殊处理：

1. x * 2^k：此时可以使用左移操作等价于 x << k
2. x * c (c 是常数)：可以将 c 分解为 2 次幂数字的和

x * 14 = x * (2^3) + x * (2^2) + x * (2^1)
       = (x << 3) + (x << 2) + (x << 1)

x * 14 = x * (2^4) - x * (2^1)
       = (x << 4) - (x << 1)
       
x * 3  = x * (2^1) + x * (2^0)
       = (x << 1) + x

  整数乘法的结果总是一个整数，但是除法可能出现除不尽的情况，这时候就需要进行舍入操作。C 语言中整数除法都执行向 0 舍入，如 3.14 -> 3，-3.14 -> 3。

  考虑一种特殊情况：除数是 2 次幂的除法操作即 x / y，y = 2^k。这时可以用右移操作来完成：

1. x / 2^k，x > 0：执行逻辑右移即 x >> k，然后向下舍入
2. x / 2^k，x < 0：直接进行算术右移会产生偏差，可以给 x 加一个偏置 (bias) 2^k - 1 来修正结果即 (x + 2^k - 1) / 2^k。

  两种情况可以由一条表达式综合：

(x<0 ? x + (1<<k) - 1 : x) >> k

混合

  在 C/C++ 中，如果一个表达式中同时出现有符号数和无符号数，那么编译器将会隐式的将所有数字看作无符号数，然后再进行求值。

  考虑表达式-1 < 0U：因为这里同时出现了有/无符号数，所以他们都被当作无符号数。-1 的位级表示是 0xff…ff，远远大于 0。因此这个表达式反直觉的被求值为 False。

  在执行数学运算时，不同位数的几个整数参与运算，结果的位数应该是其中的最大位数。

浮点数

  浮点数很适合用来表达很大或很小的数，但是却不能精确的表达每一个数。

二进制小数

  十进制小数可以表示为：d_m-1d_m-2…d₀.d_-1…d_-n (-1 < d < 10)，其数学上等于：

  二进制小数的表示与之相类似：b_m-1b_m-2…b₀.b_-1…b_-n (b = 0 / 1)，数学上等于：

  就如十进制小数无法精确表示 0.3 一样，二进制小数也不能精确表达 V = x * 2^y 外的数字：

  对于 0.2 这个数字而言，二进制小数就无法精确表示，如果只用很少位来表示 0.2，实际偏差十分大，但是通过不断的增加位数，就可以不断的提高精度：

IEEE754 编码

  二进制小数来表达浮点数虽然简单清晰，但是却太浪费位了，能表达的数字范围太小。IEEE 发布了浮点数编码标准 IEEE754，用类似科学计数法的方式来最大化的利用位，让其能表达更大范围的数字。

  IEEE 浮点数使用形式为 V = (-1)^s * M * 2^E 来表示小数：

1. 符号 s：如果 s 为 1，那么 V 就是负数，否则为正数
2. 尾数 M：尾数是一个二进制小数，范围在 [1, 2) 或 [0, 1)
3. 阶码 E：2 的指数幂，可以是负数，用来给浮点数加权

  有两种浮点数类型，根据位数分为单精度和双精度，他们的位分布如下：

  根据阶码的值，可以将浮点数分为三类，三类浮点数有不同的用处：

1. 规格化的值：0 < e < 0xff…ff

  大多数的浮点数都被解释为规格化的值，如 0.1，3.14 等等。规格化值的编码规则：

  对于一个阶码为 w 位的浮点数，现在定义其偏置 bias = 2^w-1 - 1。

• 阶码 E：此时阶码被定义为 E = e - bias
• 尾数 M：定义尾数 M = 1 + f

  据此可以根据公式得出浮点数的数值。

2. 非规格化的值：exp = 0

  非规格化的值跟 0 有很大关系，他有两个用途：

• 根据符号位，非规格化的值可以表示+0和-0，他们两个某些方面的属性是不同的
• 用于表示非常趋近于 0 的数，这种属性叫逐渐溢出，这些可能的数均匀的分布在 0 周围

  非规格化的值的编码规则：

• 阶码 E：此时阶码被定义为 E = 1 - bias
• 尾数 M：定义尾数 M = f

3. 特殊值：e = 0xff…ff

  特殊值也有两种用途，并且是根据小数域 f 进行区分的：

• f = 0：表示无穷，并且根据符号位可以分为正无穷和负无穷
• f != 0：此时特殊值为NaN，即 Not a Number

舍入

  因为有限位数的浮点数无法解决精度问题，所以根据浮点数来获取数据时要考虑舍入问题，加上之前的整数舍入规则，即向零舍入，IEEE 规定了四种舍入方式：

1. 向偶舍入：将一个数舍入到离它最近的边界，1.5，0.5 这样的中间数则舍入到偶数边界 (2 和 0)。这种舍入规则是最常用的，因为它减少了统计偏差
2. 向零舍入：与整数舍入规则类似
3. 向上舍入
4. 向下舍入

运算

  IEEE 规定的浮点数的运算规则独立于硬件和软件，但是因为舍入问题，浮点运算不满足一些运算率：

1. 不满足加法交换率

(3.14 + 1e10) - 1e10 = 0
3.14 + (1e10 - 1e10) = 3.14

2. 不满足乘法结合和分配律

1e20 * (1e20 - 1e20) = 0
1e20 * 1e20 - 1e20 * 1e20 = NaN

C 语言

  C 语言标准不要求机器使用 IEEE 浮点，所以没有标准的方法来改变舍入方式或者得到诸如 -0、正无穷、负无穷或 NaN 之类的特殊值。

  关于几个类型之间的转换问题：

From	To	Overflow	Roundoff
int	float	Not	Maybe
int	double	Not	Not
float	int	Maybe	Maybe
float	double	Not	Not
double	int	Maybe	Maybe
double	flaot	Maybe	Maybe