Lecture 2: 信息的表示与处理——位、字节与整数 (Bits, Bytes, and Integers)

目录 · ← l1 · l3 →

Lecture 2: 信息的表示与处理——位、字节与整数 (Bits, Bytes, and Integers)

讲义对应：CMU 15-213 Lecture 2 — Bits, Bytes, & Integers（素材：F25-02-bits-bytes-ints.txt） 教材对应：CS:APP3e 第 2 章 2.1–2.4（含 2.3 整数运算） 关联 Lab：L1 Data Lab

2.1 概述

第 1 讲把程序的一生压缩成”源文件 → 可执行文件 → 进程”的黑箱；本讲打开这个黑箱最底下的一层：内存里的一切都只是比特。核心问题是：同一串 $w$ 个比特，凭什么既能被解释成无符号整数、又能被解释成补码整数、还能被解释成指令、字符或指针？答案是——比特本身没有类型，类型来自施加于其上的解释规则（编码）。本讲先建立布尔代数与位运算这套”比特的手工工具”，再给出无符号编码 $B2U$ 与二进制补码编码 $B2T$ 两个映射，接着推导类型转换、扩展/截断、加减乘除与移位在位级上究竟发生了什么，最后落到字节序（Byte Ordering）这种”纯粹约定”造成跨平台差异的经典案例。它承接第 1 讲的”信息就是位 + 上下文”，直接为第 3 讲的机器级算术逻辑运算铺路，并且是 L1 Data Lab 的全部理论前提。

2.2 核心概念与底层机制图解

2.2.1 位与字节（Bits and Bytes）

  • 定义与目的：一个位（bit）只有 0/1 两种状态；8 个位组成一个字节（byte）。用二值而不是连续电压，是因为”高到可以算 On、低到可以算 Off”的判据远比”精确测出 0.37V”容易通信、复制与保存。选择 $2^k$ 进制的编码（八进制、十六进制）唯一目的是压缩书写长度且能直接切出位：1 个十六进制数字恰好对应 4 个位。
  • 直观解释：十六进制就像给二进制做的”速记”:0011 1011 0110 1101 写成 3B6D，每个十六进制数字是一组 4 位的”缩写标签”，可以随时无损展开。这也是为什么内存窗口、反汇编列表、gdb 默认都用十六进制。
  • 与机器码/硬件的对应：C 语言里 0x 前缀标记十六进制常量，如 0xFA1D37B 与 0xfa1d37b 等价（大小写不敏感）。编译器在词法分析阶段就把它们折成同一个整数常量，机器码里根本不存在”进制”这个概念。

2.2.2 字节序（Byte Ordering）

  • 定义与目的：多字节数据（int、long）在内存中占连续多个地址，哪一个字节放在最低地址属于纯约定。小端（Little Endian）：最低有效字节（least significant byte, LSB）放在最低地址；大端（Big Endian）：最高有效字节（MSB）放在最低地址。x86 与 ARM（Android/iOS/Linux）是小端；Sun SPARC、PowerPC Mac、以及网络字节序是大端。
  • 直观解释：把数字 0x01234567 想象成一句从左到右书写的句子。大端是”正常书写顺序”，第一个字节就是最重要的数字；小端是”把句子倒着塞进抽屉”，末位数字先出场——但好处是，从同一地址读 1 字节，小端总拿到低 8 位，这条性质让指针类型双关（type punning）变得自然。
  • 底层机制图解（变量 x 为 4 字节，&x == 0x100）：
 地址        小端 (Little Endian)              大端 (Big Endian)
          +--------+                          +--------+
 0x103    |   01   |  <- MSB (最高有效字节)   |   67   |  <- LSB (最低有效字节)
          +--------+                          +--------+
 0x102    |   23   |                          |   45   |
          +--------+                          +--------+
 0x101    |   45   |                          |   23   |
          +--------+                          +--------+
 0x100    |   67   |  <- LSB (最低有效字节)   |   01   |  <- MSB (最高有效字节)
          +--------+                          +--------+
              &x = 0x100 (低地址)                &x = 0x100 (低地址)
  • 与机器码/硬件的对应：字节序只在”数据跨越机器边界”时成为问题——写文件、发网络包、跨架构共享内存。位序不会反转（参考点始终是低位），char 与字符串（字符数组）不受影响，因为每个元素只有 1 字节。反汇编器读到的立即数就是字节反转过的：机器码 81 c3 ab 12 00 00 对应的值要还原成 0x000012ab 再反序得 ab 12 00 00，即 add $0x12ab,%ebx。

2.2.3 布尔代数与 C 的位运算（Boolean Algebra and Bit-Level Operations）

  • 定义与目的：George Boole 用代数刻画逻辑：&（与，两真才真）、\|（或，任一真则真）、~（非）、^（异或，恰有一个真才真）。把运算按位并行地作用到整个位向量（bit vector）上，就得到了机器可在一个时钟周期内完成的”位并行计算”。
  • 直观解释：掩码（mask）就像镂空模板：x & 0xFF 只在低 8 位”有孔”，其余被挡住。更妙的是位向量可以表示集合：第 $j$ 位为 1 表示元素 $j$ 属于该集合，于是 & 是交集、\| 是并集、^ 是对称差、~ 是补集——一次位运算等于一次性完成 32/64 个元素的集合运算。
  • 底层机制图解：
   01101001  (A)          人可读角度:  A = { 0, 3, 5, 6 }
 & 01010101  (B)                       B = { 0, 2, 4, 6 }
 ----------
   01000001  = 0x41      交集 (Intersection)  A ∩ B = { 0, 6 }

   01101001 | 01010101 = 01111101 = 0x7D   并集 A ∪ B = {0,2,3,4,5,6}
   01101001 ^ 01010101 = 00111100 = 0x3C   对称差 A △ B = {2,3,4,5}
   ~ 01010101          = 10101010 = 0xAA   补集 ~B = {1,3,5,7}
  • 与机器码/硬件的对应：& \| ~ ^ 可用于任何整型（long, int, short, char, unsigned），实参一律视作位向量逐位计算。char 场景的经典结论：~0x41 → 0xBE、~0x00 → 0xFF、0x69 & 0x55 → 0x41、0x69 \| 0x55 → 0x7D。硬件上由 ALU 的一组并行门电路完成，没有分支、没有进位链，因此常数时间。

2.2.4 逻辑运算与位运算的区别（Logic vs. Bit-Level）

  • 定义与目的：&& \|\| ! 是逻辑运算：0 视为 False、任何非零视为 True，结果永远是 0 或 1，并且有短路求值（early termination）。& \| ~ ^ 是位运算，结果保留每一位。
  • 直观解释：这是 C 语言最经典的坑：if (x & y) 与 if (x && y) 在 x=1, y=2 时前者为 0（假）、后者为 1（真）。更要命的是 p && *p —— 它先判断指针非空再解引用，避免了空指针访问；写成 p & *p 则一定会解引用 NULL。
  • 与机器码/硬件的对应：!x 编译成 testl %edi,%edi; sete %al（测试并置标志），结果被规范化到 0/1；x & y 编译成 andl，结果保留原始宽度。短路求值会产生真实的分支（或 cmov），因此逻辑运算存在控制依赖，位运算没有。

2.2.5 移位运算（Shift Operations）

  • 定义与目的：x << y 左移，左边溢出的位丢弃、右边补 0。右移 x >> y 丢弃低位，补高位有两种：逻辑右移（logical shift）补 0，算术右移（arithmetic shift）复制最高位（符号位）。移位量 $y < 0$ 或 $y \ge$ 字长是未定义行为（UB）。
  • 直观解释：左移就是”数字整体往高位搬家”，每搬一位相当于乘 2；算术右移是”带着符号整体往低位搬家”，等价于向下取整的除以 2 的幂。
  • 底层机制图解：
 x = 01100010                   x = 10100010
 x << 3        = 00010000       x << 3        = 00010000   (左移一致，溢出位丢弃)
 Log.  x >> 2  = 00011000       Log.  x >> 2  = 00101000   (补 0: 负数被"看成大正数")
 Arith.x >> 2  = 00011000       Arith.x >> 2  = 11101000   (补符号位: 保持负号)
  • 与机器码/硬件的对应：C 标准规定：有符号负数的右移是”实现定义（implementation-defined）”，不是严格的 UB——GCC/Clang 在 x86-64 上选择算术右移，Java 则把两种都给你：>> 是算术右移，>>> 是无符号（逻辑）右移。x86-64 的 shrl 是逻辑右移、sarl 是算术右移、shll/sall 是左移（两者等价）；移位量放在 %cl 寄存器中。

2.2.6 无符号编码与二进制补码编码（Unsigned & Two’s Complement）

  • 定义与目的：$w$ 位位向量 $\vec{x}$ 的两种解释：
\[B2U_w(\vec{x}) = \sum_{i=0}^{w-1} x_i 2^i \qquad 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}$，其余完全一致。最高位因此被叫符号位：0 表示非负，1 表示负。

  • 直观解释：为什么不用”符号 + 数值”（sign-magnitude）？因为那样会出现 -0，且 1 + (-1) 无法用普通加法得到 0。补码是”魔法”：取 001，希望加某个数得 000（丢弃进位），试验发现 111 正好满足 001 + 111 = 1 000 = 000，于是 111 就是 -1。求 $-x$ 的捷径由此而来：$ -x = \sim x + 1 $（按位取反再加 1）。道理是 $x + \sim x = 111\ldots1 = -1$，两边加 1 并回绕即得。
  • 底层机制图解（$w = 3$ 时两条数轴叠放在同一串位模式上）：
   位模式:    000     001     010     011     100     101     110     111
              |       |       |       |       |       |       |       |
   B2U 值:     0       1       2       3       4       5       6       7
              |       |       |       |       |       |       |       |
   B2T 值:     0       1       2       3      -4      -3      -2      -1
              +-------+-------+-------+       +-------+-------+-------+
              非负区 (符号位 0)                 负区 (符号位 1)
                                              ^
                                   TMin = -4 比 TMax = 3 多一个"没有正伴侣"的位置
  • 与机器码/硬件的对应：$w = 16$ 时 15213 是 3B 6D（00111011 01101101），-15213 是 C4 93（11000100 10010011）。取值范围：$UMin = 0$、$UMax = 2^w - 1$、$TMin = -2^{w-1}$、$TMax = 2^{w-1} - 1$。$w = 32$：unsigned 为 $[0, 4294967295]$，int 为 $[-2147483648, 2147483647]$；$w = 64$：unsigned long 为 $[0, 18446744073709551615]$，long 为 $[-9223372036854775808, 9223372036854775807]$。C 标准并未强制要求补码，但”几乎所有机器都是”，本课程一律按补码讨论。注意 $TMin$ 是不对称的：$\vert TMin\vert = TMax + 1$。

2.2.7 有符号↔无符号转换（T2U / U2T）

  • 定义与目的：转换是位模式不变、解释改变。$T2U_w(x) = x + 2^w$（当 $x < 0$），$U2T_w(u) = u - 2^w$（当 $u \ge 2^{w-1}$）。C 中显式强制转换（cast）与赋值、函数传参引发的隐式转换规则完全相同。
  • 直观解释：把补码数轴”从 $TMin$ 处剪断、上半段整体挪到 $UMax$ 之后”，就得到无符号数轴——这就是顺序反转（ordering inversion）：负数变成极大的正数。
  • 底层机制图解：
   补码范围                             无符号范围
     TMax = 2^(w-1)-1  <--- 一一对应 --->  TMax
       ...                                      ...
      -1  = 111...1     --- 加 2^w --->  UMax   = 2^w - 1
      -2  = 111...0     --- 加 2^w --->  UMax-1
       ...                                      ...
     TMin = 100...0     --- 加 2^w --->  2^(w-1)
  • 与机器码/硬件的对应：转换不产生任何指令（寄存器里的位原封不动），只影响后续指令的选择——有符号比较用 cmp + 有/无符号条件跳转（jl vs jb），除法用 idiv vs div。因此它是最”免费”、也最容易咬人的机制：-1 转 unsigned 得 UINT_MAX（4294967295）；混合表达式中 int 被隐式转成 unsigned，包括比较运算 < > == <= >=。于是 -1 > 0U 为真，因为 -1 先变成 4294967295。

2.2.8 扩展与截断（Expanding & Truncating）

  • 定义与目的：扩展（如 short int → int）：无符号补 0，有符号做符号扩展（sign extension）——复制 $k$ 份最高位。截断（如 unsigned → unsigned short）：直接丢弃高 $k$ 位，结果被重新解释：无符号等价于取模 $2^w$，有符号类似取模。
  • 直观解释：符号扩展就像把一个人的”姓氏”抄到最后——负数的高位填 1，数值不变；截断像把长号码掐掉前几位，位数不够就会”变号”。
  • 与机器码/硬件的对应：movswl（带符号扩展短→长）、movzbl（零扩展字节→长）就是这两条规则对应的指令。截断则由写窄寄存器隐式完成（如 movb）。

2.2.9 整数运算：加法、乘法与除法的位级真相

  • 无符号加法：硬件就是标准加法器、丢弃进位输出，因此实现 $s = (u + v) \bmod 2^w$，溢出时回绕（wrap around），且至多回绕一次。
  • 补码加法：与无符号加法位级行为完全相同，只是解释不同：int s = (int)((unsigned)u + (unsigned)v) 与 s = u + v 结果一致。回绕方向不同：真和 $\ge 2^{w-1}$ 变负（正溢出），$< -2^{w-1}$ 变正（负溢出）。有符号溢出是 UB，编译器有权假设它不发生。
  • 乘法：$w$ 位乘积取低 $w$ 位，精确值最多 $2w$ 位。向左移 $k$ 位等于乘 $2^k$：u << 3 == u * 8，(u << 5) - (u << 3) == u * 24——编译器自动生成移位加/减代码，因为移位加比乘法快。
  • 除以 2 的幂：无符号用逻辑右移，u >> k 就是 $\lfloor u / 2^k \rfloor$；有符号用算术右移，但它向下取整（round down）而非向零取整，会给负商引入偏置：-15213 >> 1 = -7607，而 -15213 / 2 = -7606。要得到 C 的向零取整语义必须加偏置：$(x + 2^k - 1) \gg k$，即 (x + (1<<k) - 1) >> k；若 $x$ 已能被整除，偏置不产生效果（低 $k$ 位全 0，加 $2^k-1$ 不会进位）。
  • 与机器码/硬件的对应：addl（丢弃进位）、imull（取低 32 位）、sarl/shrl（有/无符号右移）、leal (%rdi,%rdi,2), %eax（一条 LEA 完成乘以 3）——见 2.3 节的真实汇编。

2.3 代码示例与底层机制分析

2.3.1 show_bytes 逐字节打印与字节序判定

代码 (C)：

/* /tmp/c02_byteorder.c  编译: gcc -g -Wall -std=c11 c02_byteorder.c -o c02_byteorder */
#include <stdio.h>
#include <string.h>

typedef unsigned char *byte_pointer;

/* 从 start 开始，按内存地址递增顺序逐字节打印 len 个字节 */
void show_bytes(byte_pointer start, size_t len)
{
    size_t i;
    for (i = 0; i < len; i++)
        printf(" %.2x", start[i]);   /* 必须以无符号十六进制打印 */
    printf("\n");
}

void show_int(int x)      { printf("int      %11d :", x); show_bytes((byte_pointer) &x, sizeof(int)); }
void show_long(long x)    { printf("long     %11ld :", x); show_bytes((byte_pointer) &x, sizeof(long)); }
void show_pointer(void *x){ printf("pointer  %11p :", x); show_bytes((byte_pointer) &x, sizeof(void *)); }
void show_short(short x)  { printf("short    %11d :", x); show_bytes((byte_pointer) &x, sizeof(short)); }

int main(void)
{
    int  ival = 0x01234567;           /* 讲义用的是 15213 = 0x3B6D */
    long lval = 0x0123456789abcdefL;
    short sval = 15213;
    int  x = 15213;

    printf("sizeof(long) = %zu, sizeof(void*) = %zu\n\n", sizeof(long), sizeof(void *));
    printf("== 字节序: int ival = 0x%08x ==\n", ival);
    show_int(ival);
    printf("== 讲义示例: short 15213 ==\n");
    show_short(sval);
    show_int(x);                       /* 符号扩展成 4 字节 */
    show_int(-x);                      /* 负数: 补码 */
    printf("== long ival = 0x%016lx ==\n", (unsigned long) lval);
    show_long(lval);
    printf("== char 数组: 完全不受字节序影响 ==\n");
    char *s = "15213";
    printf("string   %11s :", s);
    show_bytes((byte_pointer) s, strlen(s));
    show_pointer((void *) s);

    /* 显式判断运行时字节序 */
    unsigned int probe = 1;
    unsigned char first = *(unsigned char *) &probe;
    printf("\n*(char*)&1 == %u  ->  %s endian\n", (unsigned) first, first ? "little" : "big");
    return 0;
}

【代码做什么？】

  1. byte_pointer 是 unsigned char *。C 标准保证 char 恰好 1 字节，且可以用字符指针逐字节检查任意对象的表示，所以它是内存的”显微镜”。
  2. show_bytes 从低地址向高地址遍历，%.2x 保证每字节两位十六进制、高位补 0——若用 %x 打印 0x01 会变成 1，输出就错位了。
  3. show_int(ival) 打印 ival 的 4 个字节，顺序直接暴露本机字节序。
  4. 最后用 *(unsigned char*)&probe 在运行时判定：小端机读到的第一个字节是 1。

【底层机制透视】 取地址 &x 得到的是对象最低地址，函数并不知道字节序，它只是机械地递增地址。所以 show_bytes 的输出顺序就是”机器把数字写进内存的顺序”。sizeof(long) == 8 说明这是 LP64（x86-64）模型，与教材一致。

【实测验证】（本机 gcc 12.2.0, x86-64 Linux）：

sizeof(long) = 8, sizeof(void*) = 8
== 字节序: int ival = 0x01234567 ==
int         19088743 : 67 45 23 01          <- 小端: LSB 在低地址
== 讲义示例: short 15213 ==
short          15213 : 6d 3b
int            15213 : 6d 3b 00 00          <- 正数符号扩展 = 补 0
int           -15213 : 93 c4 ff ff          <- 负数符号扩展 = 补 1
== long ival = 0x0123456789abcdef ==
long     81985529216486895 : ef cd ab 89 67 45 23 01
== char 数组: 完全不受字节序影响 ==
string         15213 : 31 35 32 31 33      <- 字符按书写顺序排列
pointer     0x4021xx : xx 21 40 00 00 00 00 00  <- 低位字节随 ASLR/链接布局而变
*(char*)&1 == 1  ->  little endian

3B 6D 与 C4 93 与讲义表格完全吻合；-15213 的 4 字节 93 c4 ff ff 正是 C4 93 符号扩展的结果。

2.3.2 有符号/无符号转换与数值范围陷阱

代码 (C)：

/* /tmp/c02_cast_traps.c  编译: gcc -g -Wall -std=c11 c02_cast_traps.c -o c02_cast_traps */
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

static unsigned count_down_iterations(unsigned n, unsigned cap)
{
    unsigned cnt = 0;
    for (unsigned i = n - 1; i >= 0; i--) {   /* i >= 0 恒为真！ */
        cnt++;
        if (cnt == cap) break;                /* 仅为了能在演示中停下来 */
    }
    return cnt;
}

int main(void)
{
    /* ---------- 1. 位模式不变、解释改变 ---------- */
    int      tx = -1;
    unsigned ux = (unsigned) tx;              /* T2U: 减 2^32 */
    printf("(unsigned)(-1)              = %u   (UINT_MAX = %u)\n", ux, UINT_MAX);
    printf("(unsigned)(-1) > 0          = %d\n", ux > 0);
    printf("(int) 2147483648U           = %d   (INT_MIN)\n", (int) 2147483648U);
    printf("2147483647U > -2147483647-1 = %d  (混合运算: 右边被转成 unsigned)\n",
           2147483647U > -2147483647 - 1 ? 1 : 0);
    printf("2147483647U < (int)2147483648U = %d  (显式转回 int 才按有符号比较)\n",
           2147483647U < (int) 2147483648U ? 1 : 0);

    /* ---------- 2. 混合表达式的隐式转换 ---------- */
    {
        int      a = -1;                      /* 0xFFFFFFFF */
        unsigned b = 0;                       /* 0x00000000 */
        /* 下面这行里 a 被隐式转换为 unsigned，-1 变成 4294967295，于是条件为真 */
        if (a > b) printf("混用: if (-1 > 0U) 判定为【真】（因为 -1 被转成 %u）\n",
                          (unsigned) a);
        else       printf("混用: if (-1 > 0U) 判定为假\n");
    }

    /* ---------- 3. 数值范围陷阱（UB！） ---------- */
    puts("\n-- 以下两行涉及未定义行为 (UB)，结果依编译器/优化级别而异 --");
    volatile int tmin = INT_MIN;
    int nabs = abs(tmin);                     /* UB: abs(INT_MIN) 不可表示 */
    int nneg = -tmin;                         /* UB: -INT_MIN 溢出 */
    printf("abs(INT_MIN) = %d   (仍是负数! 期望 2147483648 无法表示)\n", nabs);
    printf("-INT_MIN     = %d   (回绕成 INT_MIN 本身)\n", nneg);
    printf("INT_MIN == -INT_MIN ? %d\n", tmin == -tmin ? 1 : 0);

    /* ---------- 4. 无符号倒计数死循环 ---------- */
    unsigned iters = count_down_iterations(3, 6);
    printf("\n无符号倒计数 n=3，上限 6 步内观察到 %u 次迭代: ", iters);
    printf("i 取值序列 2,1,0,4294967295,4294967294,... 永不小于 0\n");

    /* ---------- 5. 正确写法：用 int 或改成 i > 0 形式 ---------- */
    int sum = 0;
    for (int i = 2; i >= 0; i--) sum += i;
    printf("改用 int 倒计数: sum = %d\n", sum);

    /* ---------- 6. 无符号减法的回绕 ---------- */
    unsigned u1 = 0, u2 = 1;
    printf("0U - 1U = %u  (模 2^32 回绕)\n", u1 - u2);
    return 0;
}

【代码做什么？】

  1. (unsigned)(-1) 把位模式 0xFFFFFFFF 按无符号解释，得 UINT_MAX，因此 (unsigned)(-1) > 0 为 1。
  2. (int) 2147483648U 反向操作，得 INT_MIN。
  3. 2147483647U > -2147483647-1 中右侧 int 被隐式转成 unsigned（变成 2147483648U），于是 2147483647U < 2147483648U，比较结果为 0。这正是讲义表中 “unsigned → >” 的那一行。
  4. abs(INT_MIN) 与 -INT_MIN 都是 UB：INT_MIN = -2147483648，其相反数 +2147483648 在 int 中不可表示。
  5. 无符号倒计数 for (unsigned i = n-1; i >= 0; i--)：i >= 0 永真，循环永不结束；程序中加了 cap 才停得下来。

【底层机制透视】 测试 a > b 时，编译器看到 int 与 unsigned 混合，按 C 的寻常算术转换（usual arithmetic conversions）把 int 提升为 unsigned，再发出无符号比较（cmpl + jbe 一类），因此负数的”极大正值”解释获胜。而 UB 的本质是：编译器可以假设有符号溢出永不发生，于是把 x + 1 > x 直接优化为”恒真”，abs(INT_MIN) 也可能被折叠成任意值。UB 不是”结果随机”，而是”编译器的任何行为都合法”。

【实测验证】：

(unsigned)(-1)              = 4294967295   (UINT_MAX = 4294967295)
(unsigned)(-1) > 0          = 1
(int) 2147483648U           = -2147483648   (INT_MIN)
2147483647U > -2147483647-1 = 0  (混合运算: 右边被转成 unsigned)
2147483647U < (int)2147483648U = 1  (显式转回 int 才按有符号比较)
混用: if (-1 > 0U) 判定为【真】（因为 -1 被转成 4294967295）

-- 以下两行涉及未定义行为 (UB)，结果依编译器/优化级别而异 --
abs(INT_MIN) = -2147483648   (仍是负数! 期望 2147483648 无法表示)
-INT_MIN     = -2147483648   (回绕成 INT_MIN 本身)
INT_MIN == -INT_MIN ? 1

无符号倒计数 n=3，上限 6 步内观察到 6 次迭代: i 取值序列 2,1,0,4294967295,4294967294,... 永不小于 0
改用 int 倒计数: sum = 3
0U - 1U = 4294967295  (模 2^32 回绕)

⚠️ 注意：abs(INT_MIN)、-INT_MIN 的”回绕成 INT_MIN”只是当前 GCC 12.2.0 在本机的实际行为，属于 UB，换编译器或开 -O2 可能得到完全不同的结果（例如循环被优化成死循环）。

2.3.3 整数运算、移位与 Data Lab 位级技巧

代码 (C)：

/* /tmp/c02_arith_bits.c  编译: gcc -g -Wall -std=c11 c02_arith_bits.c -o c02_arith_bits */
#include <stdio.h>
#include <limits.h>

/* ---------- Data Lab 风格：只允许 ! ~ & ^ | + << >>，禁止条件与循环 ---------- */
int dl_negate(int x)      { return ~x + 1; }                              /* -x  */
int dl_bitAnd(int x, int y){ return ~(~x | ~y); }                         /* x & y，De Morgan */
int dl_isEqual(int x, int y){ return !(x ^ y); }                          /* x == y */
int dl_logicalNeg(int x)  { return ((x | (~x + 1)) >> 31) + 1; }          /* !x */
int dl_sign(int x)        { return (x >> 31) | (!!x); }                   /* -1 / 0 / 1 */
int dl_isPowerOf2(int x)  { return !(x & (x + ~0)) & !(x >> 31) & !!x; }  /* x > 0 且是 2 的幂 */

/* ---------- 溢出检测（教材 2.3.2 的公式） ---------- */
int uadd_ok(unsigned u, unsigned v) { unsigned s = u + v; return s >= u && s >= v; }
int tadd_ok(int u, int v)
{
    int s = u + v;
    int pos_over = (u > 0) && (v > 0) && (s <= 0);
    int neg_over = (u < 0) && (v < 0) && (s >= 0);
    return !(pos_over || neg_over);
}
int tmult_ok(int u, int v)
{
    if (u == 0 || v == 0) return 1;
    long long p = (long long) u * (long long) v;   /* 用 64 位精确积判断 */
    return p >= INT_MIN && p <= INT_MAX;
}

int main(void)
{
    printf("== 无符号加法: 8 位视角 ==\n");
    unsigned char a = 0xE9, b = 0xD5;
    printf("0xE9 + 0xD5 = 0x%02X  (真和 %u，模 256 后 %u)\n",
           (unsigned char)(a + b), (unsigned) a + b, ((unsigned) a + b) % 256);
    printf("0xE9=233, 0xD5=213: 233 + 213 = 446, 446 mod 256 = %u (0xBE)\n",
           (233u + 213u) % 256);

    printf("\n== 补码加法 ==\n");
    printf("0xE9 + 0xD5 (int8 视角): %d + %d = %d\n", (signed char) 0xE9, (signed char) 0xD5,
           (signed char)(0xE9 + 0xD5));
    printf("tadd_ok(INT_MAX, 1)   = %d  (应为 0: 正溢出)\n", tadd_ok(INT_MAX, 1));
    printf("tadd_ok(INT_MIN, -1)  = %d  (应为 0: 负溢出)\n", tadd_ok(INT_MIN, -1));
    printf("tadd_ok(100, -200)    = %d  (应为 1)\n", tadd_ok(100, -200));
    printf("uadd_ok(UINT_MAX, 1U) = %d  (应为 0)\n", uadd_ok(UINT_MAX, 1U));

    printf("\n== 乘法 / 移位 ==\n");
    printf("tmult_ok(46341, 46341) = %d  (应为 0: 46341^2 溢出 int)\n", tmult_ok(46341, 46341));
    int u = 15213;
    printf("u << 3        = %d  (== u*8  = %d)\n", u << 3, u * 8);
    printf("(u<<5)-(u<<3) = %d  (== u*24 = %d)\n", (u << 5) - (u << 3), u * 24);

    int neg = -15213;
    unsigned uneg = (unsigned) neg;
    printf("\n-15213        = 0x%08X\n", uneg);
    printf("-15213 >> 1   (算术) = %d   0x%08X\n", neg >> 1, (unsigned)(neg >> 1));
    printf("-15213 >> 4   (算术) = %d   0x%08X\n", neg >> 4, (unsigned)(neg >> 4));
    printf("-15213 >> 8   (算术) = %d   0x%08X\n", neg >> 8, (unsigned)(neg >> 8));
    printf("(unsigned)-15213 >> 1 (逻辑) = %u  0x%08X\n", uneg >> 1, uneg >> 1);
    printf("(-15213)/2 = %d  (C 向零取整) vs -15213>>1 = %d  (向下取整)\n", neg / 2, neg >> 1);
    printf("偏置修正: (-15213 + (1<<1)-1) >> 1 = %d  (== 向零取整结果)\n",
           (neg + (1 << 1) - 1) >> 1);
    printf("(-15213)/8 = %d  vs  (-15213 + 7) >> 3 = %d\n", neg / 8, (neg + 7) >> 3);

    printf("\n== Data Lab 风格技巧 ==\n");
    printf("dl_negate(-15213)  = %d  (期望 15213)\n", dl_negate(-15213));
    printf("dl_bitAnd(0x69,0x55) = 0x%X (期望 0x41)\n", dl_bitAnd(0x69, 0x55));
    printf("dl_isEqual(5,5) = %d  dl_isEqual(5,6) = %d\n", dl_isEqual(5, 5), dl_isEqual(5, 6));
    printf("dl_logicalNeg(0) = %d  dl_logicalNeg(7) = %d  (期望 !x)\n",
           dl_logicalNeg(0), dl_logicalNeg(7));
    printf("dl_sign(-9)=%d dl_sign(0)=%d dl_sign(9)=%d\n", dl_sign(-9), dl_sign(0), dl_sign(9));
    printf("dl_isPowerOf2(1)=%d (2)=%d (6)=%d (-8)=%d\n",
           dl_isPowerOf2(1), dl_isPowerOf2(2), dl_isPowerOf2(6), dl_isPowerOf2(-8));
    printf("x & (x-1) 清掉最低位的 1: 0x%X -> 0x%X\n", 0x6C, 0x6C & (0x6C - 1));
    printf("x & -x   取出最低位的 1: 0x%X -> 0x%X\n", 0x6C, 0x6C & (-0x6C));
    printf("!!0 = %d, !!5 = %d, !0 = %d\n", !!0, !!5, !0);

    puts("\n-- 移位量 <0 或 >= 字长 是未定义行为 (UB)，结果依机器/编译器而异 --");
    volatile int sh = 32;
    printf("1 << 32 (UB) 实际得到: %d\n", 1 << sh);
    return 0;
}

【代码做什么？】 前三段分别验证无符号回绕（$233+213=446 \to 190$）、补码加法与溢出检测公式、乘法/移位等价；第四段把算术右移与逻辑右移、C 的向零取整除法三者放在一起对照；第五段集中展示 Data Lab 的核心技巧；末尾演示移位量越界这一 UB。

【底层机制透视】

  • dl_negate 就是 $\sim x + 1$，无分支、无乘法。
  • dl_logicalNeg 的依据是：$x \ne 0$ 时 $x$ 与 $-x$ 中必有一个最高位为 1，故 x \| (~x+1) 的符号位即”$x$ 非零”的标志；>> 31 得到 -1 或 0，+1 归一化为 1 或 0。
  • dl_isPowerOf2 用 x & (x-1) 清掉最低位的 1：2 的幂只有一个 1，清掉后为 0。注意 !(x >> 31) 排除负数、!!x 排除 0，且常量 ~0 只有 8 位，满足 Data Lab”常量不得超过 8 位”的限制。
  • x & -x 是”取出最低位的 1”（lowbit），x & (x-1) 是”清除最低位的 1”，这一对操作是位运算的基本功。
  • tadd_ok 用的是符号判断而非比较位宽：同号相加结果变号即为溢出，无需更宽的中间类型。

【实测验证】：

== 无符号加法: 8 位视角 ==
0xE9 + 0xD5 = 0xBE  (真和 446，模 256 后 190)
0xE9=233, 0xD5=213: 233 + 213 = 446, 446 mod 256 = 190 (0xBE)

== 补码加法 ==
0xE9 + 0xD5 (int8 视角): -23 + -43 = -66          <- 与讲义 TAdd 表格一致
tadd_ok(INT_MAX, 1)   = 0  (应为 0: 正溢出)
tadd_ok(INT_MIN, -1)  = 0  (应为 0: 负溢出)
tadd_ok(100, -200)    = 1  (应为 1)
uadd_ok(UINT_MAX, 1U) = 0  (应为 0)

== 乘法 / 移位 ==
tmult_ok(46341, 46341) = 0  (应为 0: 46341^2 溢出 int)
u << 3        = 121704  (== u*8  = 121704)
(u<<5)-(u<<3) = 365112  (== u*24 = 365112)

-15213        = 0xFFFFC493
-15213 >> 1   (算术) = -7607   0xFFFFE249
-15213 >> 4   (算术) = -951   0xFFFFFC49
-15213 >> 8   (算术) = -60   0xFFFFFFC4
(unsigned)-15213 >> 1 (逻辑) = 2147476041  0x7FFFE249
(-15213)/2 = -7606  (C 向零取整) vs -15213>>1 = -7607  (向下取整)
偏置修正: (-15213 + (1<<1)-1) >> 1 = -7606  (== 向零取整结果)
(-15213)/8 = -1901  vs  (-15213 + 7) >> 3 = -1901

== Data Lab 风格技巧 ==
dl_negate(-15213)  = 15213  (期望 15213)
dl_bitAnd(0x69,0x55) = 0x41 (期望 0x41)
dl_isEqual(5,5) = 1  dl_isEqual(5,6) = 0
dl_logicalNeg(0) = 1  dl_logicalNeg(7) = 0  (期望 !x)
dl_sign(-9)=-1 dl_sign(0)=0 dl_sign(9)=1
dl_isPowerOf2(1)=1 (2)=1 (6)=0 (-8)=0
x & (x-1) 清掉最低位的 1: 0x6C -> 0x68
x & -x   取出最低位的 1: 0x6C -> 0x4
!!0 = 0, !!5 = 1, !0 = 1

-- 移位量 <0 或 >= 字长 是未定义行为 (UB)，结果依机器/编译器而异 --
1 << 32 (UB) 实际得到: 1

-15213 >> 1/4/8 = -7607/-951/-60 与讲义表格逐行一致，正是”算术右移向下取整”的证据。1 << 32 在本机得到 1（x86 的移位量按 32 取模），但这是 UB，不可依赖。

2.3.4 真实 x86-64 汇编：乘以 24、算术右移与偏置修正

代码 (C)：

/* /tmp/c02_asm.c   查看汇编: gcc -O1 -S -std=c11 c02_asm.c -o c02_asm.s */
int       arith(int x, int y) { return (x + y) * 24; }
int       mul3(int x)         { return x * 3; }
int       udiv8(unsigned u)   { return u >> 3; }
int       sdiv8(int x)        { return x / 8; }
unsigned  umul(unsigned x, unsigned y) { return x * y; }

【与汇编 / 硬件的对应】（gcc -O1 -S 后 objdump -d c02_asm_O1.o 得到的真实 AT&T 汇编与机器码字节）：

0000000000000000 <arith>:
   0:	01 f7       	add    %esi,%edi          # x + y（丢弃进位：addl 语义）
   2:	8d 04 7f    	lea    (%rdi,%rdi,2),%eax # 3 * (x+y)，一条 LEA 完成
   5:	c1 e0 03    	shl    $0x3,%eax          # 再 << 3  => (x+y)*24
   8:	c3          	retq

0000000000000013 <sdiv8>:
  13:	8d 47 07    	lea    0x7(%rdi),%eax     # 偏置: x + 2^3 - 1 = x + 7
  16:	85 ff       	test   %edi,%edi          # 判断 x 的符号
  18:	0f 49 c7    	cmovns %edi,%eax          # 若 x >= 0 则用原值（不加偏置）
  1b:	c1 f8 03    	sar    $0x3,%eax          # 算术右移 3 位 == 向零取整的 /8
  1e:	c3          	retq

000000000000001f <umul>:
  1f:	89 f8       	mov    %edi,%eax
  21:	0f af c6    	imul   %esi,%eax          # 32 位乘法，只保留低 32 位
  24:	c3          	retq

同时对照 udiv8 只用了 movl %edi,%eax; shrl $3,%eax——无符号除法只需一条逻辑右移，而有符号除法要多出”加偏置 + 条件选择”三步。这正是 $(x + 2^k - 1) \gg k$ 公式在真实编译器输出里的样子：GCC 用 cmovns 而不是分支，避免预测失败开销；umul 用的是 imul，因为 x86-64 中有符号与无符号乘法的低 $w$ 位完全相同，同一条指令即可服务于两者。

2.4 实验关联

L1 Data Lab（LAB-datalab.txt）是本讲唯一的直接对应实验，全部 13 个 puzzle 都在考本讲内容。

  • 规则映射：整数 puzzle 只允许 8 个运算符 ! ~ & ^ \| + << >>，禁止循环与条件（必须是直通代码 straight-line code），常量不得超过 8 位；浮点 puzzle 允许条件与循环，但禁止任何浮点类型/运算/常量，参数与返回值都以 unsigned 传递位模式。这正是 2.3.3 节全部代码遵循的约束——那里的每个函数都能通过 dlc。
  • 典型 puzzle 与本讲的对照：bitXor 用 De Morgan（2.2.3 节 dl_bitAnd 的同款思路）；tmin 直接用 1 << 31 或 0x80000000 的等价 8 位构造；negate 就是 $\sim x+1$；isTmax 依赖 $TMax + 1 = TMin$ 的回绕；allOddBits 用掩码；logicalNeg 对应 2.3.3 节的 x \| (~x+1)；conditional（实现 x ? y : z）用 ~((x\|~x+1)>>31) 造出全 0/全 1 掩码；isLessOrEqual 必须分别处理同号与异号（同号相减会溢出，异号相减不会）；howManyBits 用二分法逐段判断高位是否为 0。
  • 工具链：make 后依次使用 ./btest（功能正确性，./btest -f bitXor -1 4 -2 5 可指定单个函数与参数）、./dlc -e bits.c（检查运算符计数与规则合规）、./driver.pl（汇总正确性 36 分 + 性能 26 分 + 风格 5 分，满分 67）。
  • 必须提前知道的坑：bits.c 不要 #include <stdio.h>（会让 dlc 报出难以理解的错误；调试时仍可直接调用 printf，忽略 gcc 的隐式声明警告即可）；dlc 强制”声明必须出现在块内所有非声明语句之前“（C89 风格），把 int b = a; 写在 a *= 3; 之后会报错；浮点 puzzle 请先用 ./fshow 2080374784 之类的命令观察位域结构再动手。讲义还附带可选的 “Beat the Prof” 竞赛，目标是用最少运算符数追平或击败教师。

2.5 常见错误与调试技巧

  • & 写成 &&（或 \| 写成 \|\|）：if (x & y) 与 if (x && y) 在 x=1, y=2 时结果相反；p & *p 会真的解引用空指针。调试：gcc -Wall -Wextra -Wlogical-op，GCC 会提示”logical operator applied to bitwise”；用 gdb 单步到该行，p x、p y、p x & y 对比。
  • 有符号/无符号混合比较：if (len - 1 >= 0)、for (unsigned i = n-1; i >= 0; i--) 恒真，循环永不退出甚至越界。调试：gcc -Wall -Wextra -Wsign-compare（-Werror 可强制修复）；出现”卡死”时用 gdb -p <pid> 附加后 bt 看栈、p i 看计数器的实际类型与值。
  • abs(INT_MIN)、-INT_MIN 所得为负：负数的相反数在 int 中不可表示，是 UB。调试：gcc -fsanitize=undefined -g（UBSan）编译运行，会打印 runtime error: negation of -2147483648 cannot be represented in type 'int'；用 -ftrapv 让有符号溢出直接 abort。
  • 移位量越界：1 << 32、x >> -1 是 UB，在 x86 上移位量被按 32/64 取模，看起来”能用”却不可移植。调试：UBSan 报 shift exponent 32 is too large for 32-bit type 'int'；确认字长用 p sizeof(int)*8。
  • 把算术右移当除法用：x >> k 对负数是向下取整，-15213 >> 1 = -7607 而 / 2 = -7606。调试：写单元测试对比 x >> k 与 x / (1 << k)，用 gcc -S 检查编译器是否生成了 sar 前缺偏置。
  • 字节序误判：把 int 直接 fwrite 到文件再用大端机读，得到 0x67452301 式的乱值；用 %x 打印单字节导致 01 显示成 1。调试：show_bytes 打印；gdb 中用 x/4xb &x 看原始字节、p/x x 看数值；跨平台传输一律用 htonl/ntohl 或文本格式。
  • 隐式截断丢高位：unsigned char c = 300; 得 44；把 int 塞进 short 在赋值点静默截断。调试：-Wconversion；gdb 下 p (short) x 与 p x 对照，或 p/x x 看位模式。
  • Data Lab 里违反 dlc 规则：用了 -（一元负号）、&&、if，或常量超过 8 位，导致 dlc 报错而 btest 仍然通过，最终 driver.pl 扣掉性能分。调试：先跑 ./dlc -e bits.c 看每个函数的运算符计数，再跑 ./btest -f <name>；用 ~0、1 << 31 之类的方式构造长常量。

2.6 关键要点

  • 比特没有类型，只有解释。 同一串 0xFFFFFFFF 可以是 4294967295，也可以是 -1，区别只在类型；转换是”免费”的（不产生指令），但会静默改变比较与除法的语义。
  • 补码 = 最高位权重取负。 $B2T$ 与 $B2U$ 的唯一差别是 $x_{w-1}$ 的权重为 $-2^{w-1}$；由 $x + \sim x = -1$ 立刻得到 $ -x = \sim x + 1 $，而 $TMin$ 没有正伴侣。
  • 有符号与无符号的加减乘在硬件上共用同一套位级运算。 结果位相同、解释不同；代价是混合表达式里 int 被隐式转成 unsigned，-1 > 0U 为真。
  • 右移的语义必须分清三个概念：无符号逻辑右移 = 整除；有符号算术右移 = 向下取整（负数需加 $2^k-1$ 偏置才等于 C 的向零取整）；负数右移是实现定义，移位量越界才是 UB。
  • 溢出是回绕而非报错。 无符号按 $2^w$ 取模、补码按双向回绕；编译器可以假设有符号溢出永不发生，所以 UB 代码”现在能跑”不代表正确。
  • Data Lab 的规则就是本讲的纪律：只用 8 个运算符、无分支、常量 ≤ 8 位——它逼你从”写代码”切换到”设计掩码与位模式”的思维。

2.7 思考题（带答案）

Q1（计算/推演题） 某 16 位字在内存中的字节序列（从低地址到高地址）为 6d 3b。求把它当作 unsigned short 与 short 解释时的值；若这台机器是大端机，同样的字节序列又表示什么？另外，已知 x = 0xC493，分别写出 $B2U_{16}$ 与 $B2T_{16}$ 的计算过程。

答：小端机中低地址字节是 LSB，故位模式为 00111011 01101101 = 0x3B6D。$B2U_{16} = 3\times16^3 + 11\times16^2 + 6\times16 + 13 = 12288+2816+96+13 = 15213$；最高位为 0，所以 $B2T_{16} = 15213$。大端机则把 6d 当 MSB，位模式变成 0x6D3B，$B2U = 6\times4096 + 13\times256 + 3\times16 + 11 = 24576+3328+48+11 = 27963$，仍为正数。对 0xC493：$B2U_{16} = 12\times4096 + 4\times256 + 9\times16 + 3 = 49152+1024+144+3 = 50323$；$B2T_{16} = -1\times2^{15} + 50323 = -32768 + 50323 = -15213$，与讲义表格一致。（也即 -15213 的 16 位补码正是 0xC493。）

Q2（计算/推演题） 判断下列 C 表达式的值并说明原因：(unsigned)(-1) > 0、-1 > (unsigned)-1、2147483647U < (int)2147483648U、(x & (x-1)) == 0 在 x = 0x80000000 时是否成立。

答：(unsigned)(-1) 把 0xFFFFFFFF 按无符号解释得 4294967295，故 > 0 为真。-1 > (unsigned)-1：右侧是 UINT_MAX，-1 被隐式转成 UINT_MAX，两者相等，> 为假。2147483647U < (int)2147483648U：右侧显式转回 int 得 INT_MIN = -2147483648，再按混合规则转成 unsigned 得 2147483648U，故 2147483647U < 2147483648U 为真。x = 0x80000000（即 INT_MIN）时 x-1 = 0x7FFFFFFF，x & (x-1) = 0，条件成立——但注意它并不说明 x 是 2 的幂，正因如此 dl_isPowerOf2 必须再加 !(x>>31) 排除负数。

Q3（直观但错误的想法的错在哪） 有同学说：”abs(x) 一定非负，所以 abs(INT_MIN) > 0 恒真；而且有符号整数溢出最多就是结果错误，无所谓。”请指出错误，并说明无符号倒计数循环 for (unsigned i = n-1; i >= 0; i--) 为什么会死循环。

答：两处都错。第一，\|INT_MIN\| = 2147483648 超出 int 的表示范围（$TMax = 2147483647$），所以 abs(INT_MIN) 的结果不可表示，标准规定这是 UB；本机 GCC 12.2.0 实测返回 -2147483648，仍是负数，换优化级别可能得到别的值。第二，有符号溢出是 UB，编译器可据此做优化（如把 x+1 > x 判为恒真、把 abs(INT_MIN)>0 折叠为常量），因此”只是结果错”的假设会让程序在换编译器后彻底失效。而 unsigned i 的取值范围是 $[0, 2^{32}-1]$，i >= 0 恒为真；当 i == 0 时执行 i-- 按模 $2^{32}$ 回绕成 4294967295，循环永远不会退出（若循环体访问 a[i] 则立刻越界）。正确写法是用有符号 int i，或改写成 for (unsigned i = n; i-- > 0; )。

Q4（实现细节题） 为什么 -15213 / 8 的结果是 -1901，而 -15213 >> 3 在未加偏置时得到什么？编译器为实现 /8 实际发出了哪些指令？

答：C 的整数除法向零取整，-15213/8 = -1901.625 \to -1901。算术右移 $k$ 位等价于 $\lfloor x/2^k \rfloor$，是向下取整，实测 -15213 >> 3 得 $-1902$，比正确的 $-1901$ 小 1（讲义表中 $k=1$ 时 -15213>>1 = -7607 而 -15213/2 = -7606，正是同一偏差）。因此必须先把被除数向 0 偏置：(x + (1<<3) - 1) >> 3 = (-15213+7)>>3 = -1901，与除法一致。GCC 12.2.0 -O1 对 sdiv8 的实测输出是 lea 0x7(%rdi),%eax; test %edi,%edi; cmovns %edi,%eax; sar $0x3,%eax——用 cmovns 无条件选择是否加偏置（x >= 0 时不加，因为正数右移与除法本就一致），最后一条 sar 完成除 8。