CSAPP - 01.bits, Bytes and Integers

1. 核心概念：位、字节与字

在计算机系统中，所有信息都表示为二进制位（bits）。

• 字节 (Byte)：是内存中最小的可寻址单位，通常由8个位（bit）组成。内存可以看作是一个巨大的字节数组，每个字节都有一个唯一的地址。

• 字 (Word)：是处理器处理数据的标称大小（nominal size）。字长（Word Size）决定了虚拟地址空间的最大大小。

• CPU需要通过地址来访问内存中的数据，存放这些地址的地方就是寄存器（特别是地址寄存器） 。

• 寄存器的宽度等于字长。这意味着一个32位的CPU，其地址寄存器最多只能存储32位的地址。

  • 32位系统：字长为32位（4字节），虚拟地址空间最大为 $2^{32}$ 字节，即 4GB。
  • 64位系统：字长为64位（8字节），理论地址空间可达 $2^{64}$ 字节，但实际系统（如x86-64）通常支持48位地址，即 256TB。

C语言基本数据类型大小

不同数据类型在不同架构的机器上可能占用不同大小的内存。表格中为所占的字节数。

C Data Type	Typical 32-bit	Intel IA32	x86-64
char	1	1	1
short	2	2	2
int	4	4	4
long	4	4	8
float	4	4	4
double	8	8	8
pointer	4	4	8

2. 字节序 (Byte Ordering)

当一个数据（如int）需要多个字节存储时，就涉及到了字节在内存中的排列顺序问题。指针指向的地址与大小端无关，总是指向该数据的第一个字节（即最低地址的字节）。

• 小端表示法 (Little-Endian)：数据的最低有效字节 (Least Significant Byte, LSB) 存放在最低地址。大多数个人电脑（如x86架构）采用此模式。
• 大端表示法 (Big-Endian)：数据的最高有效字节 (Most Significant Byte, MSB) 存放在最低地址。一些服务器和网络协议（如Internet Protocol）采用此模式。

示例：一个4字节的变量 x，值为 0x01234567，存放在地址 0x100 处。

Endian Type	Addr 0x100	0x101	0x102	0x103
Big Endian	01	23	45	67
Little Endian	67	45	23	01

注意：字符串是由字符（单字节）数组表示的，每个字符使用如ASCII这样的标准编码。因此，字符串的存储不受字节序的影响。

方案一：通过指针检测系统字节序

可以通过C代码判断机器是大端序还是小端序：

利用 C 语言指针的强制类型转换，查看整数的第一个字节。

#include <stdio.h>

int is_little_endian() {
    unsigned int x = 1; // 16进制表示: 0x 00 00 00 01
    
    // 核心逻辑：
    // 1. &x 取出 int 的地址
    // 2. (char*) 强制转换为“单字节视角”
    // 3. * 解引用，只读取内存中最低地址的那 1 个字节
    char *c = (char*)&x; 

    return *c; // 返回 1 则是小端，返回 0 则是大端
}

int main() {
    if (is_little_endian()) {
        printf("Detected: Little-endian (小端)\n"); // 此时内存低地址存放的是 01
    } else {
        printf("Detected: Big-endian (大端)\n");    // 此时内存低地址存放的是 00
    }
    return 0;
}

(char*)&x: 这是最关键的一步。

• &x 指向 4 字节的整体起始位置。
• 转换为 char* 后，编译器认为指针指向的“跨度”只有 1 个字节。

方案二：使用 show_bytes 可视化内存

不仅检测，还能看到完整的字节排列。

#include <stdio.h>

typedef unsigned char *byte_pointer;

void show_bytes(byte_pointer start, int len) {
    // 遍历内存，从低地址向高地址打印
    for (int i = 0; i < len; i++) {
	    //这里的start被解释为unsigned char指针，[]操作每次移动1字节
        printf(" %.2x", start[i]); 
    }
    printf("\n");
}

int main() {
    int a = 1; // 0x00000001
    // 将 int 指针强转为 byte_pointer，传入字节长度
    show_bytes((byte_pointer) &a, sizeof(int)); 
    return 0;
}

• start[i]：取出一个字节的数据
  • 含义：start 是一个指向字节（unsigned char）的指针（数组）。[i] 表示“偏移量”。
  • 动作：这表示去内存中找到 start 地址开始，向后数第 i 个位置，取出那里存放的1 个字节的内容。
  • 数值范围：因为是 unsigned char，取出来的值在十进制看是 0 到 255，在十六进制看是 0x00 到 0xFF。
• %占位符开始，仅仅作为标记
• 十六进制 (Hex)。把数值转换成十六进制显示，使用小写字母 (a-f)。这是计算机底层最通用的语言。
• .2 精度/宽度控制。这是最精髓的地方：“至少显示 2 位”。如果数字不够 2 位，在前面补 0。

3. 位级操作

1. 结合表示与操作

1. 集合的位向量表示 (Bit Vector Representation)

• 核心定义：使用宽度为 $w$ 的位向量来表示集合 $\{0, \dots, w-1\}$ 的子集。
• 规则：当第 $j$ 位为 1 时 ($a_j = 1$)，表示元素 $j$ 存在于集合中。
• 索引对应：位索引从右向左依次为 76543210。
• 示例：
  • 01101001 $\rightarrow \{ 0, 3, 5, 6 \}$
  • 01010101 $\rightarrow \{ 0, 2, 4, 6 \}$

2. 集合操作 (Operations)

基于位运算实现集合代数：

位运算符	对应集合操作	运算结果 (二进制)	结果集合
&	交集 (Intersection)	01000001	$\{ 0, 6 \}$
|	并集 (Union)	01111101	$\{ 0, 2, 3, 4, 5, 6 \}$
^	对称差 (Symmetric Difference)	00111100	$\{ 2, 3, 4, 5 \}$
~	补集 (Complement)	10101010	$\{ 1, 3, 5, 7 \}$

2. 位运算符 (&, |, ~, ^)

C语言提供了直接在位级别上进行操作的运算符。

这些运算符将操作数视为位向量，并按位进行计算。

• & (AND): 逐位与
• | (OR): 逐位或
• ~ (NOT): 逐位取反
• ^ (XOR): 逐位异或

示例 (char 类型):

• ~0x41 (01000001₂) -> 0xBE (10111110₂)
• 0x69 | 0x55 -> 01101001₂ | 01010101₂ -> 01111101₂ -> 0x7D

3. 逻辑运算符 (&&, ||, !)

逻辑运算符与之不同，它们将任何非零值视为 True，将零值视为 False，并且结果总是 0 或 1。

示例 (char 类型):

• !0x41 -> !True -> False -> 0x00
• 0x69 && 0x55 -> True && True -> True -> 0x01

4. 移位运算 (<<, >>)

• 左移 x << y: 将 x 的位向左移动 y 位，右侧补0。
• 右移 x >> y: 将 x 的位向右移动 y 位。
  • 逻辑右移: 左侧补0。对无符号数 (unsigned) 必须使用逻辑右移。
  • 算术右移: 左侧用最高有效位 (符号位) 填充。几乎所有机器都对有符号数使用算术右移，这能保证负数在除以2的幂时结果正确。

注意：移位量小于0或大于等于字长是未定义行为。

---

5. 整数表示

1. 无符号整数 (Unsigned)

• 表示: $B2U(X) = \sum_{i=0}^{w-1} x_i \cdot 2^i$
• 范围: 对于一个 $w$ 位的整数，范围是 $[0, 2^w - 1]$。

2. 有符号整数 (Signed) - 二进制补码 (Two’s Complement)

• 表示: $B2T(X) = -x_{w-1} 2^{w-1} + \sum_{i=0}^{w-2} x_i 2^i$
• 最高有效位 $x_{w-1}$ 是符号位，0 代表非负数，1 代表负数。
• 范围: 对于一个 w 位的整数，范围是 $[-2^{w-1}, 2^{w-1} - 1]$。这是一个不对称的范围，负数的表示范围比正数多一个。

w (Bits)	UMax (Unsigned Max)	TMin (Signed Min)	TMax (Signed Max)
8	255	-128	127
16	65,535	-32,768	32,767
32	4,294,967,295	-2,147,483,648	2,147,483,647

![[Course-Notes/Computer-Organization/Slides/02-bits-ints.pdf#page=42&rect=24,17,699,499|02-bits-ints, p.42|500]]

3. 整数和它的相反数

对于一个补码表示的整数 $X$，其相反数 $-X$ 可以通过 ~X + 1 计算得到。对于TMin计算相反数有~TMin+1仍然为TMin。

---

6. 类型转换与扩展

1. 有符号与无符号整数的转换

在C语言中，对有符号和无符号数进行强制类型转换时，底层的位模式保持不变，改变的只是对这些位的解释方式。

• 潜在问题：当一个表达式中同时包含 signed 和 unsigned 类型的变量时，C语言会隐式地将有符号数转换为无符号数再进行比较或运算。

(1) -2147483647-1 == 2147483648U T
(2) 2147483647 > (int) 2147483648U T
(3) -1 < 0U F

示例:

• -1 < 0U 的结果是 False。因为 -1 被转换为 UMax (一个很大的正数)，所以 UMax < 0 不成立。
• 2147483647 > (int)2147483648U 的结果是 True。因为 2147483648U (即 TMax + 1) 转换为 int 后，其位模式被解释为 TMin (-2147483648)，所以 TMax > TMin 成立。

2. 扩展与截断

• 扩展 (Expanding): 从一个较小的数据类型转换为一个较大的数据类型（如 short -> int）。
  • 无符号数: 高位补0 (零扩展)。
  • 有符号数: 高位用符号位填充 (符号扩展)。
• 截断 (Truncating): 从一个较大的数据类型转换为一个较小的数据类型。直接丢弃高位。数值可能会发生巨大变化。
  • 对于有符号整数而言是模运算。

当把一个数扩展一位（从 $w$ 位变成 $w+1$ 位）时，你把原来的符号位复制到了新的最高位。

• 原来的符号位（现在变成了次高位）：权重从 负 变成了 正。即 $-2^{w-1}$ 变成了 $+2^{w-1}$。
• 新的符号位（复制过来的）：拥有了新的 负 权重 $-2^w$。

数值保持不变，因为：

$$\underbrace{-2^w}_{\text{新符号位权重}} + \underbrace{2^{w-1}}_{\text{旧符号位(现为正)}} = \underbrace{-2^{w-1}}_{\text{原符号位权重}}$$

• 类似的可以说明：为什么对有符号数进行位运算是乘除。

---

7. 整数运算

1. 加法

• 加法的实现是位级的，直接对对应位进行加法，并处理进位。使用异或（XOR）和与（AND）操作来实现。
  • 对应两种位运算：
    • 本位和（Sum without Carry） $\rightarrow$ 异或 (^ XOR)
    • 进位（Carry） $\rightarrow$ 与 (& AND) + 左移 (<<)
  • 加法运算逻辑上是串行的，但现代硬件把它做成了并行的。现代计算机（x86, ARM）无法忍受这种等待，于是设计了超前进位加法器 (Carry Lookahead Adder, CLA)。
• 减法的实现是通过补码转换成加法来完成的，即 x - y 等价于 x + (~y + 1)。
• 无符号加法: 结果是对 $2^w$ 取模的。如果真实和 u+v 大于等于 $2^w$，就会发生溢出 (Overflow)，实际结果是 u+v - 2^w。这是一种模运算。
• 有符号加法 (补码加法): 位级行为与无符号加法完全相同。 溢出分为两种情况：
  • 正溢出 (Positive Overflow): 两个正数相加，结果大于 TMax，变成了一个负数。
  • 负溢出 (Negative Overflow): 两个负数相加，结果小于 TMin，变成了一个正数。

在 C 语言或其他底层开发中，不能用 if (a + b > TMax) 来判断，因为 a+b 在计算时就已经溢出（截断）了，比较结果是失效的。

// 假设 x 和 y 都是 int 类型
int sum = x + y;

// 获取符号位 (这里简化概念，实际代码可以直接比较 < 0)
int x_sign = x < 0; 
int y_sign = y < 0;
int sum_sign = sum < 0;

// 核心判断逻辑
int overflow = (x_sign == y_sign) && (x_sign != sum_sign);

// 假设计算 result = x - y;

int x_sign = x < 0;
int y_sign = y < 0;
int res_sign = result < 0;

// 逻辑：(X与Y符号不同) 并且 (结果符号与X不同)
int overflow = (x_sign != y_sign) && (res_sign != x_sign);

![[Course-Notes/Computer-Organization/Slides/02-bits-ints.pdf#page=63&rect=13,40,693,499|02-bits-ints, p.63|725]]

2. 乘法

C语言中的整数乘法会丢弃高 w 位，其实质也是一种模运算。

• 乘以2的幂: 可以通过左移 << 来实现，这比直接使用乘法指令效率更高。 u << k 等价于 $u \times 2^k$。
• 通用乘法是通过 左移和加法 的算法实现的。模拟我们手算乘法的过程（二进制版）。对于 a * b，检查 b 的每一位：
  1. 如果 b 的当前位是 1，则将 a 左移相应位数后，加到最终结果上。
  2. 如果 b 的当前位是 0，则什么都不做。

传统的“逐位移位累加”算法过于缓慢，现代计算机主要从软硬件两个层面进行优化。

1. 编译器优化：强度削减 (针对常数乘法)
   编译器会自动选择计算步数（代价）最少的方式，将乘法转化为移位和加减法。

• 方案 A：移位 + 加法 (Run of 1s)

  • 原理：直接分解二进制中的 1。
  • 示例 (x * 14, 1110): $(x \ll 3) + (x \ll 2) + (x \ll 1)$
  • 代价：2 次加法，3 次移位。

• 方案 B：移位 + 减法 (Booth’s Algorithm 思想)

  • 原理：利用连续的 1 序列，将其视为 $2^{n+1} - 2^m$ (即 $14 = 16 - 2$)。
  • 示例 (x * 14): $(x \ll 4) - (x \ll 1)$
  • 代价：1 次减法，2 次移位 (效率更高)。

2. 硬件优化：并行电路 (针对变量乘法)
   现代 CPU 使用 华莱士树 (Wallace Tree) 或 Dadda Tree 结构，极大地提高了并行度。

   1. 并行生成部分积：利用逻辑门电路，瞬间并行生成所有位的部分积。
   2. 树状压缩：不再逐行累加，而是使用保留进位加法器 (Carry Save Adder) 并行地将几十行部分积“压缩”成 2 行。
   3. 最终相加：当只剩下最后两行时，使用普通加法器求和。

• 在现代 CPU (如 Intel Core 或 AMD Ryzen) 中，整数乘法通常只需要 3 到 4 个时钟周期，而不是 64 个周期。

3. 除以2的幂

• 无符号除法: 使用逻辑右移 >>。u >> k 等价于 $\lfloor u / 2^k \rfloor$。
• 有符号除法: 使用算术右移 >>。
  • 实现原理：模拟手算长除法。这是一个迭代的过程，不断地用除数去减被除数（或其一部分），并根据能否成功相减来确定商的每一位是1还是0。这通常被称为移位和减法算法。
  • 对于正数，x >> k 等价于 $\lfloor x / 2^k \rfloor$，结果正确。
  • 对于负数，x >> k 会向负无穷舍入（例如，-2.5 -> -3），而C语言要求向零舍入（-2.5 -> -2）。
  • 修正方法: 为了得到正确的结果，可以在移位前加入一个偏置 (bias)。对于负数 x，计算 (x + (1<<k) - 1) >> k。

在整数算术中，有一个非常著名的恒等式，用于将“向上取整”转化为“向下取整”：

$$\lceil \frac{x}{y} \rceil = \lfloor \frac{x + y - 1}{y} \rfloor$$

现在把数学公式对应回计算机的位运算：

1. 除数 $y$：在位运算中是 $2^k$，即 1 << k。
2. 偏置量 $y - 1$：即 $2^k - 1$，在位运算中写为 (1 << k) - 1。
3. 除法 $\lfloor \dots / y \rfloor$：即右移 >> k。

所以有(x + (1 << k) - 1) >> k

类型	例子	对应的位操作	复杂度	关键点
无符号整数 (unsigned)	u / 4	逻辑右移 (>> 2)	✅ 简单	左边补 0，直接移位结果就是对的。
有符号正数 (int > 0)	7 / 2	算术右移 (>> 1)	✅ 简单	左边补符号位(0)，结果也是对的。
有符号负数 (int < 0)	-7 / 2	偏置 + 算术右移	❌ 复杂	直接右移会得到 -4 (向下取整)，但 C 语言要求结果是 -3 (向零取整)。 必须先加偏置 (Bias) 再移位。

对于像 x / 3, x / 10 这样的除法，现代编译器通常不使用昂贵的除法指令 (div/idiv)，而是将其优化为 “乘法 + 移位”。

1. 核心原理：乘以倒数 (Multiply by Reciprocal)
   基本思想是将除法 $x / K$ 转换为乘法 $x \times \frac{1}{K}$。

   • 问题：整数算术无法直接表示小数 $\frac{1}{K}$。
   • 方案：将 $\frac{1}{K}$ 放大 $2^n$ 倍，近似为一个整数 $M$ (Magic Number)。

     $$M \approx \frac{2^n}{K} \implies \frac{1}{K} \approx \frac{M}{2^n}$$

   • 最终公式：

     $$x / K \approx (x \cdot M) \gg n$$

2. 实现步骤

   1. 预计算 Magic Number ($M$): 编译器会在编译阶段算出这个特殊的整数（例如除以 3 的 magic number 可能是 0xAAAAAAAB）。
   2. 执行乘法 (Multiply): 计算 x * M。通常利用 CPU 的 mul 指令获取 64 位乘积的高 32 位 (相当于先乘 $M$ 再除以 $2^{32}$)。
   3. 算术右移 (Shift): 对结果进行移位，修正剩余的比例因子。
   4. 符号修正 (Signed Adjustment): 如果是有符号数，最后通常还需要根据符号位调整（例如加 1），类似于除以 2 的幂时的偏置处理。

3. 识别特征
   当你在汇编代码中看到 “乘以一个奇怪的大整数”（如 imul ... $1431655766），紧接着是 移位操作，这通常就是在做除以常数的除法。

(1) (x&7) != 7 || (x << 29 < 0)

• 结果：1 (True)
• 证明：
  1. 情况一：(x & 7) != 7 为真。如果 x 的最低 3 位不全是 1，那么第一部分为真。由于短路求值，整个表达式结果为 1。
  2. 情况二：(x & 7) != 7 为假。这意味着 (x & 7) == 7。换句话说，x 的二进制表示的最低 3 位全是 1（即形式为 …111）。x << 29 的结果是一个负数，表达式 x << 29 < 0 成立（为真）。

(2) x * x >= 0

• 结果：0 (False)

• 反例：整数溢出

  在 32 位补码算术中，两个正数相乘可能会发生正溢出，导致结果变成负数；或者运算结果截断后符号位为 1。

  • 反例取值：取 $x = 65535$ (即十六进制 0xFFFF)。
  • 计算过程 $x^2 = (2^{16} - 1)^2 = 2^{32} - 2^{17} + 1 > 2^{31} -1$ 并且$x^2 < 2^{32}$
    在 32 位系统中，$2^{32}$ 会被截断丢弃，剩下的部分是 $-2^{17} + 1$。

(3) x > 0 || -x >= 0

• 结果：0 (False)
• 反例：最小负数 TMin，TMin 的相反数还是 TMin 自己。

x < 0 || -x <= 0 的结果对于所有整数（包括 TMin）恒为 1 (True)。