CSAPP - 学习笔记 (1): 字节与整数
摘要
最近开了个新坑，打算学习一下 CSAPP 和 Mit S6.081，会把一些学习笔记和实验报告更新在博客上。CSAPP（Computer Systems：A Programmer’s Perspective），即从程序员的角度学习计算机系统，是 CMU 的一门名课，配套同名黑书教材，译为《深入了解计算机系统》。
这一节是 CSAPP 的第一节，包含了整数表示、操作等。
下面是一些有用的链接，供想学习的同学参考：
逻辑运算
逻辑运算：&&, ||, ! 特点：
- 0 被认为是 false
- 非 0 值被认为是 true
- 总是返回 true 或 false
- 短路求值
- 短路求值一种友好的特性，它的优点是：
- 可以用于前置判断，避免非法操作
- 例如，
p&&*p，会先判断指针 p 地址合法，再去访问，避免错误
- 例如，
- 可以减少无用操作
- 例如，
1||func()永远返回 true，无需调用func函数，可以提高效率 当然，短路求值也有一定的缺点
- 例如，
- 基于跳转法实现的，短路求值需要增加很多跳转指令，会把代码块拆分为更小的基本块，给优化带来挑战
- 短路求值的关键是：若结果已确定则直接跳出，否则继续计算结果。需要在每次求解后插入跳转指令。
- 编译优化算法一般以跳转 / 分支拆分得到的基本块为单位，进行块内和块间优化，基本块越小、数量越多，越不利于优化 如果逻辑操作无副作用，那么可以直接使用算术法，相当于不严格按照短路求值实现，但由于无副作用，所以结果是相同的。
可参考 逻辑表达式的短路是如何实现的？ - 知乎 (zhihu.com)
移位
左移: x<<y
左移总是相同的，例如二进制串 "011000010" 左移 3 位后得到 "00010000"，低位用 0 补充，溢出的高位消失不见，规则同时适用于正负数。
右移: x>>y
右边的多余低位被丢弃，左侧的填充规则有两种：
- 逻辑右移：使用 0 填充高位
- 算数右移：使用符号位填充高位 例如串 "10100010"，右移 3 位的结果分别是：
- 逻辑右移：00101000
- 算数右移：11101000 在 C/C++ 语言中，右移均使用 ">>" 操作符，编译器对有符号数进行算数右移，对无符号数进行逻辑右移 在 Java 中，算数右移对应 ">>" 操作符，逻辑右移使用 “>>>”。而且 Java 中只存在有符号数。
未定义行为
如果把一个 8 位的数 x，左移 8 位，会发生什么？
- 直觉来看应该是 0
- 在大多数机器上，会得到 x 本身，因为移位的长度会对数长取模，8%8=0，即左移 0 位
- 这是一种未定义行为，不应该依赖它的结果
整数表示
无符号数
对于 w 位的无符号整数，最小值为 0，最大值为 \(2^w-1\)，所有位都被解释为正数权重，从高到底依次为 \(2^{w-1},2^{w-2},...,2^0\)，数字的值为 \[ B2U(X)=sum_{i=0}^{w-1}x_i\cdot 2^i \] \(B2U(X)\) 表示将比特串 X 转换为无符号数的数值。
有符号数
几乎所有的现代机器都使用补码表示。
补码
补码（Two's Complement），使用最高位作为符号位，权重为 \(-2^{w-1}\)，剩余位与无符号数的权重相同。 \[ B2T(X)=-x_{w-1}\cdot 2^{w-1}+sum_{i=0}^{w-2}x_i\cdot 2^i \] 在补码场景下，负数最小值的表示为 \(T_{min}=10\cdots 0\)，即只有负权重，负数最大值（-1）的表示为 \(11\cdots 1\)，即全部为 1，正数最大值为 \(T_{max}=01\cdots 1\)。 w 位补码的表示范围为 \(-2^{w-1} \sim 2^{w-1}-1\)，正数比负数少一个，这可能会导致各种边界错误。 补码标识下，正负数的转换，可以通过 取反 + 1 得到，例如 4 位数下，2 的表示为 "0010"，按位取反得到 "1101"，再 + 1 得到 “1110”，这就是 - 2.
- 这是由于负数数量比正数多 1 个。
- \(T_{min}\) 的相反数还是 \(T_{min}\)
除了补码，还有两种标准表示方法：
反码
反码（One's Complement），除了最高位的权是 \(-(2^{w-1}-1)\)，不是 \(-2^{w-1}\)，剩下的跟补码是一样的， \[ B2O(X)=-x_{w-1}\cdot (2^{w-1}-1)+sum_{i=0}^{w-2}x_i\cdot 2^i \]
原码
原码（Sign-Magnitude），最高有效位是符号位，用来确定剩下的位应该取负权还是正权： \[ B2S(X)=-(-1)^{x_{w-1}}\cdot sum_{i=0}^{w-2}x_i\cdot 2^i \] 这两种方法都有一个奇怪的属性，对于数字 0 有两种表示，把 \([00\cdots 0]\) 解释为 + 0，把 \([10\cdots 0]\) 解释为 - 0，虽然过去存在基于反码表示的机器，但几乎所有的现代机器都使用补码。浮点数中有使用原码。
转换
无符号数和符号数的转换遵循以下规则：
- 保留位特征，即数字的比特串存储不会改变
- 重新解释，根据比特的权重重新计算
- 可能会有未期望的效果，例如，加或减 \(2^w\)，即转换出现问题
- 同时包含有符号和无符号数的表达式，有符号数会转换为无符号数 无符号数和有符号数进行比较 / 计算时，会将有符号数隐式转换为无符号数，例如 \(-1>0u\)，在使用时要注意。 例如，下面的代码，无符号数 \(i\ge 0\) 恒成立，代码会数组越界或者死循环。
1 | unsigned int i; |
另外，sizeof 的返回值也是无符号数。 上面的倒数计数的场景，需要改写成如下形式才能正常工作，它利用了溢出的特性，第一眼看上去会很反直觉。
1 | unsigned int i; |
在 C 语言中，无符号数和有符号数的转换是隐式的，不会有任何的 warning 或者 error。而在 Go 语言中，需要显式对数值进行类型转换，避免了可能的问题。
扩展
如何把一个 w 位的数扩展为 w+k 位的数，数值不变？
有符号数
做法是，新增的高位复制符号位，剩余位保持不变。 例如 "1100"，扩展增加 1 位，结果是 "11100"。观察可知，\(-2^3=-2^4+2^3\)，最高位及更高位的权重和不变，整个结果不变。
无符号数
增加 0 即可。
截断
当一个 w+k 位的数去掉高 k 位时，对
- 无符号数，等价于对 \(2^w\) 取模
- 有符号数，可能正负会发生变化
整数运算
加法
考虑 w 位的两个数 u,v 相加
无符号数
等价于两数相加后截断只保留低 w 位（可能会有进位被丢弃） \[ s=UAdd_w(u,v)=(u+v)mod 2^w \] 例如两个 4 位数，\(13+5=18\ mod\ 16=2\)
补码加法
有符号的加法在比特特征上与无符号数相同，但是从表现上看，会出现两种情况：
- 正数溢出：两个正数相加，超过 \(T_{max}\)，变为负数
- 负数溢出，两个负数相加，小于 \(T_{min}\)，变为正数 减法可以转换为加法求解。
乘法
两个 w 位数相乘，可能需要至多 2w 位存储结果（考虑不可达的上界，两个 w+1 位的数相乘，最高位为 1，其余位时 0，结果为 2w+1 位）。 同样，需要截断取低 w 位，对无符号数来说，等价于取模。 对于有符号数，经过证明，其乘法与无符号数的乘法位级表示是等价的，同样可能会出现溢出现象。 由于乘法会消耗更多时钟周期（现代计算机需要 3 个），移位只需要 1 个时钟周期，编译器会对乘法进行优化。移位与无符号整数乘比特等价，进而与符号整数相乘等价。
除法
同样的，除法也可以优化为右移操作，由于整数除法总是舍入到 0，对于补码除法，需要引入偏置位进行修正。
无符号数使用建议
从前面转换一节讲的例子，可以看到无符号整数的使用可能会引发奇怪的问题。下面是一些使用无符号数的场景
- 加密运算
- 表示集合，bitmap 需要强调的是，“无符号数适用于非负值的场景” 是一种常见的误区，一个例子就是之前提到的倒排问题。在《Go 程序设计语言》中，作者也建议了一般不要使用无符号数，除非像加密算法这种特殊的场景。
大端与小端
多个字节存储时，根据字节在内存中的地址顺序，有两种存储方式，例如 0x01234567，
- 大端，高位字节在先，01,23,45,67
- 网络传输
- 小端，低位字节在先，67,45,23,01
- x86，ARM 处理器 大端优势是读取直观，但这对计算机来说无关紧要，计算机只需要一个统一的标准进行计算即可。