Skip to content

Chapter 02 Representing and Manipulating Information

2.1 信息存储

2.1.1 十六进制表示法

  • 一个字节 (byte) 由 8 位组成.
  • 二进制: \(00000000_2\) 到 \(11111111_2\)
  • 十进制: \(0_{10}\) 到 \(255_{10}\)
  • 十六进制: \(00_{16}\) 到 \(FF_{16}\). 使用 '0x' 或 '0X' 开头.
  • 转换技巧: 记住 A(10), C(12), F(15).
  • \(x = 2^n\), hex 格式为 \(1\) 后面跟 \(n/4\) 个 \(0\).

2.1.2 字数据大小

  • 字长 (word size): 指明指针数据的标称大小 (nominal size).
  • 32 位机器: 虚拟地址空间 \(4GB\).
  • 64 位机器: 虚拟地址空间 \(16EB\) (目前实际只用 48 位).
  • C 语言数据类型大小 (64位机器):
  • char: 1 字节
  • short: 2 字节
  • int: 4 字节
  • long: 8 字节
  • float: 4 字节
  • double: 8 字节
  • char *: 8 字节

2.1.3 寻址和字节顺序

  • 大端法 (Big Endian): 最高有效字节在最前面的方式. (IBM, Internet)
  • 小端法 (Little Endian): 最低有效字节在最前面的方式. (Intel, Android, iOS)
  • 例子: 变量 x 类型为 int, 值为 0x01234567, 地址 0x100.
  • Big Endian: 0x100: 01, 0x101: 23, ...
  • Little Endian: 0x100: 67, 0x101: 45, ...

字节顺序的影响

  1. 网络传输: 需要在主机字节序和网络字节序之间转换.
  2. 反汇编: 阅读机器级代码字节序列时需注意 (通常是逆序显示).
  3. 类型双关 (Type Punning): 使用 union 或强制类型转换访问不同字节时结果不同.

2.1.4 字符串表示

  • C 语言字符串以 null 字符 (\0, 值为 0) 结尾.
  • 文本数据比二进制数据具有更强的平台独立性.

2.1.5 代码表示

  • 二进制代码在不同操作系统和机器上是不兼容的.

2.1.6 布尔代数

  • NOT (~), AND (&), OR (|), XOR (^).
  • 位向量 (Bit Vector): 表示有限集合. [01101001] 表示集合 \(\{0, 3, 5, 6\}\).

2.1.7 C 语言中的位级运算

  • |, &, ~, ^.
  • 这里的运算是对参数的每一位进行的.
  • 掩码 (Masking): x & 0xFF 提取最低字节.

2.1.8 C 语言中的逻辑运算

  • ||, &&, !.
  • 逻辑运算认为所有非零参数都为 TRUE, 0 为 FALSE.
  • 短路求值: 如果第一个参数能确定结果, 就不会计算第二个参数.
  • 区别: & 是位级运算，&& 是逻辑运算。例如 !0x41 是 0x00, ~0x41 是 0xBE.

2.1.9 C 语言中的移位运算

  • 左移 <<: \(x << k\) 丢弃最高的 \(k\) 位, 右端补 \(k\) 个 0.
  • 右移 >>:
  • 逻辑右移: 左端补 \(k\) 个 0. (无符号数)
  • 算术右移: 左端补 \(k\) 个最高有效位的值. (有符号数)
  • 注意: 移位量 \(k\) 如果很大 (\(k \ge w\)), 实际移位量是 \(k \mod w\). (C 标准称其为未定义行为，但 x86 机器指令如 sal 会执行取模操作).

2.2 整数表示

2.2.1 整数数据类型

  • 负数的范围比正数大 1 (因为 0 归在非负数里).

2.2.2 无符号数的编码

  • \(B2U_w(\vec{x}) = \sum_{i=0}^{w-1} x_i 2^i\)
  • 范围: \([0, 2^w - 1]\).
  • 唯一性: 双射.

2.2.3 补码编码 (Two's Complement)

  • 最常见的有符号数表示. 最高位 \(x_{w-1}\) 是符号位, 权重为 \(-2^{w-1}\).
  • \(B2T_w(\vec{x}) = -x_{w-1} 2^{w-1} + \sum_{i=0}^{w-2} x_i 2^i\)
  • 范围: \([-2^{w-1}, 2^{w-1} - 1]\).
  • TMin (10...0) = \(-2^{w-1}\).
  • TMax (01...1) = \(2^{w-1} - 1\).
  • |TMin| = |TMax| + 1. (不对称性)
  • -1 的位表示是全 1 (FF...F).

2.2.4 有符号数和无符号数之间的转换

  • C 语言允许强制类型转换.
  • 规则: 位模式不变, 只是解释方式不同.
  • \(T2U_w(x) = x + 2^w\) (if \(x < 0\)), else \(x\).
  • 负数转无符号数会变成很大的正数.

2.2.5 C 语言中的有符号数和无符号数

  • 常数默认是有符号的. 添加 U 后缀表示无符号 (e.g., 12345U).
  • 运算规则: 如果一个运算数是有符号的, 另一个是无符号的, C 语言会隐式地将有符号数强制转换为无符号数来执行运算. 这可能导致非直观的结果.
  • 例子: -1 < 0U 结果为 False。因为 -1 被转换为 UMax (全1)，这比 0 大。

隐式转换陷阱

慎用无符号数, 特别是在循环索引或减法运算中. 比如 i - 1 当 i=0 时如果是无符号数会变成 UMax.

2.2.6 扩展一个数字的位表示

  • 零扩展 (Zero Extension): 无符号数, 开头补 0.
  • 符号扩展 (Sign Extension): 补码数, 开头补符号位.

2.2.7 截断数字

  • 截断 \(w\) 位到 \(k\) 位: 丢弃高 \(w-k\) 位. 相当于 \(x \mod 2^k\).

2.3 整数运算

2.3.1 无符号加法

  • \(x +_w^u y = (x + y) \mod 2^w\).
  • 溢出: 结果变小了.
  • 检测溢出: 如果 \(s = x + y\), 当 \(s < x\) (或 \(s < y\)) 时发生溢出.

2.3.2 补码加法

  • \(x +_w^t y\). 也是位级加法, 截断结果.
  • 正溢出: 两个正数相加得到负数.
  • 负溢出: 两个负数相加得到正数.

2.3.3 补码的非

  • \(-^t_w x\).
  • 除了 TMin 的非是其本身 (TMin), 其他 \(x\) 的非是 \(-x\).
  • 位级技巧: ~x + 1 (按位取反再加 1).

2.3.4 无符号乘法

  • 截断到 \(w\) 位.

2.3.5 补码乘法

  • 无符号和补码的位级乘法结果是一样的 (截断后).

2.3.6 乘以常数

  • 编译器优化: 用移位和加减法代替乘法.
  • \(x * 14 = (x<<3) + (x<<2) + (x<<1)\) 或 \((x<<4) - (x<<1)\).

2.3.7 除以 2 的幂

  • 除法比乘法慢.
  • 无符号: 逻辑右移 >>.
  • 补码: 算术右移 >>.
  • 注意负数除法的舍入: 移位是向下舍入, 整数除法通常是向零舍入.
  • 修正: \((x + (1<<k) - 1) >> k\) (偏置 bias).

2.4 浮点数

2.4.1 二进制小数

  • \(b = \sum_{i=-n}^m b_i 2^i\).
  • 很多小数无法精确表示 (如 0.1, 0.2).

2.4.2 IEEE 浮点表示

  • \(V = (-1)^s \times M \times 2^E\)
  • 符号 (sign) \(s\): 1 位.
  • 阶码 (exponent) \(E\): \(k\) 位.
  • 尾数 (significand) \(M\): \(n\) 位.
  • 两种精度:
  • float: \(s=1, k=8, n=23\) (32 bits). Bias = 127.
  • double: \(s=1, k=11, n=52\) (64 bits). Bias = 1023.

2.4.3 浮点数的三种情况

  1. 规格化值 (Normalized): \(exp \neq 00...0\) 且 \(exp \neq 11...1\).
    • \(E = exp - Bias\). \(Bias = 2^{k-1} - 1\).
    • \(M = 1.frac\). (隐含的 1).
  2. 非规格化值 (Denormalized): \(exp = 00...0\).
    • \(E = 1 - Bias\).
    • \(M = 0.frac\).
    • 用途: 表示 0, 以及非常接近 0 的数 (逐渐下溢).
  3. 特殊值: \(exp = 11...1\).
    • \(frac = 0\): 无穷大 (\(\infty\)). (溢出, 除以 0).
    • \(frac \neq 0\): NaN (Not a Number). (非法运算, 如 \(\sqrt{-1}\)).

2.4.4 舍入

  • 向偶数舍入 (Round to even): 默认模式. 在中间值时, 向最低有效位为偶数的方向舍入. 避免统计偏差.
  • 例子:
  • \(1.4 \to 1\)
  • \(1.6 \to 2\)
  • \(1.5 \to 2\) (中间值，向偶数舍入)
  • \(2.5 \to 2\) (中间值，向偶数舍入)

2.4.5 浮点运算

  • 不满足结合律 (因为舍入). \((3.14 + 1e10) - 1e10 = 0\), 但 \(3.14 + (1e10 - 1e10) = 3.14\).
  • 满足单调性.

2.4.6 C 语言中的浮点数

  • int 转 float: 不会溢出, 但可能被舍入.
  • int / float 转 double: 精确.
  • double 转 float: 可能溢出 (\(+\infty / -\infty\)) 或舍入.
  • float / double 转 int: 向零舍入. 可能溢出.