二进制算术是怎么工作的:补码整数与 IEEE-754 浮点数

你的程序执行的每一个数值运算——a + bx * ycount / 2——最终都会变成对位模式的一串位级操作。而这些位操作如何变成正确的算术结果,完全取决于这些位用的是哪种编码。

对整数,计算机使用补码:一种漂亮而简单的方案,其中带符号加法用的是与无符号加法完全相同的硬件电路——这些位既不知道也不在乎你是否把它们当成带符号的。对小数,计算机使用 IEEE-754 浮点:一套精巧得多的机制,带有各自独立的符号、指数和尾数字段,每次运算都必须对它们做对齐和舍入。

本文会把两者的算术都走一遍——在每种格式下,加、减、乘、除时这些位实际发生了什么,运算在哪里失效,以及两套系统如何对比。每种格式的编码那一面在姊妹文章里讲过:

这里我们只专注于算术运算本身,需要时会对编码做简短回顾。

补码整数的算术

我们假设你已经知道编码的基础——最高有效位(MSB)带负权重,要取一个数的相反数就把它的位取反再加 1,而且取值范围是不对称的、差一个(4 位是 -8+7,32 位是 -2,147,483,648+2,147,483,647)。如果其中有不熟悉的地方,完整的讲解在偏移二进制与补码一文里。下面用的 4 位例子只是任意 n 位宽度的替身。

加法与减法:和无符号一样

补码的第一个漂亮性质:带符号加法用的是与无符号加法相同的物理电路。 补码把每个负数 xx 存成这样一个位模式:当它被当作无符号数读取时等于 x+2nx + 2^n——例如在 4 位(n=4n = 4)里,3-3 存成 13 的位模式:x+2n=3+24=3+16=13x + 2^n = -3 + 2^4 = -3 + 16 = 13,二进制就是 1101。正因如此,把一个负数和一个正数相加常常会溢出 nn 位寄存器,但硬件只是把进位输出丢掉——带符号的答案就自动出来了。

我们看看负数相加是怎么运作的。在 4 位下追踪 -3 + 5——-3 编码为 1101(= 13),50101

    1 1 0 1     (-3,存成 13)
  + 0 1 0 1     (+5)
  ─────────
  1 0 0 1 0     (= 18;4 位装不下——前导 1 是进位输出,权重 2^4 = 16)
    0 0 1 0     (留在 4 位寄存器里:2)  ✓ 与 -3 + 5 = 2 相符

硬件只是把无符号位模式相加得到 13 + 5 = 18。第 5 个位置上的进位位(权重 24=162^4 = 16)装不进 4 位寄存器,被丢掉了。 被丢掉的那个 16 正是我们上面看到的 x+2nx + 2^n 公式里的 +2n+2^n 部分——编码偏移与溢出互相抵消,带符号的答案免费得来。 现在我们只是把这些位解释成带符号的,而硬件机制本身并不作这种区分。同样的逻辑也覆盖不溢出的情形:-7 + 41001 + 0100 = 1101,解码为 -3(带符号)或 13(无符号)。

既然减法就是加上一个相反数,它也不需要单独的电路:a - b = a + (-b),其中取相反数就是「取反再加 1」那套配方。对 5 - 3-31101,于是 0101 + 1101 = 10010。在 4 位下前导位掉了,剩下 0010 = 2——掉掉的那一位就是模运算的绕回。 完整的框架(nn 位算术是一个有 2n2^n 个位置的圆环)在编码那篇文章的模算术一节里走过。

2n2^n 这套机制带来了下面这种溢出处理:INT_MAX + 1 = INT_MIN,而 INT_MIN - 1 = INT_MAX——这不是 bug,只是模运算的一步跨过了正负两半之间的接缝。注意 INT_MAXINT_MIN 是 C/C++ 里给带符号 32 位极值 23112^{31} - 1231-2^{31} 起的名字;Java 有 Integer.MAX_VALUE/MIN_VALUE,Rust 有 i32::MAX/MIN。Python 和 JavaScript 没有,因为它们的整数类型是任意精度的。

比较:只靠位还不够的地方

与加法不同,比较确实取决于解释。位模式 1111 作为无符号数是 15,所以自然有 1111 > 0001(15 > 1)。然而,如果这同样的位本意是带符号的 -1,正确答案就是 -1 < 1——可位级比较仍然给出 1111 > 0001。同样的位,相反的答案。

在硬件层面,比较常常实现为一次减法:CPU 计算 a - b 并设置标志位(符号、零、溢出、进位);随后分支指令读取这些标志位来决定分支走向。减法本身用的就是上面那套 a + (-b) 机制——CPU 只是把结果丢掉,只留标志位。几个 4 位例子,看看每个标志位如何起作用:

 5 - 3:   0101 - 0011 = 0010    carry=0, sign=0, zero=0, overflow=0
 3 - 5:   0011 - 0101 = 1110    carry=1, sign=1, zero=0, overflow=0    (= -2 带符号)
 5 - 5:   0101 - 0101 = 0000    carry=0, sign=0, zero=1, overflow=0
-8 - 1:   1000 - 0001 = 0111    carry=0, sign=0, zero=0, overflow=1    (= -9,装不下)

看第一行,5 - 3 = 2,每个标志位都是 0carry = 0,因为无符号减法留在范围内(5 ≥ 3);sign = 0,因为结果(0010)的 MSB 是 0zero = 0,因为结果非零;overflow = 0,因为 +2 轻松装进 4 位带符号范围。其余各行各翻转一个标志位:carry 在无符号减法绕过零时点亮(第 2 行:3 < 5,所以结果是一个负数的补码编码);sign 在结果的 MSB 为 1 时点亮(第 2 行的 1110);zero 在两个操作数相等时点亮(第 3 行);overflow 在带符号结果落到 4 位带符号范围之外时点亮(第 4 行:-8 - 1 = -9 下溢到最小值 -8 以下)。

因为同样的位在带符号和无符号下可以有不同含义,CPU 提供了两套分支指令族——带符号的(x86 上的 JLJG,即「小于/大于则跳转」)和无符号的(JBJA,即「低于/高于则跳转」)——各自读取不同的标志位组合:

比较无符号带符号
a < bJB: carry = 1JL: sign ⊕ overflow = 1
a > bJA: carry = 0 ∧ zero = 0JG: sign ⊕ overflow = 0 ∧ zero = 0
a ≤ bJBE: carry = 1 ∨ zero = 1JLE: sign ⊕ overflow = 1 ∨ zero = 1
a ≥ bJAE: carry = 0JGE: sign ⊕ overflow = 0

这些条件里, 是逻辑异或(恰好一个输入为 1), 是逻辑与(两个输入都为 1), 是逻辑或(至少一个输入为 1)。 编译器根据声明的类型挑选正确的变体。

实际运作,同样是 4 位(每一行的标志条件都满足,所以分支被采纳):

  JB  (1 < 2  无符号):     0001 - 0010 = 1111    carry = 1
  JA  (3 > 2  无符号):     0011 - 0010 = 0001    carry = 0, zero = 0
  JL  (-1 < 1 带符号):     1111 - 0001 = 1110    sign ⊕ overflow = 1 ⊕ 0 = 1
  JG  (3 > 2  带符号):     0011 - 0010 = 0001    sign ⊕ overflow = 0 ⊕ 0 = 0, zero = 0

每行的右半部分读作 公式 → 代入的标志值 → 布尔结果。看 JL 那行:减法 1111 - 0001 = 1110 得到 sign = 1(结果的 MSB)和 overflow = 0(带符号值 -2 在 4 位里仍装得下),所以 sign ⊕ overflow 变成 1 ⊕ 0,求值为 1——正是 JL 的触发条件。JG 那行同理,sign = 0overflow = 0,给出 0 ⊕ 0 = 0(加上 zero = 0),这就是 JG 的触发条件。

相等(a == b,指令 JE)及其否定(JNE)只读零标志位,带符号和无符号完全一样。

乘法:移位与相加

回想小学的竖式乘法:对其中一个操作数的每一位数字,把它乘上另一个操作数,把得到的那一行按该位数字的位置移位,再把所有行加起来。例如 123 × 456

        1 2 3              (a = 123)
      × 4 5 6              (b = 456)
      ─────────
        7 3 8              ← 123 × 6(6 在位置 0,不移位)
      6 1 5                ← 123 × 5,向左移一位(5 在位置 1)
    4 9 2                  ← 123 × 4,向左移两位(4 在位置 2)
    ─────────
    5 6 0 8 8              = 56088

二进制的做法一样,但有一个大简化:乘数的每一位要么是 0,要么是 1。于是每一行要么是被乘数 a 的移位副本(当乘数位为 1 时),要么就是零(当该位为 0 时)——没有像十进制那样逐位相乘的步骤。就好像每次乘法的对象都是一个只由 10 构成的十进制数——比如 25 × 101

        2 5               (a = 25)
      × 1 0 1             (b = 101)
      ─────────
        2 5               ← 数位 0 = 1:加 25
      0 0                 ← 数位 1 = 0:跳过
    2 5                   ← 数位 2 = 1:加左移 2 位的 25(= 2500)
    ─────────
    2 5 2 5               = 2525

注意这里根本没有真正的数位相乘——每一行要么是移到自己位置上的 25,要么就是 0。而移位本身只是在低端补零:25 左移 2 位就是 2500,末尾接了两个零(二进制里同样的移位把 0011 变成 1100)。 于是整个运算就归约成「要么加上一份补零后的 a,要么跳过」。 正是这个性质让二进制乘法如此便宜:二进制里乘数的数位永远取自 {0, 1},所以无论操作数是什么,每一行都塌缩成同一个「移位还是零」的选择。

下面是 4 位下的 3 × 50011 × 0101),走同一套算法:

        0 0 1 1           (a = 3)
      × 0 1 0 1           (b = 5)
      ─────────
        0 0 1 1           ← 位 0 = 1:加 a
      0 0 0 0             ← 位 1 = 0:跳过
    0 0 1 1               ← 位 2 = 1:加 a ≪ 2
  0 0 0 0                 ← 位 3 = 0:跳过
  ─────────────────
  0 0 0 0 1 1 1 1         = 15

逐行的排布让人以为需要 n 个顺序步骤——但 CPU 并不需要它们按顺序来。每一行只依赖 ab 的某一位,不依赖任何前一行的结果,所以全部 n 行都可以并行算出。要产出第 i 行,硬件把 a 左移 i 位(该行的位置),然后要么保留移位后的值(若 b[i]1),要么把它换成全零(若 b[i]0)。 这 n 个部分积随后由一棵并行加法器树(WallaceDadda)求和,代价是 O(logn)O(\log n) 的门延迟——与串行移位相加乘法器的 O(n)O(n) 个周期形成对比。

在硬件里,这变成一棵并行的树:b 拆成它的各个位,每一位是一条分支,每条分支决定 0 还是 1。若为 1,该分支贡献按其位置移位后的 a;若为 0,则贡献零。 所有分支并行运行,随后一棵加法器树把它们加起来。

a = 0011(= 3)、b = 0101(= 5),计算过程长这样:

              a = 0011 (广播到每条分支)

  ┌───────────┼───────────┬───────────┬───────────┐
  │           │           │           │           │
  ▼           ▼           ▼           ▼
a ≪ 0       a ≪ 1       a ≪ 2       a ≪ 3            ← 按分支下标移位
= 00000011  = 00000110  = 00001100  = 00011000        (结果在 8 位字段中)
  │           │           │           │
  × b₀=1      × b₁=0      × b₂=1      × b₃=0          ← 用那一位 b 做门控
  │           │           │           │                 (若 bᵢ=0,输出 = 0;
  ▼           ▼           ▼           ▼                 若 bᵢ=1,输出 = a≪i)
00000011    00000000    00001100    00000000
(partial₀)  (partial₁)  (partial₂)  (partial₃)
  │           │           │           │
  └───────────┴─────┬─────┴───────────┘


       ┌────────────────────────────┐
       │  parallel adder tree       │   ← 门深度 O(log n)
       │  sum = 00001111 = 15       │
       └──────────────┬─────────────┘


                  P = 00001111 = 15                ← 2n 位的乘积 (= a × b)

有一个值得知道的实际陷阱——乘法可能悄无声息地溢出,哪怕操作数离类型最大值还差得远。原因在于乘积需要 2n2n,而不是 nn 位:4 位 × 4 位时,最大乘积是 15×15=225=1110000115 \times 15 = 225 = \texttt{11100001},会溢到 8 位;8 位 × 8 位时,255×255=65,025255 \times 255 = 65{,}025 需要 16 位。不同语言的处理方式各不相同:

策略溢出时的行为示例
静默截断保留低 n 位,丢掉高半部分C/Java int * int → int;release 下的 Rust i32 * i32
更宽的类型先提升操作数,让全部 2n 位都装得下C:(int64_t)a * (int64_t)b;Java:(long)a * b
检查 / 陷入检测溢出,返回错误或 panicRust a.checked_mul(b)Option;debug 模式下 * 会 panic
饱和夹到类型的 MAX/MIN,而不是绕回Rust a.saturating_mul(b)
任意精度用一个会增长的类型——根本不会溢出Python int、JavaScript BigInt、Java BigInteger

带符号乘法

与加法不同,带符号和无符号的乘法用同一套算法并不能那么直截了当地奏效。原因是在补码里,乘数的 MSB 带的是权重——所以当它为 1 时,那一行的贡献应当被减去而不是加上。例如取 b = 1110a = 3:作为无符号读,b = 14,所有行都相加(0 + 6 + 12 + 24 = 42,与 3 × 14 相符);作为带符号读,b = -2,MSB 那一行改为减去(0 + 6 + 12 − 24 = -6,与 3 × -2 相符)。同样的操作数位,只有一行的符号翻转了。

所以上面的算法需要做几处调整:对符号位那一行减去(而不是加上)部分积,并把每个部分积按符号扩展到完整的 2n2n 位宽度,让负的贡献能正确地传播进高半部分。把 3 × -20011 × 1110)按这套配方跑一遍:

        0 0 1 1                  (a = 3)
      × 1 1 1 0                  (b = -2 带符号)
      ─────────
  0 0 0 0 0 0 0 0    ← 位 0 = 0:跳过
  0 0 0 0 0 1 1 0    ← 位 1 = 1:加 a ≪ 1
  0 0 0 0 1 1 0 0    ← 位 2 = 1:加 a ≪ 2
  1 1 1 0 1 0 0 0    ← 位 3 = 1(MSB!):减 a ≪ 3(= -24,以 8 位补码编码)
  ─────────────────
  1 1 1 1 1 0 1 0    = -6(带符号)  ✓

带符号与无符号的分歧完全住在完整 2n2n 位乘积的高 nn 位里——nn 位两种读法下都一样。例如,用同样的操作数位 0011 × 1110

  无符号 (3 × 14 = 42):     0 0 1 0  |  1 0 1 0
  带符号 (3 × -2 = -6):     1 1 1 1  |  1 0 1 0
                            ───────     ───────
                            高 n 位     低 n 位
                            (不同)    (相同)

这就是为什么同宽度的乘法(int * int → int)在语言层面不需要分开的带符号/无符号变体:它只是低 n 位,溢出时像加法一样绕回(没有除法那种 INT_MIN / -1 式的特殊病态情形)。

除法:移位与相减

现在来看除法。在位这一层它毫无奇异之处——就是把竖式除法用到二进制上。 回想学校里的竖式除法,比如 105 ÷ 7

      1 5
    ─────
7 │ 1 0 5
      7
    ─────
      3 5
      3 5
    ─────
        0

为了计算,我们从左到右走过被除数(105)的各位。每一步都问「除数(7)能装进目前手上的数几次?」,减去那么多次,把下一位挪下来,再重复。

二进制除法的做法完全一样,只是「几次?」这个问题只有两个可能答案:01——除数要么装进去一次,要么根本装不进去。这就是关键的简化。 在十进制里,每一步都需要真正的计算(或估算)才能定下一个 0–9 的数字——你得弄清除数能装进多少,这在一般情况下需要乘法和试错。

在二进制里没什么要算的:把当前余数与除数做一次比较,答案就直接出来了——装得进就是 1,装不进就是 0 不需要乘法表,不需要试错,每一位只有一个「减还是不减」的决定。这就是二进制竖式除法能如此干净地映射到硬件的原因:顶层循环遍历被除数的各位,而每次迭代只是一个比较器加一次条件减法——仅此而已。

再回想比较那一节:比较器是用减法实现的,R ≥ D 就是 R − D 加上一次符号位或进位位的检查。 所以每次循环迭代硬件都会推测性地计算 R − D:如果结果非负(没有借位),就把它提交回 R 并在 Q 中记下 1;否则把结果丢掉并记下 0。每次迭代总是一次减法。

CPU 保有两个寄存器:R 存放当前余数,Q 逐位累积商。 每一步它把 R 左移并移入被除数的下一位,然后总是通过计算 R − D 来把 RD 作比较。根据结果:

  • 如果 R − D 非负(D 装得进)→ 把新的 Q 位置为 1,并用该结果替换 R
  • 如果 R − D 为负(D 装不进)→ 把新的 Q 位置为 0,丢弃结果,R 保持不变

看个例子:4 位下的 13 ÷ 3,被除数 1310=1101213_{10} = 1101_2,除数 310=001123_{10} = 0011_2。 逐步点击下面的小组件,可以并排看到两种呈现——左边是学校式的竖式除法,右边是 CPU 的移位寄存器轨迹。 组件显示四行寄存器:Ds 是除数(正文里我们一直叫它 D),Dd 是被除数,R 是当前余数,Q 是逐位构建出来的商。心智模型:Dd 是喂进 R 的输入位流(每一拍移入被除数的下一位);DsR 用来比较的静态参照;RQ 是工作寄存器,每一拍都左移。

School long division
CPU shift-register trace
Ds
0011
= 3
Dd
1101
= 13
R
0000
= 0 (remainder)
Q
0000
= 0 (quotient)
 
if R < Ds
no subtract · Q bit = 0
if R ≥ Ds
subtract (R ← R − Ds) · Q bit = 1
 
Step 0 / 13

上面的组件有 14 个状态——每拍都是一致的 3 个子阶段结构(移位 R、比较/相减、移位 Q)。下面的轨迹对应组件信息面板中显示的每步文字:

Step 0   — Init. Ds = 0011 (3), R = 0000, Q = 0000.

第 1 拍 — 位 3 = 1(不减)
    Step 1   — (a) 移位 R:位 3 移入 → R = 0001。还未比较。
    Step 2   — (b) 比较:1 < 3 → 不减。点亮「R < D」分支。
    Step 3   — (c) 移位 Q:Q = 0000。商的第一位数字 = 0。

第 2 拍 — 位 2 = 1(减法触发)
    Step 4   — (a) 移位 R:位 2 移入 → R = 0011(中间态,可见)。
    Step 5   — (b) 比较:3 ≥ 3 → 点亮「R ≥ D」分支;下一次点击时才会做减法。
    Step 6   — (c) 相减 + 移位 Q:R = 0011 − 0011 = 0000;Q = 0001。学校那一侧出现「1 1」行。

第 3 拍 — 位 1 = 0(不减)
    Step 7   — (a) 移位 R:位 1 移入 → R = 0000。
    Step 8   — (b) 比较:0 < 3 → 不减。
    Step 9   — (c) 移位 Q:Q = 0010。商的第三位数字 = 0。

第 4 拍 — 位 0 = 1,最低位(不减)
    Step 10  — (a) 移位 R:位 0 移入 → R = 0001。
    Step 11  — (b) 比较:1 < 3 → 不减。
    Step 12  — (c) 移位 Q:Q = 0100。商的第四位数字 = 0。

Step 13  — Done. Q = 0100 (= 4), R = 0001 (= 1). 13 ÷ 3 = 4 余 1。

走完 n 步(每位一步)之后,你就有了完整的商。不管 CPU 在一趟运行结束时落在哪个 Q 和 R 上,它们由构造方式就满足一个严格的恒等式:

(a/b)b+(amodb)=a对任意 b0(a / b) \cdot b + (a \bmod b) = a \quad \text{对任意 } b \neq 0

这个恒等式不是额外加的规则——它就是余数的定义:R 是循环把 D 尽可能多次减掉之后剩下的东西。组件给出的 Q = 4, R = 1 是个平凡的验算:4 · 3 + 1 = 13。移位相减在一趟里同时产出 a / ba % b——两个结果一起掉出来。

只要 Q 和 R 都装得进寄存器,各种实现都保持这个恒等式。当真正的商不是整数时,就得对它做舍入——而各语言走了两条路:

  • 向零截断(C99/C++、Rust、Java、Go):a / b 向零舍入;余数继承被除数的符号。
  • 向下取整除法(Python):a // b-\infty 舍入;余数继承除数的符号。

a = -17b = 5 为例(真正的商是 3.4-3.4):

C:       -17 / 5  = -3     -17 % 5 = -2    (-3) * 5 + (-2) = -17   ✓
Python:  -17 // 5 = -4     -17 % 5 =  3    (-4) * 5 +  3   = -17   ✓

两者都满足恒等式;它们只在舍入方向上不同。上面那套移位相减算法直接产出截断除法——它在绝对值上运作,并在边界处重新施加符号。向下取整除法只是事后的小修正:如果两个操作数符号不同且余数非零,就把商减 1,并给余数加上 b

正如我们刚看到的,移位相减算法每位跑一次循环迭代,这让整数除法对 n 位数来说是 O(n) 的操作——明显慢于加法或乘法,这也是为什么即便现代 CPU 执行一条 idiv 指令也要花许多周期。较简单的架构有时用软件循环而不是专用硬件来实现它,而现代 CPU 则弃用朴素的移位相减,转向更快的算法——SRT 除法牛顿–拉弗森Goldschmidt——它们把除法归约为少数几次乘法,因为乘法在硬件里便宜得多。

带符号除法是同一套算法跑在操作数的绝对值上,符号在循环前后修正——如果恰好一个操作数为负,商就取相反数,而余数取被除数的符号(C/C++)或除数的符号(Python)。

这对每一对操作数都干净地成立——只有一个边界情形除外。

唯一会溢出的带符号除法

加法溢出在「绕回有明确定义」这个意义上是可修补的。但补码里恰好有一个算术运算根本没有任何合理答案:用最小值除以 -1

INT_MIN÷1=INT_MIN=+231\text{INT\_MIN} \div -1 = -\text{INT\_MIN} = +2^{31}

那正是 INT_MAX + 1,或者 (2^31 − 1) + 1 = 2^31,比最大可表示的带符号值大一。 这个结果在任何 32 位补码位模式里都字面上无法表示。 没有哪种绕回能给出正确答案——2312^{31} 在这个格式里就是不存在。

这是范围不对称差一的直接后果。INT_MIN 之外,每个负整数都有配对的正数;INT_MIN 是唯一的例外。试图取它的相反数(通过一元 - 或者除以 -1)就是在索要一个格式产不出来的值。

不同系统的处理各不相同:

系统行为
x86 CPU(直接执行)除法溢出异常(在 Unix 上程序通过 SIGFPE 崩溃)
C / C++未定义行为——编译器可以假定它永不发生
Java有定义:Integer.MIN_VALUE / -1 == Integer.MIN_VALUE(绕回到自身)
Python不成问题——int 是任意精度的
Rust(debug)带溢出消息 panic
Rust(release)依编译设置绕回或 panic

它们都必须做个选择,因为数学上的答案根本装不进那个位模式——这里没有行为良好的退路。

IEEE-754 浮点数的算术

浮点算术完全是另一头野兽。IEEE-754 给你的不是补码那个干净的模运算世界,而是一张可表示值的网格,其间距每当指数增加一就翻倍——靠近零处密集,靠近极端处稀疏。每次运算都必须对齐指数、做底层的数学、把结果重新规格化,再舍入到能装进尾数。

我们假设你已经知道 IEEE-754 binary64 的布局——1 个符号位、11 个带偏移的指数位、52 个尾数位、隐含的前导 1。如果这是新东西,完整的拆解在JavaScript 的 Number 与 Python 的 float 是怎么存数字的一文里。这里我们从那篇文章结束的地方接着讲——格式已经定下了;那么当你对两个这样的数做算术时会发生什么。

关于术语的一点说明

下面会出现的一个术语是次正规数(有时也叫非规格化数):一个非常小的浮点数,比最小的正规值 210222^{-1022} 还小。正规浮点数的形式是 1.xxx × 2e2^e,带隐含的前导 1;次正规数丢掉那个隐含的 1,用全零指数和非零尾数来编码。这让 IEEE-754 能一路平缓地表示到大约 210742^{-1074},而不是从 210222^{-1022} 直接跳到零——这个特性叫做渐进下溢

四种算术运算都遵循同一个骨架:三个字段(符号、指数、尾数)各自单独处理,然后结果被规格化(强行回到 1.xxx × 2^e 的形式)并舍入到能装进 52 个尾数位。

乘法和除法,操作数已经是 1.xxx × 2^e 的形式,所以运算可以直接进行:符号做异或,指数相加(乘)或相减(除),尾数相乘或相除。三步:运算 → 规格化 → 舍入

加法和减法,还有一个额外的前奏步骤——对齐——因为把值相加要求它们处在同一尺度上。较小操作数的尾数被右移,直到两个指数相等,然后尾数才被合并;结果的符号来自绝对值较大的那个操作数。四步:对齐 → 运算 → 规格化 → 舍入

现在我们来详细走一遍每个运算,从加法开始。

加法:对齐、相加、规格化、舍入

把两个浮点数相加比把两个整数相加繁琐得多。五个步骤是:

  1. 比较指数。 取较大的那个作为参照指数。
  2. 对齐尾数。 把较小操作数的尾数右移,使两个尾数表示的值处在同一指数下。这可能把一些位挤出右端(它们成为用于正确舍入的 guard、round 和 sticky 位)。
  3. 把对齐后的尾数相加。 就是两者的普通二进制加法(包括隐含的前导 1)。
  4. 重新规格化。 如果和溢进了下一个指数(例如 1.1 + 1.1 = 11.0,需要写成 1.10 × 2^1),就把尾数右移并把指数加一。如果和小于规格化形式(减法中的相消),就左移并把指数减一。
  5. 舍入。 重新规格化后的尾数通常比 52 位字段允许的位数更多。按 IEEE-754 的默认规则——舍入到最近值,平局取偶——舍入到最近的可表示值。

只要详细跟一遍那个著名案例,就能看到所有这些步骤如何施行:0.1 + 0.2 算出来是 0.30000000000000004 而不是 0.30.10.2 都是无限循环的二进制小数(就像十进制里 1/30.333…0.1=0.0001120.1 = 0.0\overline{0011}_2),所以存储时各自都被舍入到 52 个尾数位,加法又舍入一次。三次舍入,误差并不互相抵消。逐位的详细走查在姊妹文章里。

有了这个例子就能看出:浮点加法既不满足结合律,也不精确。三次舍入给出的答案与对同一数学结果只舍入一次不同。这就是 (a + b) + ca + (b + c) 可能产出不同浮点结果的原因。

减法:灾难性相消的陷阱

浮点减法遵循与加法相同的「对齐—相加—规格化—舍入」舞步,但多了一层顾虑:灾难性相消

当两个几乎相等的浮点数相减时,前导位互相抵消。重新规格化那一步于是要左移很多位,把原本属于操作数最低有效(因而最不精确)部分的低位「拉上来」。

binary64 里的例子:两个只在最后一个尾数位上不同的 double:

  • a = 1.0000…0001 × 2⁰(尾数:51 个零然后一个 1;等于 1 + 2⁻⁵²
  • b = 1.0000…0000 × 2⁰(尾数:全零;等于 1.0

a − b = 0.0000…0001 × 2⁰,重新规格化为 1.0 × 2⁻⁵²。52 个前导尾数位相消掉了,而最低那一位——本来就已在精度极限上——成了整个结果。如果 a 本身就是某个上游计算舍入后的输出,那么最低那一位基本上是舍入噪声,而减法刚刚把它提升到了最高有效的位置。

这就是数值代码常常重构公式以避免相减两个几乎相等的值的原因——相消能把一个微小的舍入误差变成一个实际上没有任何有效数字的结果。

比较:位序管用(差不多)

浮点数比较几乎和整数比较一样简单:对非特殊值来说,按位模式比较两个浮点数,和比较它们的数值给出相同答案。这是因为 IEEE-754 把符号放在 MSB,然后是指数,然后是尾数——所以(按符号-数值读的)较大位模式对应较大的浮点数。CPU 用一条硬件指令就能比较两个浮点数。

但有两种特殊情形打破了这个简单规则:

  • NaN 与一切都不相等,包括它自己。 NaN == NaN 求值为 false。这是有意为之——NaN 表示「没有有效的数」,所以它不能等于任何东西。排序算法和哈希表必须对 NaN 特殊处理。
  • +0 == -0,尽管它们的符号位不同。这两个零在数值上比较为相等,但它们并不完全可以互换:1 / +0 给出 +∞,而 1 / -0 给出 -∞

这些会在意想不到的地方冒出来。在 JavaScript 里,[NaN].includes(NaN)true(语言规范在那里用的是位相等),但 [NaN].indexOf(NaN)-1(用的是 ===,它遵守 IEEE-754 的规则)。而在大多数语言里,if (x == x) 是判断「x 不是 NaN 吗?」的标准惯用写法。

乘法:比加法更简单

出人意料的是,浮点乘法比加法更简单,因为你不需要对齐指数。

要计算 a × b

  1. 把尾数相乘(包括隐含的前导 1)。每个尾数至少为 1(因为隐含的前导位是 1)且小于 2(任何 ≥ 2 的东西都会被重新规格化到更高的指数)。所以它们的乘积至少为 1 且小于 4(最小 1 × 1 = 1;最大略低于 2 × 2 = 4),这意味着结果要么已经规格化(1.xxx),要么大了一位(1x.xxx)。
  2. 把真实指数相加。 带偏移的指数必须先去偏移,再重新加上偏移:(e11023)+(e21023)+1023=e1+e21023(e_1 - 1023) + (e_2 - 1023) + 1023 = e_1 + e_2 - 1023
  3. 把符号位做异或。 正 × 负 = 负,如此类推。
  4. 必要时重新规格化。 如果尾数乘积溢出成 1x.xxx,就右移 1 位并给指数加 1。
  5. 把尾数舍入到 52 位。

不需要对齐意味着只有一个舍入误差来源(第 5 步),加上操作数里本来就有的误差。所以当两者都在刚舍入过的输入上计算时,a × b 通常比 a + b 更准确。

跟一遍 0.1 × 0.2 就能看到这些步骤如何施行,它算出来是 0.020000000000000004 而不是 0.020.10.2 都舍入到同一个 52 位尾数(就是我们之前见过的那个无限循环二进制),只在指数上不同:

  • 0.11.10011001…10011010 × 242^{-4}(52 位)
  • 0.21.10011001…10011010 × 232^{-3}(52 位)

跑一遍五个步骤:

  1. 把尾数相乘。 每个尾数解码出来大约是十进制的 1.6(二进制的 1.10011001…100110108/5 = 1.6 最接近的 53 位近似)。两个 53 位值的完整乘法产出最多 106 位,值约为 1.6 × 1.6 = 2.56。由于 2.56 ≥ 2,结果是 1x.xxx 形式,需要重新规格化。
  2. 把真实指数相加: 4+3=7-4 + -3 = -7
  3. 把符号做异或: 正 × 正 = 正。
  4. 重新规格化。 尾数乘积是 1x.xxx 形式,所以右移 1 位(尾数变成约 1.28),并把指数从 7-7 抬到 6-6
  5. 106 位的尾数乘积舍入到 52 位。

最终存下的值解码为精确的十进制 0.0200000000000000004163336342344337026588618755340576171875——接近 0.02,但不相等。0.10.2 里的舍入误差被带进了乘积,而乘积本身又舍入了一次。

除法:很少精确

浮点除法照搬乘法的五步结构,只是运算方向反过来:

  1. 把尾数相除。 每个尾数至少为 1 且小于 2,所以商的尾数至少为 0.5 且小于 2——要么已经规格化(1.xxx),要么小了一位(0.xxx)。
  2. 把真实指数相减。 和乘法一样的「去偏移再加回偏移」舞步:(e11023)(e21023)+1023=e1e2+1023(e_1 - 1023) - (e_2 - 1023) + 1023 = e_1 - e_2 + 1023
  3. 把符号位做异或。 负 / 正 = 负,如此类推。
  4. 必要时重新规格化。 如果商的尾数是 0.xxx,就左移 1 位并把指数减一。
  5. 把尾数舍入到 52 位。

与乘法的最大区别:除法很少精确。两个 53 位的值可能产出一个需要无穷多位才能表示的商——哪怕两个操作数都很简单。例如 1.0 / 3.0 就是十进制 1/3 = 0.333… 的二进制对应物:一个必须被舍入的无限循环二进制小数。所以第 5 步几乎总要舍入,即使操作数本身根本不需要舍入。

现代 CPU 用的正是前面为整数除法提过的那套 牛顿–拉弗森 / Goldschmidt 迭代来实现浮点除法,把它归约为几次乘法——但除法通常仍是四种基本浮点运算中最慢的。

上溢与下溢:无穷和零,而不是绕回

与补码整数不同,浮点数在上溢时不会绕回。IEEE-754 为「太大」和「太小」的结果保留了特殊的位模式:

  • 上溢 → 指数会超过最大可表示值 210232^{1023}。结果变成 ±\pm\infty,编码为全一指数配全零尾数。
  • 下溢 → 指数会掉到最小值以下(正规数为 210222^{-1022})。结果变成一个次正规数(尾数没有隐含的前导 1,允许精度逐步流失),或最终变成 ±0\pm 0

按位布局来看(符号 | 11 个指数位 | 52 个尾数位):

+∞          :  0 | 11111111111 | 0000…0000
-∞          :  1 | 11111111111 | 0000…0000
+0          :  0 | 00000000000 | 0000…0000
-0          :  1 | 00000000000 | 0000…0000
subnormal   :  s | 00000000000 | xxxx…xxxx   (尾数非零;没有隐含的前导 1)
NaN         :  s | 11111111111 | xxxx…xxxx   (尾数非零)

所以 double 里的 1e300 × 1e300 产出 Infinity,而不是某个绕回后的位模式。而 1e-300 × 1e-300 会穿过次正规数下溢到零。

特殊值的位模式全都住在指数范围的两个极端上,这也正是当初为指数字段选择偏移二进制的原因:它把全零和全一的指数模式放在边界上,在那里做保留是自然的。

除以零:Infinity,而不是异常

整数除以零在大多数语言里会陷入陷阱或抛出异常。浮点除以零不会——它产出 ±Infinity

> 1 / 0
Infinity
> -1 / 0
-Infinity

Python 是个例外(它在语言层抛出 ZeroDivisionError),但底层的 IEEE-754 算术产出的是 Infinity;Python 只是把它拦下来了。在 JavaScript 里你拿到的是原始行为。

0 / 0 是另一回事——它产出 NaN,那个「不是数」的特殊值,它会在后续算术中传播,并且与一切都不相等,包括它自己。

两套系统有何不同

把两套系统都摊开之后,对比就很鲜明了。整数算术和浮点算术在位这一层几乎毫无共同之处,而这些差异在实践中很要紧:

方面补码整数IEEE-754 浮点数
位间距均匀——每个整数相隔 1对数式——靠近零处密度最高,靠近极端处稀疏
加法精确、可交换、可结合有舍入;可结合只是巧合
乘法范围内精确,溢出绕回每次运算舍入一次
上溢2^n 取模绕回饱和到 ±Infinity
下溢不适用(整数没有下溢)经次正规数逐步下溢,然后 ±0
除以零异常 / 未定义±Infinity0/0 则为 NaN
符号性编码在位里(MSB 约定)显式的符号位;+0-0 都存在
相等逐位精确;x == x 永真大体逐位精确;NaN != NaN 是例外

对大多数应用代码来说,这些差异表现为日常的怪脾气:

  • 整数可预测但狭窄。 加法可结合且精确,所以 (a + b) + c == a + (b + c) 永远成立。但一旦踏出范围,你就会绕回(或者崩溃,取决于语言)。
  • 浮点数宽广但不精确。 你可以表示从 1030810^{-308}1030810^{308} 的值,但其中只有很少数是精确的。每次运算都舍入,而舍入误差的累积方式取决于运算顺序。
  • 混用它们需要小心。 把一个大的 int64 转成 float64 会在超过 2532^{53} 后丢失精度(安全整数边界)。把一个大浮点数转成整数会截断。一般来说两者都不可逆。

在这些日常观察之下,有四个更深的点值得记住:

  1. 补码整数算术是模的。 每次运算都在模 2n2^n 下发生,这就是加法和减法用同一个电路、以及 INT_MAX + 1 = INT_MIN 的原因。不对称的范围(多出一个负数)给了你 INT_MIN / -1 这个边界情形,那里真正的结果根本没有任何位模式。
  2. 浮点算术就是对齐—相加—规格化—舍入。 对两个浮点数的每次运算都涉及重新对齐它们的指数(对加法而言)、执行数学、重新规格化结果,并舍入到 52 个尾数位。每一步都可能引入误差,这就是浮点结果很少逐位精确的原因。
  3. 上溢的行为完全不同。 整数绕回;浮点数饱和到无穷。这不是个表面选择——它反映了这两个数空间根本不同的结构(平坦的模空间对上带保留端点的对数空间)。
  4. 携带含义的不是位,而是类型。 同样的 32 位可以是 int 也可以是 float,取决于程序怎么决定。补码加法和浮点加法是完全不同的两种运算,只是碰巧用了同样的 32 位内存。

知道自己身处哪套算术系统(以及它的怪脾气),通常比知道你那些数字的具体编码更重要。当一次计算给出意外答案时,问「这是哪套系统处理的?」通常是通往答案最快的路。