CS 与 LLM 学习知识库

信息的表示

28分钟阅读

在 C 里 INT_MAX + 1 会变成一个很大的负数；在 Python 里 0.1 + 0.2 == 0.3 是 False；训练大模型时把 fp32 换成 fp16，loss 突然变成 inf，换成 bf16 却没事。这三件怪事有同一个根源：计算机里只有固定长度的一串位，“这串位代表什么”完全是人约定的。看懂这几种约定，上面的现象都能从位上直接推出来。

前置：离散数学（进制与模运算）

文中的 C 程序用 Apple clang 21 在 macOS（Apple M3）上编译运行，Python 用 /usr/bin/python3。

位、字节与十六进制

一个位（bit）只有 0 和 1 两种状态。之所以用二进制，不是因为它在数学上更优雅，而是因为电路上区分”有电压/没电压”最稳：噪声让 0.9V 变成 0.8V，依然能判为 1。这一点 Crash Course 的晶体管那几集讲得很直观，CPU 本身的结构留给 机器级程序。

单个位能表达的太少，于是 8 位组成一个字节（byte），这是内存寻址的最小单位：地址指向的是字节，不是位。一个字节有 256 种取值，写成二进制要 8 个字符，太长；写成十进制又看不出位的结构。折中方案是十六进制：每 4 位正好对应一个 hex 数字 0–f，一个字节就是两个 hex 数字。0x3dcccccd 一眼就能拆成 0011 1101 1100 1100 …，这是读内存转储和浮点位模式的基本功。

n 位能表示 2ⁿ 种不同的模式。这句话是下文所有编码的边界：无论约定成整数、小数还是字符，32 位最多只能区分约 43 亿个东西。整数编码会溢出、浮点会舍入、字符集要分层编码，都是在这个上限下做取舍。

把位串当成一组开关时，就需要位运算：&（与）、|（或）、^（异或）、~（取反）和移位。它们是逐位独立计算的，最常见的用途是掩码（mask）：x & 0xFF 取出最低字节，x | (1 << k) 把第 k 位置 1，(x >> k) & 1 读第 k 位。两个经典小技巧值得自己在纸上验算一次：x & (x - 1) 清掉最低的那个 1（10110100 变成 10110000），x & -x 只保留最低的那个 1（得到 100）。前者可以用来数 1 的个数、判断是否为 2 的幂；后者是树状数组的核心操作。页表项里的权限位、文件权限 0755、CPU 的标志寄存器，都是这样按位打包的。

还有一个容易忽略的单位叫字长（word size），即指针有多宽。今天的机器基本都是 64 位，所以 sizeof(void*) == 8，虚拟地址空间理论上可达 2⁶⁴ 字节。C 的 long 在 macOS/Linux 上是 8 字节，int 依然是 4 字节，这就是为什么下文的整数例子用 int 能看到 32 位边界。

无符号整数与补码

最直接的约定是无符号（unsigned）编码：把位串当成二进制数，第 i 位贡献 2ⁱ。4 位能表示 0 到 15，32 位能表示 0 到 4294967295。

负数怎么办？最朴素的想法是拿最高位当符号位，剩下的位表示绝对值（原码）。它有两个毛病：0 有 +0 和 -0 两种写法；加法电路必须先看符号再决定做加还是做减。

补码（two’s complement）用一个很巧的办法把两个毛病一起消掉：最高位的权重不是 +2^(w-1)，而是 -2^(w-1)。4 位补码里，1011 = −8 + 2 + 1 = −5。这样一来：

  • 0 只有一种写法 0000；范围是 −8 到 7，负数比正数多一个。
  • 求相反数的规则是”按位取反再加 1”：0101（5）取反得 1010，加 1 得 1011（−5）。
  • 最关键的：补码加法和无符号加法用的是同一个电路。两个 w 位数相加，丢掉第 w 位的进位，结果对无符号是”模 2ʷ 加法”，对补码恰好也是正确的有符号结果（只要不溢出）。

最后一条是补码胜出的原因。CPU 里只需要一个加法器，有符号和无符号的区别只存在于程序员怎么解释结果、以及比较和除法该用哪条指令。

这同时意味着：同一串位，换个解释，值就变了。C 里有符号和无符号之间的转换不改变任何位，只改变解释：

int x = INT_MAX;
printf("INT_MAX = %d, INT_MAX+1 = %d\n", x, x + 1);
int m = -1; unsigned u = (unsigned)m;
printf("-1 as unsigned = %u (0x%x)\n", u, u);
printf("-1 < 0u ? %d\n", -1 < 0u);
short s = -12345; int i = s;
printf("short -12345 = 0x%04hx, sign-extended int = 0x%08x\n",
       (unsigned short)s, (unsigned)i);
INT_MAX = 2147483647, INT_MAX+1 = -2147483648
-1 as unsigned = 4294967295 (0xffffffff)
-1 < 0u ? 0
short -12345 = 0xcfc7, sign-extended int = 0xffffcfc7

逐行看：

INT_MAX 是 0x7fffffff，加 1 得 0x80000000，按补码读就是 −2³¹。硬件只是做了一次普通加法。注意 C 标准规定有符号溢出是未定义行为（UB），编译器可以假设它不发生并据此优化（例如把 x + 1 > x 直接折叠成真）；上面编译时加了 -fwrapv 才保证看到回绕。无符号溢出则是明确定义的模 2ʷ 运算。

-1 的补码是全 1，即 0xffffffff，按无符号读就是 2³² − 1。

-1 < 0u 为假，是 C 最经典的坑：当一个有符号数和一个无符号数比较，C 先把有符号数转成无符号，于是比较的是 4294967295 < 0。写 for (unsigned i = n - 1; i >= 0; i--) 会死循环，原因相同：i >= 0 对无符号数永远成立。size_t、sizeof 的结果都是无符号的，混用时要格外小心。

把 16 位的 short 扩展成 32 位 int 时，高位填的是原来的符号位（这里是 1），叫符号扩展；无符号数扩展时高位填 0，叫零扩展。两种规则都保证数值不变。反过来截断（int 转 short）就是直接丢掉高位，对无符号相当于取模，对有符号可能把正数变成负数。

停一下，检查理解单选

在 C 里，unsigned n = 0; for (int i = 0; i < n - 1; i++) {...} 的循环体会执行几次？

整数运算：乘法、移位与溢出

既然加法是模 2ʷ 的，乘法也一样：两个 32 位数相乘，真实结果最多 64 位，只保留低 32 位。CSAPP 的一个经典结论是，在模 2ʷ 意义下，补码乘法和无符号乘法的低 w 位完全相同，所以硬件同样只需要一套乘法器。

乘法比加法慢（在现代 CPU 上大约 3 个周期，加法是 1 个），所以编译器会把乘以常数改写成移位和加法：x * 8 变成 x << 3，x * 14 可以变成 (x << 4) - (x << 1)。除法慢得多（几十个周期），除以 2 的幂会变成右移。这里有个细节：对负数，算术右移是向下取整（-5 >> 1 得 −3），而 C 的整数除法是向零取整（-5 / 2 得 −2），所以编译器要先给负数加一个偏置 (1 << k) - 1 再移位。你在 机器级程序 里看到的汇编，经常会出现这种看起来奇怪的移位组合。

右移有两种：逻辑右移高位补 0，算术右移高位补符号位。对无符号数 C 用逻辑右移；对有符号数，几乎所有编译器用算术右移（C++20 起才写进标准）。

溢出会造成真实的安全问题。一段常见代码是 malloc(n * sizeof(T))：如果攻击者能控制 n，让 n * sizeof(T) 溢出回绕成一个很小的数，malloc 就只分配了一点点内存，后续却按 n 个元素去写，变成堆溢出。这就是为什么 calloc(n, size) 和 reallocarray 会在内部检查乘法溢出。在 Python 里不会有这个问题，因为 Python 的 int 是任意精度的，它在底层用一个数组存多段”数字”，代价是每次运算都要循环，这部分的对象布局见 Python 对象模型。

字节序：一个 int 在内存里怎么摆

一个 4 字节的 int 占 4 个连续地址。那么 0x01234567 的哪一个字节放在最低地址？

int n = 0x01234567; unsigned char *p = (unsigned char*)&n;
printf("0x01234567 in memory: %02x %02x %02x %02x\n", p[0],p[1],p[2],p[3]);
0x01234567 in memory: 67 45 23 01

最低有效字节 0x67 放在最低地址，这叫小端序（little-endian）。x86-64 和 Apple Silicon（ARM64 默认模式）都是小端。反过来叫大端序（big-endian），网络协议的报文头规定用大端，所以写 socket 程序要用 htonl/ntohl 转换（细节见 网络：从链路到 IP）。

两种都没有本质优劣。小端的好处是，把一个 int 当成 short 读，只需要读相同起始地址的前两个字节，地址不变。字节序只在”把多字节值拆成字节”时才会暴露出来：读二进制文件、跨机器传数据、用 struct.pack 打包、或者像上面这样拿 char* 窥探内存。在同一台机器上用 int 读写 int，你永远感觉不到它。

停一下，检查理解多选

在一台小端机器上，uint32_t v = 0xAABBCCDD; 存在地址 0x100 起的 4 个字节。下面哪些说法正确？

浮点数：用科学计数法换范围

整数的问题是范围：32 位最大约 21 亿，表示不了 10³⁰，也表示不了 0.5。最朴素的修正是定点数：约定小数点固定在第 16 位后。可这样范围和精度只能二选一，要表示极大和极小的数，位数会爆炸。

科学计数法给了出路：6.02 × 10²³ 用很少的数字就覆盖了巨大的范围，代价是只保留几位有效数字。IEEE 754 浮点数就是二进制的科学计数法：

值 = (-1)^s × 1.f × 2^(e - bias)

一个 fp32 有 32 位：1 位符号 s、8 位指数 e、23 位尾数（fraction）f。指数用偏置（bias = 127）表示而不是补码，这样指数字段可以当无符号数比较，两个正浮点数的大小关系和它们位模式按整数比较的大小关系一致。尾数前面那个 1. 不存储，因为规格化的二进制数首位必然是 1，省下一位等于白赚一位精度。

看几个真实位模式：

import struct
def bits(x, fmt, n):
    v = int.from_bytes(struct.pack('>'+fmt, x), 'big'); return format(v, f'0{n}b')
for x in [1.0, -2.5, 0.1]:
    b = bits(x, 'f', 32); print(f"fp32 {x:>5}: {b[0]} {b[1:9]} {b[9:]}")
fp32   1.0: 0 01111111 00000000000000000000000
fp32  -2.5: 1 10000000 01000000000000000000000
fp32   0.1: 0 01111011 10011001100110011001101

1.0 = 1.0 × 2⁰，指数字段存 0 + 127 = 01111111，尾数全 0。−2.5 = −1.01₂ × 2¹，符号位 1，指数 128，尾数 01…。

0.1 的尾数是 1001 1001 1001 … 的循环，因为 0.1 = 1/10，而 10 含有因子 5，在二进制里和 1/3 在十进制里一样是无限循环小数。23 位截不完，只能舍入（最后一位进了 1，所以末尾是 1101）。存进去的已经不是 0.1，而是离它最近的那个可表示数。这就是 0.1 + 0.2 != 0.3 的全部原因：

0.1+0.2 == 0.3 ? 0, 0.1+0.2 = 0.30000000000000004

三个数各自带着舍入误差，加完后的误差恰好和 0.3 自己的舍入误差不一样。比较浮点数应该用 abs(a - b) < eps 或 math.isclose。

指数字段有两个保留值。全 0 表示非规格化数（denormal）：去掉隐含的 1，让数值能平滑地逼近 0，而不是在最小规格化数和 0 之间留一个大坑。全 1 表示特殊值：尾数为 0 是 ±inf，否则是 NaN。1.0/0 得 inf，0.0/0 和 inf - inf 得 NaN；NaN 和任何数比较都是假，包括它自己，所以 x != x 是判断 NaN 的老办法。

舍入的代价：浮点不满足结合律

浮点数是不均匀分布的：在 1 附近，相邻两个 fp32 相差约 1.2 × 10⁻⁷；在 2²⁴ = 16777216 附近，相邻间隔已经是 2。于是：

16777216f + 1 = 16777216.0
(1e20 + -1e20) + 3.14 = 3.14, 1e20 + (-1e20 + 3.14) = 0

16777216 + 1 的精确结果落在两个可表示数中间，按”向偶数舍入”（round-to-nearest-even，IEEE 默认）回到 16777216。第二行说明浮点加法不满足结合律：先让两个大数抵消，3.14 能保住；先让 3.14 和 −1e20 相加，3.14 小于 −1e20 的精度间隔，直接被吞掉。

相邻可表示数的间隔叫 ulp（unit in the last place），它和数值本身成比例。Python 的 math.ulp 可以直接查 fp64 的间隔：

import math
for x in [1.0, 1024.0, 2.0**24, 1e16]: print(f'ulp({x:g}) = {math.ulp(x):g}')
ulp(1) = 2.22045e-16
ulp(1024) = 2.27374e-13
ulp(1.67772e+07) = 3.72529e-09
ulp(1e+16) = 2

数值每翻一倍，间隔也翻一倍，所以浮点的相对误差大致恒定（fp64 约 1e-16，fp32 约 6e-8），绝对误差却随数值增长。到 1e16 时 fp64 连相邻整数都分不开了，这也是 JavaScript 里大于 2⁵³ 的整数会”失真”的原因。

这对系统设计有直接后果。编译器在没有 -ffast-math 时不敢重排浮点加法，因为那会改变结果。GPU 上的并行归约（reduce）每次的加法顺序可能不同，所以同一个模型跑两次，loss 的最后几位可能不一样。用 fp32 累加一亿个小数时，越往后累加和越大，新加进来的小数损失越多，这就是为什么 Kahan 求和、分块求和、以及”低精度乘、高精度累加”在数值代码里随处可见。

停一下，检查理解单选

用 fp32 变量 s 从 0 开始依次累加两千万个 1.0f，最终结果最可能是？

低精度格式：fp16 与 bf16

深度学习把浮点的取舍推到了极致。参数、激活、梯度动辄几十 GB，用 16 位代替 32 位，显存和带宽直接减半，Tensor Core 的吞吐还更高。问题是 16 位怎么分给指数和尾数。两种主流答案：

格式符号指数尾数最大值1 附近的精度
fp321823~3.4e38~1.2e-7
fp16151065504~9.8e-4
bf16187~3.4e38~7.8e-3

fp16（IEEE half）保精度、牺牲范围；bf16（brain float，Google Brain 提出）保范围、牺牲精度。bf16 的布局就是 fp32 砍掉低 16 位，指数位数一样：

b = bits(0.1,'e',16); print(f"fp16   0.1: {b[0]} {b[1:6]} {b[6:]}")
f32 = bits(0.1,'f',32); print(f"bf16   0.1: {f32[0]} {f32[1:9]} {f32[9:16]}  (fp32 高 16 位)")
print("fp16 max =", struct.unpack('>e', bytes.fromhex('7bff'))[0])
try: struct.pack('>e', 70000.0)
except OverflowError as e: print("fp16(70000):", e)
bf = lambda x: struct.unpack('>f', struct.pack('>f', x)[:2] + b'\0\0')[0]   # 截断高 16 位，示意 bf16
print("bf16(70000) ≈", bf(70000.0), " bf16(1.0+1/256) =", bf(1+1/256))
fp16   0.1: 0 01011 1001100110
bf16   0.1: 0 01111011 1001100  (fp32 高 16 位)
fp16 max = 65504.0
fp16(70000): float too large to pack with e format
bf16(70000) ≈ 69632.0  bf16(1.0+1/256) = 1.0

（上面的 bf 用截断演示布局，真实硬件转换通常是向偶数舍入，数值可能差一个单位。）

现在能解释开头的现象了。fp16 最大只有 65504，大模型里 attention 的 logits、某些层的激活、loss 本身都可能超过它，一旦超过就变成 inf，再参与运算就成了 NaN。另一端，很小的梯度（比如 1e-8）低于 fp16 能表示的最小值，直接下溢成 0。所以 fp16 训练必须配合 loss scaling：先把 loss 乘一个大系数，让梯度挪进 fp16 的可表示区间，更新参数前再除回去。

bf16 的指数和 fp32 一样宽，范围问题基本消失，可以不用 loss scaling，这是它成为大模型训练默认格式的原因。代价是只有 7 位尾数：1 + 1/256 在 bf16 里直接等于 1。所以实践中仍然用 fp32 保存主参数副本、用 fp32 累加矩阵乘的部分和，这套混合精度方案以及显存账怎么算，归 资源核算与 Scaling Laws；更激进的 fp8（E4M3/E5M2）和 int8/int4 量化，在推理里的用法归 推理系统。它们的位布局逻辑和这里完全一样：指数位决定范围，尾数位决定精度。

停一下，检查理解多选

用 fp16 做混合精度训练时 loss 变成 NaN，换成 bf16 后正常。下面哪些解释合理？

文字：从 ASCII 到 UTF-8

最后一种信息是文字。约定很简单：给每个字符一个编号。ASCII 用 7 位给 128 个字符编号，'A' 是 65（0x41），'a' 是 97，大小写正好差 32，也就是一个位（0x20），所以 C 里 c | 0x20 能把大写变小写。CS50 第一周讲的 'A' + 1 == 'B' 正是利用了编号连续。

128 个位置装不下中文。Unicode 把问题分成两层：第一层给世界上每个字符分配一个码点（code point），写作 U+4E2D（“中”），目前范围是 0 到 0x10FFFF；第二层是编码，即码点怎么变成字节。如果直接用 4 字节存每个码点（UTF-32），英文文本会膨胀 4 倍，而且和所有 ASCII 程序不兼容。

UTF-8 是现在的事实标准，它是变长编码：

  • U+0000–U+007F：1 字节 0xxxxxxx，与 ASCII 完全相同。
  • U+0080–U+07FF：2 字节 110xxxxx 10xxxxxx。
  • U+0800–U+FFFF：3 字节 1110xxxx 10xxxxxx 10xxxxxx（常用汉字在这里）。
  • U+10000–U+10FFFF：4 字节 11110xxx 开头（emoji 在这里）。
for s in ["A", "é", "中", "🙂"]:
    e = s.encode('utf-8'); print(f"{s!r}: U+{ord(s):04X} -> {e.hex(' ')} ({len(e)} bytes)")
print(len("中文🙂"), len("中文🙂".encode()))
'A': U+0041 -> 41 (1 bytes)
'é': U+00E9 -> c3 a9 (2 bytes)
'中': U+4E2D -> e4 b8 ad (3 bytes)
'🙂': U+1F642 -> f0 9f 99 82 (4 bytes)
3 10

这个设计有几处精妙。首字节的前缀 0、110、1110、11110 直接告诉你这个字符有几个字节；后续字节都以 10 开头，绝不会和首字节混淆，所以从任意位置开始读，最多往回退 3 个字节就能找到字符边界，坏掉一个字节也只影响一个字符。ASCII 字节（最高位为 0）永远不会出现在多字节字符内部，所以按 '/' 或 '\n' 切分 UTF-8 字符串是安全的。

最后一行说明”字符串长度”有歧义：Python 的 len(str) 数的是码点（3 个），len(bytes) 数的是字节（10 个），C 的 strlen 数的也是字节。截断 UTF-8 字节串时如果切在多字节字符中间，就会得到无法解码的半个字符。LLM 的 tokenizer 正是在 UTF-8 字节序列上做 BPE 的，所以一个汉字可能被切成多个 token，这部分归 分词。

停一下，检查理解单选

一个 UTF-8 字节串里某个字节是 0xB8（二进制 10111000）。关于它能确定什么？

记住这三件事

  1. 位本身没有含义，含义来自约定：同一串位可以是 −1、4294967295 或者一个 NaN，C 里的类型转换往往只是换一种解释。
  2. 固定位宽意味着整数会回绕、浮点会舍入；补码让加减乘共用一套电路，浮点用指数换范围、用尾数换精度，因此不满足结合律。
  3. fp16 和 bf16 的差别只是 16 位怎么分给指数和尾数：fp16 怕溢出，bf16 怕精度不够；UTF-8 用前缀码让变长编码可以自同步并兼容 ASCII。

延伸阅读

反向链接