二进制算术是怎么工作的:补码整数与 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 个位置的圆环)在编码那篇文章的模算术一节里走过。

保留低 nn 位会产生回绕:最大有符号值加一会变成最小值。语言规则可能不同于硬件结果:C/C++ 的有符号溢出属于未定义行为,无符号运算则按模回绕。INT_MAXINT_MIN 表示当前实现的 int 范围,并不一定是 32 位。Python 的 int 与 JavaScript 的 BigInt 支持任意精度;JavaScript 的 Number 使用浮点数。

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

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

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

 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 位,丢掉高半部分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 位
                            (不同)    (相同)

因此,乘积的低 nn 位可以共用有符号和无符号乘法电路。但溢出检查及语言规则仍有区别;这并不意味着 C/C++ 的有符号溢出有明确规定。

除法:移位与相减

现在来看除法。在位这一层它毫无奇异之处——就是把竖式除法用到二进制上。 回想学校里的竖式除法,比如 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=qb+r,q,rZ对任意 b0a = q \cdot b + r, \quad q,r \in \mathbb{Z} \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

nn 位被除数,这种移位减法需要 nn 次迭代。这里统计的是迭代次数,而非单个位操作:每次比较和减法也有成本。硬件除法器可能采用更快的算法,延迟取决于处理器及操作数。

向零截断的有符号除法先计算绝对值之商,操作数异号时将商取负,非零余数采用被除数的符号。Python 的向下取整除法还需要上文的调整;仅改变余数符号并不够。

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

唯一会溢出的带符号除法

对固定宽度的有符号整数,除数非零时只有一对操作数会使除法溢出:最小值除以 -1。以 32 位有符号类型为例:

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)MIN / -1 会 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} 直接跳到零——这个特性叫做渐进下溢

下面假设操作数是有限正规数,并采用舍入到最近值、恰好位于中点时取偶数。先分别处理符号、指数和有效数,再归一化并舍入到 53 位有效精度(其中 52 位小数存入字段)。零、次正规数、无穷、NaN 及溢出需要额外处理。

乘法和除法,操作数已经是 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 个尾数位,加法又舍入一次。三次舍入,误差并不互相抵消。逐位的详细走查在姊妹文章里。

这个例子说明加法不一定精确,也不一定满足结合律:在 binary64 中,(1e16 + -1e16) + 11,而 1e16 + (-1e16 + 1)0,因为内层加法舍入时丢失了 1

减法:灾难性相消的陷阱

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

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

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

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

这里的 a − b = 2⁻⁵² 是精确结果:相消本身不一定产生舍入误差。危险在于操作数已包含先前计算的误差,此时它们很小的差值可能具有很大的相对误差。

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

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

对于非负有限 binary64 值,将位模式视为无符号整数时,其顺序与数值顺序一致。对于负数,需要反转绝对值的顺序;异号比较也必须处理符号。因此,直接按无符号整数比较位模式并不适用于所有浮点数。

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

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

JavaScript 的 [NaN].includes(NaN) 返回 true,因为它使用 SameValueZero,将 NaN 视为相等,也将 +0-0 视为相等。这并非按位相等。[NaN].indexOf(NaN) 使用严格相等比较,因此返回 -1

乘法:比加法更简单

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

要计算 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 位。

加法与乘法都将精确结果舍入一次到目标格式。正确保留保护位、舍入位和粘滞位信息时,对齐指数不会增加一次独立舍入。对于任意输入,不能笼统地说其中一种运算更精确。

跟一遍 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 位的尾数乘积舍入到 53 位有效精度(52 位存储位加上隐含的首位)。

最终存下的值解码为精确的十进制 0.02000000000000000388578058618804789148271083831787109375——接近 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 步几乎总要舍入,即使操作数本身根本不需要舍入。

硬件除法可能逐位求商,也可能先近似计算倒数,具体取决于处理器。它通常比乘法慢,但确切延迟取决于体系结构。

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

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

  • 溢出:舍入后的结果需要超过上限的指数,binary64 的指数上限为 1023。舍入到最近值时,溢出产生 ±∞;定向舍入也可能返回带相应符号的最大有限值,其绝对值为 (2252)21023(2-2^{-52})2^{1023}
  • 极小结果:低于最小正规数绝对值 210222^{-1022} 时,次正规数仍可保留部分精度,最低可至 210742^{-1074};更小的结果可能舍入为零。精确的次正规结果不一定触发下溢标志。

按位布局来看(符号 | 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   (尾数非零)

例如,舍入到最近值时,1e300 * 1e300 产生无穷,1e-300 * 1e-300 则直接舍入为零。渐进下溢描述的是格式中可用的次正规值,而不是每次运算都会依次经过这些中间值。

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

除以零:Infinity,而不是异常

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

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

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

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

两套系统有何不同

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

属性固定宽度补码IEEE-754 binary64
间距相邻整数相差一随指数变化;次正规数之间固定
加法与乘法范围内精确;溢出取决于语言正确舍入到目标格式
溢出可能回绕、报错或属于未定义行为依舍入模式返回无穷或最大有限值
除以零错误处理取决于语言默认不触发陷阱时,有限非零数除以零得到无穷;0/0 得到 NaN
一种编码+0-0,数值相等

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

  • 中间结果不越界时,整数加法是精确的。溢出行为取决于语言,而不只取决于编码。
  • 浮点运算范围很广,但精度有限;舍入会让运算顺序影响结果。
  • 整数与浮点数之间的转换可能丢失信息。超过 2532^{53} 后,binary64 无法表示每个整数;浮点数转整数也取决于语言规则和目标类型范围。

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