二进制与数制 入门

这门课里每一层搬的都是字节。curl https://api.example.com/user/42 一离开 shell 就变成一串字节，你的 handler 从路径里解析回来的那个整数也是。 8 不是自然规律：IBM System/360 在 1964 年把它定死，而按字节寻址的工具链让这个选择再也回不了头。

每个位置带一个 2 的幂，值就是被置位的那些幂之和 —— 拖滑块，看比特一个个填进去，两个半字节拼出的十六进制位跟着变：

注意十六进制位从不和比特打架：4 位恰好是 1 位十六进制，因为 16 = 2⁴，翻译过程里没有任何东西被藏起来。十进制没有这个性质 —— 255 告诉不了你哪些位被置上，而 0xff 告诉你 8 位全是 1。

这也是为什么所有调试器、十六进制编辑器和抓包工具都打十六进制而不是十进制。一个十六进制字节永远占两列；同一个字节的十进制写法占一到三列。沿着这一行拖动游标：

看十进制那一行怎么失去它的网格。72、84、47 对不齐，于是找第 14 个字节变成了数字符而不是数格子。十六进制那一行是一把尺子。十六进制的全部理由是排版上的，而且这个理由很硬。

字节不带类型。URL 里的字符 4 不是数字四 —— 它只是 ASCII 分配给这个字形的那个字节，而滑块一个字符一个字符地走过这个字符串：

字符 4 是 52，也就是 0x34；整数 4 是 0x04。一个忘掉这个区别的解析器，每一位数字都差 48 —— 这正是 atoi 要减 '0' 的原因。这 7 个字节就是 curl 为路径尾巴写出去的东西。

ASCII 用一个最高位为 0 的字节覆盖 128 个码点。UTF-8 让那个字节逐位保持不变，再靠多花字节把 Unicode 的其余部分买下来 —— 把码点往上走，看后续字节跟在首字节后面冒出来：

因为 ASCII 那一段一个比特都没动，Web 标准化到 UTF-8 时，所有 ASCII 工具一行代码都不用改就活了下来。0x7F 以上，首字节的高位宣告长度 ——110 是 2 字节，1110 是 3 字节，11110 是 4 字节 —— 所以解码器永远不需要一个单独的长度字段。

这些东西一个字节都没存下来。内存里的字节不带标签说该用哪份约定；下一条读它的指令说了算。切换读法，看固定不变的 4 个字节给出 4 个毫不相干的答案：

注意这些字节从头到尾没动过。42 28 00 00 是文本 B( 加两个 NUL、小端整数 10,306、大端整数 1,109,917,696，也是一个约 1.4×10⁻⁴¹ 的 float32 次正规数。类型是编译器替你守的承诺；硬件什么都不承诺。

存正整数是显然的；存 −42 才是有意思的那一半。符号加数值把最高位给符号，结果是两个零和 4 种加法分支。反码把每一位取反，加法要多一个循环进位。两者到 1970 年代都输了。

二进制补码换了个视角：8 个比特装的是模 256 的一个同余类，就这些。下面这个轮子就是那个同余类画一遍 —— 拖着它转，看同一个位置同时带着一个无符号读法和一个有符号读法：

这个轮子只有一道缝。顺时针走，无符号读法从 0 一路数到 255 中间不断，而有符号读法从 0 数到 127 之后掉到 −128。两者在下半圈完全一致，在上半圈恰好相差 256。这就是全部定义。

取负是从这里掉出来的。我们要 −x 满足 x + (−x) ≡ 0 (mod 256)，所以 −x 就是 256 − x；而 256 − x 正好是「每一位取反，然后加一」，因为取反得到的是 255 − x。推动步进滑块，看负数怎么从正数里搭出来：

光取反不是答案：~42 是 213，而 42 + 213 = 255 —— 离绕回还差一。那个 +1 把它补上。这里没有任何一段「负数专用电路」；它只是 ALU 本来就有的两个操作，按代数要求的顺序排了一下。

于是减法也不是一段电路。加法器把 8 列加起来，把第 9 个进位丢掉，而在模 256 意义下，这对两种读法都是对的 —— 移动两个操作数，看进位离开寄存器：

把两个操作数设成 42 和 −42，这些列产生 1 00000000：进位被丢掉，寄存器里剩下零。用无符号读法看，同样这些列说的是 42 + 214 = 256 ≡ 0。一个加法器，两种读法，数据通路上没有任何一处按符号分支。

其中两个进位值得起个名字，因为硬件两个都留着。最高位的进位输出 c₈ 就是进位标志 CF；它和进入最高位的进位 c₇ 的异或就是溢出标志 OF。把同一台加法器推过 127，看哪一盏灯亮：

CF = c₈ 说的是无符号读法装不下；OF = c₈ ⊕ c₇ 说的是有符号读法装不下。两者互相独立：100 + 100 只置 OF —— 200 装得进一个字节，只是装不进一个有符号字节。−1 + 1 只置 CF —— 255 + 1 离开了这个字节，而有符号的答案 0 仍然是对的。−100 + −100 两个都置。加法器只算一个和，却给它打两次标志；ADD 两种情况下开销一样，因为这一对标志只是挂在本来就要存在的进位链上的一个异或门。

确实有三个操作必须知道你指的是哪种读法，其中最容易看清的是移位。两个版本移的是同样 8 列，唯一的区别是往空出来的高位格子里塞什么 —— 复制的符号位，还是零。把 x 拖到零以下，两者就分开了：

x ≥ 0 时两者一致。在 x = −100、k = 3 处，算术移位给 −13，逻辑移位给 19：只有前者是 x / 2^k，而且它向 −∞ 取整，所以每个负奇数上 x >> 1 和 x / 2 都对不上。

这一节值得带走的不变式：一个 n 位寄存器装的是模 2ⁿ 的一个同余类，有符号和无符号只是这个类的两个代表元。加减乘在两种读法下是同一条指令；除法、比较和右移是仅有的三个把最高位当符号读的操作 —— 也正是下一节出错的那张清单。

8 个有符号比特的范围是 −128 到 +127：128 个负数、127 个正数，加上零。大小 128 没有正的孪生兄弟，所以 C 和 C++ 把 abs(INT_MIN) 定成未定义行为。多数实现原样返回参数，而且没有一个会抛异常。

取反加一是 256 个模式上的一个置换，而这个置换有不动点 —— 让 x 沿轴走，直到它的负数不再移动：

在 −128 处，取反给出 01111111，那个 +1 一路进位回到 10000000，也就是我们出发的地方。abs 交回一个负数，并且什么都不报。它下游的东西 —— 数组下标、长度、循环边界 —— 现在拿到了一个它当初假定不会出现的负数。

往上溢出是同一个失败，只是名声好一点。往一个 int8 累加器里反复加 16，第 9 列一掉出去，装得下的值就变成绕回去的值：

在 加 8 次 的时候，和是 128，寄存器读出 −128，没有任何东西提出异议。这不是硬件在装聋：加法器绕回的同时把 OF 置位，和 §02 一样 —— 丢掉标志的是语言。C 没有表达式能读状态位，标准还把有符号溢出定为未定义行为，于是编译器可以假定 i + 1 > i 成立并据此向量化。 Rust 的 checked_add 用的是同一条 ADD加一个分支：检查是一个可预测的分支，不是一次额外的加法。

被引用最多的例子是求平均。lo + hi 一超过 2³¹ − 1，(lo + hi) / 2 就溢出，而下面这条轴是一个有符号 32 位整数的全宽 —— 把 hi 往右拖：

看朴素中点越过零落进负半边，而这时两个下标都还是再正常不过的数。lo + (hi − lo) / 2 永远不会离开区间，因为它压根没有构造那个大和。Joshua Bloch 在 2006 年在 JDK 自己的二分查找里发现了这个，那时它已经上线 9 年了。

时间也是整数。Unix 的 time_t 是从 1970-01-01 起的有符号 32 位秒数，下面这条轴就是那个计数，像素和它成正比 —— 把时钟往前拖：

它能命名的最后一秒是 2038-01-19 03:14:07 UTC。再过一秒，计数器读出 −2,147,483,648，同一份代码打印出 1901-12-13。每一个仍然用 32 位 time_t 存时间的字段、日志格式和线上协议，里面都带着这个日期。

最后一个陷阱根本不需要溢出。C 的常规算术转换在比较里遇到一有符号一无符号时，会把有符号那个提升成无符号，于是比较发生在一条你没有选的轴上 —— 把 x 移到零以下：

int x = −1; if (x < 1u) 是假的，因为 x 变成了 4,294,967,295 —— 图里那条轴。和 size_t 比时，提升宽度就是该类型的宽度：32 位目标上是 32 位， LP64 上是 64 位，同一个 x 当成 18,446,744,073,709,551,615 来比。宽度会变，反转不会。size_t 几乎总是无符号那一半，编译器只对显式情况告警，于是这段代码干净地编过，然后上线。

float32 把这个字划成 1 + 8 + 23；float64 划成 1 + 11 + 52。两者说的是同一句话：值 = (−1)^s × 1.m × 2^{e − 偏移}，偏移分别是 127 和 1023。

3 个字段按这个顺序排列且彼此相连，而这个顺序不是随手定的 —— 让位下标走过整个字，看每一位属于哪个字段：

注意阶码排在尾数上面。把符号位撇开，两个正浮点数的大小顺序，和它们的位模式当无符号整数读时的顺序完全一致，所以整数比较器同时服务两边 —— 这在 1985 年对硅片很重要，今天也仍然让你可以对一数组浮点数做基数排序。

1.m 里那个前导 1 从来不存。每个正规值按定义都有它，所以标准把那一位收回来，白拿一位精度 —— 用阶码和尾数搭出一个值，在舞台底部读那条公式：

于是 23 位存下来的尾数买到 24 位有效数字，约 7.2 个十进制位。 float64 的 52 位买到 53 位，约 15.9 个。这个数 —— 53 位 —— 是要带走的那一个；下一节里每一个结论都从它掉出来。

阶码是带偏移存的，而不是当成一个有符号字段，下面两条轴刻度间距一致，所以那个平移看起来就只是一次平移：

因为存下来的形式就是一个普通的无符号字节，阶码越大位模式就越大，中间没有符号加数值那种断点来破坏顺序。代价是两个保留编码：0 和 255 不表示任何一个 2 的幂。

这两个编码就是数系其余部分住的地方。在 5 种编码之间切换，看保留的阶码各自占住范围的两端：

咬人的是 NaN。NaN == NaN 在所有符合标准的语言里都是假，所以 x != x 是可移植的判定方式，也所以排序比较器里混进一个 NaN 会让数组排不好 —— 比较器不再是一个严格弱序。次正规数填的是零和最小正规值之间那段空隙，而且它不是免费的：在 Sandy Bridge 一代的 Intel 核心上，次正规的操作数或结果会陷入微码辅助，按 Agner Fog 的实测大约是 150 个时钟周期，而一次正常的 mulps 延迟是 5 个周期。 Skylake 之后去掉了其中很多情形的惩罚，但没有全部去掉 —— 所以音频和 DSP 代码至今仍然打开 FTZ 和 DAZ 标志，用一次冲零来代替这笔账。

这整套安排买到的是「够得着多远」。把 float32 和 int32 放在同一条量级的对数轴上，拖着走一遍：

两者都是 32 位。int32 够到 2.1×10⁹，而且底下每一个整数都是精确的；float32 在 10³⁸ 处还拿得住一个值，而中间的值几乎没有一个是精确的。这就是那笔交易，说一遍就够：同样的预算，花在够得远上，而不是花在分得细上。

这笔预算值得数一遍，因为它就是这一节的全部。32 个比特能命名 2³² ≈ 4.29×10⁹ 个不同的值，一个也不会多，随你怎么叫它们。int32把整笔预算花在一段连续的区间上，所以它的值处处相隔 1。float32 把其中 2²³ 个花在它 254 个正规二进制区间的每一个里面 —— 沿着这些区间走一遍，看两条计数在哪里相交：

float32 的计数是平的，int32 的每走一步翻倍，所以它们只在一处相遇：2²³ —— 同一个区间里两者都是 8,388,608 个值，间隔都是 1。再上一级，2²⁴： float32 还是 840 万个值，区间却长了一倍，间隔变成 2 —— 奇数不再存在。 §07 那张梯子就是这样数出来的。够得远在比特上不要钱，它要的是分辨率。

十分之一在二进制里是 0.000110011001100… 无限循环，就像三分之一在十进制里是 0.333… 一样。一个有 53 位有效数字的格式留下其中 53 位，把剩下的在入口处一次性舍掉。

挑一个小数，一位一位地把它的二进制位加进来。下面那根条是还差多少，画在对数刻度上，因为它每加一位就减半：

0.5、0.25、0.75 会终止，因为它们的分母是 2 的幂。 0.1 的 24 位 还是不够， 53 位也一样 —— 存下来的 double 是 0.1000000000000000055511151231257827，高出 5.55×10⁻¹⁸。

两次这样的舍入再加一次，凑出了这个主题里最有名的那一行。一步步走过去，看每根条离它当初被写成的那个十进制数有多远：

存下来的 0.1 偏高，存下来的 0.2 也偏高；它们的精确和比三分之一十高 1.67×10⁻¹⁷，而把这个和舍入成 double 又把它推到高 4.44×10⁻¹⁷。离 0.3 最近的那个 double 则低 1.11×10⁻¹⁷。两者正好差一个 ULP —— 0.1 + 0.2 == 0.3 在所有 IEEE-754 语言里都为假，原因就是这个，没有别的。

这个 ULP 不是常数。double 在零附近挤成一团，离零越远铺得越开，每过一个 2 的幂间距就翻一倍 —— 沿着曲线拖，读出每个量级上那条缝有多宽：

在 1 处缝是 2.22×10⁻¹⁶；在 10¹⁶ 处它是 2。在这个量级之上，相邻 double 之间比相邻整数之间还远，所以那上面的大多数整数干脆就不作为 double 存在。

这个交叉点有名字，也有确切的值。2⁵³ 以下每个整数都是一个 double；到了它和它之上，有效数字的位就用光了 —— 把指数往上走，看用掉的尾数位顶到这一行的末尾：

在 2⁵³ = 9,007,199,254,740,992 处，n + 1 === n 开始为真并一直为真，因为有效数字再也匀不出一位给那个一。 JavaScript 把所有数都存成 double，所以那正好是 Number.MAX_SAFE_INTEGER + 1 —— 这就是 BigInt 被加进语言的原因，也是一个把 64 位 id 当 JSON 数字返回的 API 会交回一个和它存的不一样的 id 的原因。

最后一笔代价是累积。每次加法都舍入，而循环里的这些误差并不互相抵消 —— 把一分钱加一千次，看累计误差怎么游走：

这个误差既不单调，也不被任何单次舍入界住：它在游走。 0.01 加一千次，落点比十少 1.69×10⁻¹³。这在仪表盘上什么都不是，在账本上就是一次对不上账 —— 所以钱要存成最小单位的整数计数，或者存进 decimal 类型，绝不存进 double。

小端把最低有效字节放在最低地址：x86、x86-64、默认配置下的 ARM、 Apple Silicon、RISC-V。大端把最高有效字节放在那里：PowerPC、SPARC、 IBM 主机 —— 以及每一个标准网络协议。

把 0x12345678 写进 4 个连续地址，然后切换字节序，看最低有效字节和最高有效字节各自落在哪里：

注意变的只是地址，值没有变。CPU 读自己的内存时根本看不到字节序 —— 字节序只有从机器外面才看得见，而 hex dump、抓包和磁盘上的文件，站的正是那个位置。

小端有一个很实的理由：把一个值变窄不要钱，因为低位字节本来就在最前面。在同一个地址上分别读 1 个、2 个、4 个字节：

在小端布局上读 1 个字节得到 0x78，正好是这个值模 256 —— 一次免费的截断。同样这次读取在大端布局上得到 0x12，它不是任何东西的截断：要变窄，读的人必须知道原来的宽度再加一个偏移。多精度加法的进位从低往高流，也是同一个理由。

大端的理由是它先来。ARPANET 的主机大多是大端，所以 IP、TCP、UDP、DNS 把它冻进了头部，而每一个多字节字段至今仍然那样走：

ntohs 和 ntohl 就是那次交换。在大端主机上它们编译出来什么都没有；在 x86 上它们是一条 bswap，一条指令，一个周期的延迟。 TCP 的固定头是 20 个字节，其中18 个字节是多字节整数 —— 两个端口、两个 32 位序号、窗口、校验和、紧急指针 —— 内核对每个方向的每一个段里的每一个字段都做这次交换。剩下的第 19、20 个字节是数据偏移和标志位：它们按一个字来读，但不是一个数。

这一节存在的理由是它的失败方式。让一个小端读者去读大端字节，一个个值走过去：

大多数值会大声出错：305,419,896 到达时变成 2,018,915,346。但是在 0x12121212、在零、在 0x7f7f7f7f，这次交换看不出来，两种读法完全一致。于是一个字节序 bug 会通过任何以小值或回文值做样例的测试 —— 而大多数样例正是这样 —— 然后在生产环境里遇到第一个真实值时倒下。所以每一个值得用的二进制格式都把自己的字节序写进规范： PNG、ELF、TIFF、WAV 全都写了。

选宽度回答的问题不是「能装多大」，而是能装多大而不撒谎。整数类型够得多远就精确到多远；浮点类型够得远远超过它精确的范围，而这两个数之间的差正是 bug 住的地方。

下面这张梯子对每种宽度能精确装下的最大整数取对数 —— 让宽度沿着它往上走，在右端读出它够得着多远：

注意 float32 落在哪里：它只精确到 2²⁴ = 16,777,216，比 int32 还低，尽管够得着的地方远 10²⁹ 倍。当整数用它差 128 倍，尺寸却一样。

4 行就能推出这一整页。前两行推出 abs(INT_MIN) 和绕回；后两行推出 0.1 + 0.2 和 MAX_SAFE_INTEGER：

n bits hold a residue mod 2^n
bit n-1 set: signed = unsigned-2^n
float = (-1)^s x 1.m x 2^(e-bias)
exact ints: 2^24 f32, 2^53 f64

这张梯子也是一个可以跑的测试。全篇只用一个说法：一种宽度在它第一个「装不下下面每一个整数」的 2 的幂上离开精确范围。把量级横着拖过去，float32 在 2²⁵ 处离开 —— 也就是它 24 位有效数字够得到的 2²⁴ 再上一级 —— 而同样 32 位的 int32 在 2³¹处离开：

注意 float32 比 int32 早 6 个 2 的幂就翻了脸。条子末端伸出去的那一小截就是它此刻撒谎的距离，用的是同一把 log₂ 尺。 2⁵⁴ 轮到 float64，2⁶³ 轮到 int64，到 2⁶⁴ 就没有一根还是精确的了。

• 对浮点用 ==。 它问的是「两次舍入是不是碰巧一致」。改成和按量级缩放的容差比，或者按 ULP 比。
• 对外来的 x 用 abs(x)。 在 INT_MIN 处未定义，而且它返回负数而不是抛异常。先加宽。
• 有符号值和 size_t 比较。 i < v.size() 会把有符号的 i 提升，于是一个负计数器比起来就是那个无符号类型的最大值 —— 对 32 位 unsigned 是四十亿，对 LP64 的 size_t 是 1.8×10¹⁹。
• 把钱放进 double。 存成最小单位的整数计数；循环里的误差会累积。
• fread 进带多字节字段的 struct。 跨字节序时它会成功，然后给出胡话。

这些都不稀奇：编得过、不抛异常、返回一个数。