浮點數 (Floating Point)

#csapp #data-representation #ieee-754 #concept

Overview Table

主題	核心結論	書頁
小數二進位 (fractional binary)	只能精確表示 $x \times 2^{y}$ 形式的數;如 0.1 無法精確表示	p.145-148
IEEE 754 編碼	$V = (- 1)^{s} \times M \times 2^{E}$ ,三欄位:`s` / `exp`(k bits)/ `frac`(n bits)	p.148
Normalized	exp 非全 0 非全 1; $E = e - B i a s$ 、 $M = 1 + f$ (implied leading 1)	p.149-150
Denormalized	exp 全 0; $E = 1 - B i a s$ 、 $M = f$ ;表示 0 與極接近 0 的數(gradual underflow)	p.150-151
Special values	exp 全 1:frac = 0 → $\pm \infty$ ;frac ≠ 0 → NaN	p.151
分佈特性	可表示值靠近 0 越密集;bit pattern 當 unsigned 整數比較即為浮點大小順序	p.151-153
Rounding	預設 round-to-even;另有 toward-zero / down / up 三種可求上下界	p.156-158
運算性質	`+f`、`f` 可交換 (commutative) 但不可結合 (not associative)*、乘法不可分配;具單調性 (monotonicity)	p.158-160
C 語言轉型	`float`=單精度、`double`=雙精度;float/double→int 一律 round toward zero,溢位得 TMin	p.160-161

2.4.1 小數的二進位表示 (Fractional Binary Numbers) (p.145-148)

二進位小數點 (binary point) 左側位元權重為 $2^{i}$ ,右側為 $2^{- i}$ ,是理解浮點數的第一步:

\begin{matrix} (2.19) & b = \sum_{i = - n}^{m} 2^{i} \times b_{i} \end{matrix}

權重:  2^m ... 4  2  1  .  1/2  1/4  1/8 ... 1/2^n
位元:  b_m ... b2 b1 b0 .  b-1  b-2  b-3 ...  b-n
                        ^
                   binary point
   左移小數點一位 = 除以 2;右移一位 = 乘以 2

例: ${101.11}_{2} = 4 + 1 + \frac{1}{2} + \frac{1}{4} = 5 \frac{3}{4}$
$0.111 \dots 1_{2}$ 形式表示「略小於 1」的數,書中記為 $1.0 - ϵ$
有限長度的二進位小數只能精確表示 $x \times 2^{y}$ 形式的值; $\frac{1}{5}$ (十進位為 0.2)、 $\frac{1}{3}$ 等只能逼近,越多位越準
$\frac{1}{10}$ 的二進位是無限循環 $0.000110011 [0011] \dots_{2}$ — Patriot 飛彈事件(PP 2.46)即因截斷 23 bits 累積時鐘誤差,100 小時後偏差約 0.343 秒、預測位置偏差約 687 公尺 (p.147-148)

十進位能精確表示的數,二進位不一定能。0.1、0.2 在任何有限二進位小數下都是近似值;這是浮點比較 == 常出錯的根源。

2.4.2 IEEE 浮點表示 (IEEE Floating-Point Representation) (p.148-151)

IEEE Standard 754(1985,源自 Intel 8087 與 William Kahan 的設計)將數編碼為:

V = (- 1)^{s} \times M \times 2^{E}

sign $s$ :1 bit,負數為 1
significand(有效數) $M$ :介於 $[1, 2 - ϵ)$ 或 $[0, 1 - ϵ)$ ,由 n-bit frac 欄位編碼
exponent $E$ :2 的冪次權重,由 k-bit exp 欄位編碼

Single precision (float, 32 bits):  k = 8, n = 23
 31 30       23 22                    0
+--+-----------+----------------------+
|s |   exp     |        frac          |
+--+-----------+----------------------+

Double precision (double, 64 bits):  k = 11, n = 52
 63 62         52 51                  0
+--+-------------+--------------------+
|s |    exp      |       frac         |
+--+-------------+--------------------+

依 exp 欄位的值分三種情況(Figure 2.33):

exp 欄位            分類              E             M
--------------    -------------    -----------   ---------
非全0 且 非全1  →  1. Normalized     E = e - Bias   M = 1 + f
全 0           →  2. Denormalized   E = 1 - Bias   M = f
全 1, frac = 0 →  3a. Infinity      +∞ (s=0) / -∞ (s=1)
全 1, frac ≠ 0 →  3b. NaN           "not a number"

Case 1: Normalized(最常見)

$E = e - B i a s$ ,其中 $e$ 是 exp 欄位的 unsigned 值, $B i a s = 2^{k - 1} - 1$ (single 為 127,double 為 1023)
E 範圍:single 為 $- 126 \sim + 127$ ;double 為 $- 1022 \sim + 1023$
frac 編碼小數值 $f = 0. f_{n - 1} \dots f_{1} f_{0}$ ( $0 \leq f < 1$ ),而 $M = 1 + f$
implied leading 1:因為總能調整 E 使 $1 \leq M < 2$ ,最高位的 1 不必儲存 → 免費多得 1 bit 精度

Case 2: Denormalized(exp 全 0)

$E = 1 - B i a s$ (不是 $- B i a s$ )、 $M = f$ (無 implied leading 1)
兩個用途:
- 表示 0:+0.0 是全 0 bit pattern;s=1 其餘全 0 則是 -0.0(IEEE 中 +0.0 與 -0.0「某些方面相同、某些方面不同」)
- 表示極接近 0 的數,提供 gradual underflow(漸進下溢):0 附近數值間距均勻

為何 denormalized 的 E 定為

1 - B i a s

而非

- B i a s

?為了補償 denormalized 沒有 implied leading 1,使最大 denormalized 值與最小 normalized 值平滑銜接(如 8-bit 格式中 7/512 → 8/512)。(p.150, 152)

Case 3: Special values(exp 全 1)

frac 全 0 → $+ \infty$ (s=0)或 $- \infty$ (s=1):表示溢位結果或除以 0(如 1/+0 = +∞,1/-0 = -∞)
frac 非 0 → NaN:結果無法以實數或無限表示時回傳,如 $\sqrt{- 1}$ 、 $\infty - \infty$ ;也可用來標記未初始化資料

2.4.3 範例數值 (Example Numbers) (p.151-155)

以 8-bit 格式(k=4, n=3, Bias=7)為例的關鍵值(Figure 2.35):

描述	Bit pattern	E	M	V
Zero	`0 0000 000`	−6	0	0
最小正 denormalized	`0 0000 001`	−6	1/8	1/512
最大 denormalized	`0 0000 111`	−6	7/8	7/512
最小 normalized	`0 0001 000`	−6	8/8	8/512 = 1/64
One	`0 0111 000`	0	1	1.0
最大 normalized	`0 1110 111`	7	15/8	240
Infinity	`0 1111 000`	—	—	∞

數線分佈(6-bit 格式,Figure 2.34):

 -∞ ←|——|——|——|—|—|—|-|||0|||-|—|—|—|——|——|——|→ +∞
      Normalized       Denorm.      Normalized
          可表示值不均勻分佈:越靠近 0 越密集

一般 k-bit exp / n-bit frac 格式的極值公式(Figure 2.36,務必會推):

值	Bit pattern 特徵	公式	Single 十進位
+0.0	全 0	$0$	0.0
最小正 denormalized	僅最低位是 1	$V = 2^{- n} \times 2^{- 2^{k - 1} + 2}$	$1.4 \times 10^{- 45}$
最大 denormalized	exp 全 0、frac 全 1	$V = (1 - 2^{- n}) \times 2^{- 2^{k - 1} + 2}$	$1.2 \times 10^{- 38}$
最小正 normalized	exp 最低位 1、其餘 0	$V = 2^{- 2^{k - 1} + 2}$	$1.2 \times 10^{- 38}$
1.0	exp = 011...1、frac 全 0	$1 \times 2^{0}$	1.0
最大 normalized	exp = 111...10、frac 全 1	$V = (2 - 2^{- n}) \times 2^{2^{k - 1} - 1}$	$3.4 \times 10^{38}$

整數 → 浮點編碼流程(以 12345 為例,p.155):

12345 = [11000000111001]₂
  │ 正規化:右移 binary point 13 位
  ▼
1.1000000111001₂ × 2¹³
  │ frac:去掉 leading 1,補 0 至 23 bits → 10000001110010000000000
  │ exp :13 + Bias(127) = 140 = [10001100]₂
  │ s = 0
  ▼
[0 10001100 10000001110010000000000] = 0x4640E400

位元相關性:整數表示中「最高位 1 以下的低位位元」對應浮點 frac 的高位位元(最高位 1 成為 implied leading 1)
可用整數排序浮點數:非負浮點數的 bit pattern 視為 unsigned 整數比較,大小順序與浮點值一致(IEEE 刻意設計);負數因 leading 1 呈遞減序,需額外處理 (p.153)
由 PP 2.49:n-bit frac 格式下,最小無法精確表示的正整數為 $2^{n + 1} + 1$ (single: $2^{24} + 1 = 16,777,217$ )

2.4.4 捨入 (Rounding) (p.156-158)

浮點只能近似實數,需系統性找「最接近」的可表示值 $x^{'}$ 。IEEE 定義四種捨入模式;預設為 round-to-even,其餘三種可求出保證上/下界( $x^{-} \leq x \leq x^{+}$ ):

Mode	$1.40	$1.60	$1.50	$2.50	$−1.50	性質
Round-to-even(預設)	$1	$2	$2	$2	$−2	最接近;正中間時取偶數尾數
Round-toward-zero	$1	$1	$1	$2	$−1	$\| \hat{x} \| \leq \| x \|$
Round-down	$1	$1	$1	$2	$−2	$x^{-} \leq x$
Round-up	$2	$2	$2	$3	$−1	$x \leq x^{+}$

為何取偶不恆進位? 恆進位會使一組資料平均值產生系統性統計偏差 (statistical bias);取偶使進位/捨去各約 50%
二進位規則:LSB 為 0 是偶、1 是奇。只有 bit pattern 形如

XX...X.YY...Y100...(最右 Y 為捨入位,其後恰為 1 接全 0)

才是正中間 (halfway),此時才套用取偶;否則一律取最近值
例(捨入至 1/4,即 binary point 右 2 bits): ${10.00011}_{2} \to {10.00}_{2}$ (非 halfway,取近); ${10.11100}_{2} \to {11.00}_{2}$ 、 ${10.10100}_{2} \to {10.10}_{2}$ (halfway,取偶)

判斷三步驟:(1) 捨去部分 < 一半 → 直接捨去;(2) > 一半 → 進位;(3) 恰為一半(100...0)→ 使保留部分的 LSB 為 0。

2.4.5 浮點運算 (Floating-Point Operations) (p.158-160)

IEEE 規定運算結果為「先精確計算、再捨入」:對實數運算 $⊙$ ,計算應產生 $R o u n d (x ⊙ y)$ 。此定義獨立於任何硬體實作(實務上 FPU 用技巧避免真的算出精確值,只需精度足以保證正確捨入)。

定義 $x +^{f} y = R o u n d (x + y)$ 、 $x *^{f} y = R o u n d (x \times y)$ :

性質	整數加法 (abelian group)	浮點 `+f`	浮點 `*f`
封閉性	✓	✓(可能得 $\infty$ /NaN)	✓(可能得 $\infty$ /NaN)
交換律 (commutative)	✓	✓	✓
結合律 (associative)	✓	✗	✗
單位元素	0	0	1.0
反元素 (inverse)	✓	大多有; $\pm \infty$ 、NaN 例外	—
分配律 (distributive)	✓(整數乘對加)	—	✗(乘不分配於加)
單調性 (monotonicity)	✗(unsigned/two's-complement 皆無)	✓(NaN 除外)	✓(NaN 除外)

不可結合的經典反例(single precision):

(3.14 + 1e10) - 1e10 → 0.0(3.14 被捨入吃掉);3.14 + (1e10 - 1e10) → 3.14
(1e20 * 1e20) * 1e-20 → +∞;1e20 * (1e20 * 1e-20) → 1e20
不分配:1e20 * (1e20 - 1e20) → 0.0;1e20*1e20 - 1e20*1e20 → NaN

單調性公式(a, b, c ≠ NaN):

a \geq b \Rightarrow x +^{f} a \geq x +^{f} b

a \geq b 且 c \geq 0 \Rightarrow a *^{f} c \geq b *^{f} c

a \geq b 且 c \leq 0 \Rightarrow a *^{f} c \leq b *^{f} c

a \neq NaN \Rightarrow a *^{f} a \geq 0

結合律缺失是浮點最重要的失落性質:compiler 不能把 x = a+b+c; y = b+c+d; 改寫成共用 t = b+c,因為可能改變結果 — 所以 compiler 對浮點最佳化非常保守。相對地,整數運算保有結合/交換/分配律,才允許 7*x → (x<<3)-x 這類改寫(見 02-Information-Representation/03-Integer-Arithmetic)。

2.4.6 C 語言中的浮點 (Floating Point in C) (p.160-162)

C 提供 float(單精度)與 double(雙精度);支援 IEEE 的機器使用 round-to-even 模式
C 標準不強制 IEEE 754 → 沒有標準方法改捨入模式或取得 $- 0$ 、 $\pm \infty$ 、NaN;gcc 需 #define _GNU_SOURCE 1 + #include <math.h> 才有 INFINITY、NAN 常數

轉型 (casting) 行為總表(int 為 32 bits):

轉型	溢位?	捨入?	說明
`int → float`	不會	可能(float 只有 24 bits 精度)
`int / float → double`	不會	不會	double 範圍與精度皆更大,精確保值
`double → float`	可能 → ±∞	可能	範圍與精度都縮小
`float / double → int`	可能	round toward zero(截斷)	1.999 → 1、−1.999 → −1

float/double → int 溢位時 C 標準未定義結果;Intel 相容處理器產生 integer indefinite bit pattern [10...00](即 $T M i n_{w}$ )→ (int) +1e10 得 -2147483648,正數轉出負數
Ariane 5 火箭事故(1996,p.163 aside):64-bit 浮點水平速度轉 16-bit signed int 溢位,診斷 bit pattern 被當成飛控資料,火箭升空 37 秒後解體,損失 5 億美元衛星 — 沿用 Ariane 4 程式碼而未重新驗證假設

2.5 本章總結 (Summary) (p.162-163)

電腦以 bits(組成 bytes)編碼資訊;整數用 two's-complement、實數用 IEEE 754,不同機器有不同 byte ordering 慣例
浮點編碼 $x \times 2^{y}$ 形式的數;有 single(32-bit)、double(64-bit)等精度,以及 $\pm \infty$ 與 NaN 特殊值
整數運算會 overflow;浮點會 overflow 也會 underflow(太接近 0.0 被變成 0)
整數運算保有結合/交換/分配律(compiler 可最佳化,如 (1<<k)-1 產生 k 個 1 的 mask、~x+1 == -x);浮點不滿足結合律,必須小心使用

Exam/Test Patterns

情境 / 關鍵字	答案
給 bit pattern 判斷類別	exp 非全 0 非全 1 → normalized;exp 全 0 → denormalized;exp 全 1 且 frac=0 → ±∞;exp 全 1 且 frac≠0 → NaN
求 Bias	$B i a s = 2^{k - 1} - 1$ (single 127、double 1023)
Normalized 解碼	$V = (- 1)^{s} (1 + f) \times 2^{e - B i a s}$
Denormalized 解碼	$V = (- 1)^{s} f \times 2^{1 - B i a s}$ (注意是 $1 - B i a s$ ,且無 leading 1)
最大 normalized 值公式	$(2 - 2^{- n}) \times 2^{2^{k - 1} - 1}$ ;single ≈ $3.4 \times 10^{38}$
最小正 denormalized	$2^{- n} \times 2^{- 2^{k - 1} + 2}$ ;single ≈ $1.4 \times 10^{- 45}$
最小無法精確表示的正整數	$2^{n + 1} + 1$ (single: 16,777,217)
「halfway」如何捨入	round-to-even:使結果 LSB 為 0(偶);只有捨去部分恰為 `100...0` 才算 halfway
`(3.14+1e10)-1e10 == 3.14+(1e10-1e10)` ?	否(0.0 vs 3.14)— 浮點加法不可結合
`x == (int)(float) x` 恆真?	否:float 只有 24 bits 精度,大 int 會被捨入(如 TMax)
`x == (int)(double) x` 恆真?(32-bit int)	是:double 53 bits 精度足以精確表示所有 32-bit int
`d == (double)(float) d` 恆真?	否:double → float 損失精度或溢位
`f == -(-f)`、`d*d >= 0.0` 恆真?	是:取負只翻 sign bit;平方單調 ≥ 0(浮點不像 int 的 `x*x` 會溢位成負)
`(f+d)-f == d` 恆真?	否:捨入使結合律失效(如 f=1e20, d=3.14 → 左式 0.0)
`(int) +1e10` 結果	$T M i n_{32}$ = −2147483648(Intel integer indefinite)
`1/+0`、`1/-0`、`∞−∞`、`sqrt(-1)`	$+ \infty$ 、 $- \infty$ 、NaN、NaN
為何 denormalized 用 $E = 1 - B i a s$	使最大 denorm 與最小 norm 平滑銜接(gradual underflow)
浮點可用整數指令排序?	可(非負數 bit pattern 遞增即值遞增);負數呈遞減序需特殊處理
Patriot / Ariane 5	0.1 截斷誤差累積(時鐘偏差)/ double→int16 溢位(轉換未檢查範圍)

Overview Table

2.4.1 小數的二進位表示 (Fractional Binary Numbers) (p.145-148)

2.4.2 IEEE 浮點表示 (IEEE Floating-Point Representation) (p.148-151)

Case 1: Normalized(最常見)

Case 2: Denormalized(exp 全 0)

Case 3: Special values(exp 全 1)

2.4.3 範例數值 (Example Numbers) (p.151-155)

2.4.4 捨入 (Rounding) (p.156-158)

2.4.5 浮點運算 (Floating-Point Operations) (p.158-160)

2.4.6 C 語言中的浮點 (Floating Point in C) (p.160-162)

2.5 本章總結 (Summary) (p.162-163)

Exam/Test Patterns

Related Notes