整數算術 (Integer Arithmetic)

Overview Table

2.3.1 Unsigned 加法 (p.120-126)

兩個 w-bit 非負整數 $0\le x,y<2^w$ 相加,真實總和範圍是 $0\le x+y\le 2^{w+1}-2$,可能需要 w+1 bits。若持續保留完整結果會造成「word size inflation」(字長無限膨脹),故 C 等語言採固定字長算術:把總和截斷 (truncate) 為 w bits,等價於 mod $2^w$ 的模運算(Lisp 等語言則支援任意精度整數,為例外)。

公式(Eq. 2.11):

 真實和 x+y                     w-bit unsigned 和
 2^(w+1) ─┐
          │ Overflow ──── 減去 2^w ────┐
 2^w     ─┤                           ├─ 2^w
          │ Normal  ──── 原值不變 ────┤
 0       ─┘                           └─ 0

• 範例(w=4):9 + 12 = 21 = [10101],丟棄最高位得 [0101] = 5 = 21 mod 16。
• Overflow 偵測原理:令 $s=x{+}_w^{u}y$,則 overflow 發生 若且唯若 $s<x$(等價於 $s<y$)。推導:未溢位時 $s=x+y\ge x$;溢位時 $s=x+(y-2^w)<x$,因為 $y-2^w<0$。
• C 語言中 unsigned overflow 不會發出任何錯誤訊號,程式須自行檢查。
• Unsigned 取負(Eq. 2.12):模加法構成 abelian group(交換、結合、單位元素 0、每個元素有加法反元素):

2.3.2 Two's-Complement 加法 (p.126-131)

有號數 $-2^{w-1}\le x,y\le 2^{w-1}-1$ 的真實和範圍是 $-2^w\le x+y\le 2^w-2$,同樣截斷成 w bits。結果分三種情況(Eq. 2.13):

 真實和 x+y                    w-bit two's-complement 和
 +2^w    ─┐
          │ Positive overflow ── 減 2^w ──┐
 +2^(w-1)─┤                              ├─ +2^(w-1)
          │                              │
       0 ─┤ Normal ────── 原值不變 ──────┤─ 0
          │                              │
 -2^(w-1)─┤                              ├─ -2^(w-1)
          │ Negative overflow ─ 加 2^w ──┘
 -2^w    ─┘

• 位元層級:two's-complement 和與 unsigned 和的位元表示完全相同,形式化為 $x{+}_w^{t}y=U2T_w(T2U_w(x){+}_w^{u}T2U_w(y))$(Eq. 2.14)。因此多數 CPU 用同一條加法指令處理兩者。
• 4-bit 範例(Figure 2.25):5 + 5 = 10 → 截斷得 -6(positive overflow,少 16);-8 + (-5) = -13 → 得 3(negative overflow,多 16);-8 + 5 = -3(normal,不溢位)。
• Overflow 偵測原理:令 $s=x{+}_w^{t}y$:
  • Positive overflow ⟺ x > 0 && y > 0 && s <= 0
  • Negative overflow ⟺ x < 0 && y < 0 && s >= 0
  • 一正一負相加絕不會溢位。

2.3.3 Two's-Complement 取負 (p.131-132)

公式(Eq. 2.15):

• TMin 是自己的加法反元素:$TMin+TMin=-2^w$ 造成 negative overflow,截斷後為 0。這是「取負」最重要的例外。
• 位元技巧一:-x == ~x + 1(逐位取反再加一),對所有整數值成立。例:0xfffffffa 逐位取反得 0x00000005,加 1 得 6,故原值為 −6。
• 位元技巧二:設 k 為最右邊的 1 的位置(x ≠ 0),則取負 = 位置 k 左邊的位元全部取反、位置 k 與其右邊保持不變。例:[0101](5)→ [1011](−5)。
• 觀察(Practice 2.28/2.33):unsigned 取負與 two's-complement 取負對同一位元模式產生的結果位元模式相同。

2.3.4 Unsigned 乘法 (p.132-133)

真實乘積 $x\cdot y$ 範圍可達 $(2^w-1{)}^2=2^{2w}-2^{w+1}+1$,最多需要 2w bits。C 定義 unsigned 乘法取 2w-bit 乘積的低 w 位,等價於模運算:

2.3.5 Two's-Complement 乘法 (p.133-137)

有號乘積範圍 $-2^{2w-2}+2^{w-1}$ 到 $2^{2w-2}$,同樣截斷為低 w 位再以 two's-complement 解讀:

• 位元層級等價原理:$T2B_w(x{\ast }_w^{t}y)=U2B_w(x^{\prime }{\ast }_w^u{y}^{\prime })$——同一組位元向量,不論當作有號或無號相乘,截斷後的位元結果完全相同(完整 2w-bit 乘積則可能不同)。推導關鍵:$x^{\prime }=x+x_{w-1}{2}^w$,mod $2^w$ 後含 $2^w$、$2^{2w}$ 權重的項全部消失(Eq. 2.18)。
• 3-bit 範例(Figure 2.27):[101]×[011],unsigned 為 5×3=15=[001111],signed 為 −3×3=−9=[110111],截斷後皆為 [111]。
• 溢位偵測(Practice 2.35):!x || p/x == y 可行——乘法可用除法驗證(因 $x\cdot y=p+t{2}^w$ 且 $t\ne 0$ ⟺ 溢位;除法無截斷、結果唯一),這與「加法不能用減法驗證」形成對比。也可改用更寬型別:int64_t p = (int64_t) x * y; 再檢查 p == (int) p(Practice 2.36)。

2.3.6 乘以常數 (p.137-139)

整數乘法指令歷史上需 10+ clock cycles(參考機 Intel Core i7 Haswell 上需 3 cycles),而 add/sub/shift 只需 1 cycle,因此編譯器把「乘以常數」改寫成 shift + add/sub 組合。

• 乘以 2 的冪 = 左移:對 unsigned 值 x 與 $0\le k<w$,x << k $=x{\ast }_w^u{2}^k$;對 two's-complement 值同理 x << k $=x{\ast }_w^t{2}^k$。即使溢位,左移與乘法結果仍逐位相同。例:[1011](11)左移 2 得 [101100](44),截斷 4 bits 得 [1100](12 = 44 mod 16)。
• 任意常數 K:把 K 的二進位視為 0 串與 1 串交替;對每段從 bit n 到 bit m 的連續 1(n ≥ m)有兩種展開:
  • Form A:(x<<n) + (x<<(n-1)) + ... + (x<<m)
  • Form B:(x<<(n+1)) - (x<<m)
• 範例:x*14,因 $14=2^3+2^2+2^1=[1110]$,Form A 為 (x<<3)+(x<<2)+(x<<1)(3 shifts + 2 adds);Form B(利用 $14=2^4-2^1$)為 (x<<4)-(x<<1)(2 shifts + 1 sub),更佳。兩者對 unsigned/signed、甚至溢位時皆與乘法結果一致。
• 選擇準則(Practice 2.41):run 長度 = 1 用 Form A(單一 shift);run 長度 ≥ 2 用 Form B;划算與否取決於各指令相對速度(machine dependent),多數編譯器只在少量 shift/add/sub 即可取代時才做此最佳化。
• x86-64 的 lea 指令可單條完成 (a<<k) + b(k ∈ {0,1,2,3}、b 為 0 或程式值),故 a 的 1、2、3、4、5、8、9 倍都能一條指令算出(Practice 2.38)→ 見 03-Machine-Level-Programs/02-Data-Movement-and-Arithmetic。

2.3.7 除以 2 的冪 (p.139-143)

整數除法更慢(30+ clock cycles)。除以 $2^k$ 可用右移實現,但 unsigned/signed 需不同種類的 shift——這正是機器同時提供 logical / arithmetic right shift 兩種右移的原因。

• 捨入定義:C 整數除法一律向零捨入 (round toward zero)——結果為正時向下取整 $\lfloor x/y\rfloor$,為負時向上取整 $\lceil x/y\rceil$。floor:$\lfloor 3.14\rfloor =3$、$\lfloor -3.14\rfloor =-4$;ceiling:$\lceil 3.14\rceil =4$、$\lceil -3.14\rceil =-3$。

• Unsigned:x >> k(logical shift)$=\lfloor x/2^k\rfloor$,直接正確(非負數向下取整即向零捨入)。例(Figure 2.28):12340 >> 8 = 48(= ⌊48.203⌋)。

• Signed(直接算術右移):x >> k(arithmetic shift)$=\lfloor x/2^k\rfloor$——對負數是向下捨入而非向零,不整除時比 C 除法小 1。例(Figure 2.29):−12340 >> 4 = −772,但 C 要求 −12340/16 = −771。

• Bias 修正(向零捨入):利用恆等式 $\lceil x/y\rceil =\lfloor (x+y-1)/y\rfloor$(y > 0;設 $x=qy+r$,$0\le r<y$,加 $y-1$ 後向下取整,r=0 得 q、r>0 得 q+1),先加 bias $2^k-1$ 再右移:

  (x + (1 << k) - 1) >> k $=\lceil x/2^k\rceil$

• 完整的 C 慣用式(編譯器對 signed 除以 $2^k$ 的實際產出):

             x
             │
       ┌─────┴─────┐
    x < 0 ?        │
       │ yes       │ no
       ▼           │
  x += (1<<k)-1    │      ← bias = 2^k - 1
       │           │
       └─────┬─────┘
             ▼
     x >> k (arithmetic)   →  x / 2^k(向零捨入)

即 (x < 0 ? x + (1<<k) - 1 : x) >> k。無分支版本(Practice 2.42,k=4):(x + ((x >> 31) & 15)) >> 4——用符號位 mask 產生 bias。

• Practice 2.43 逆向範例:x*M + y/N 被編譯成 (x<<5) - x 與 if (y<0) y += 7; y >>= 3,故 M = 31、N = 8。

2.3.8 整數算術總結 (p.143-144)

• 電腦的「整數」算術實際上是 modular arithmetic:有限字長限制值域,運算可能 overflow,且 C 不會產生任何錯誤訊號。
• Two's-complement 的巧妙之處:同時表示正負數,而加、減、乘、甚至除法的位元層級行為與 unsigned 相同或非常相似。
• unsigned 型別雖然概念簡單,卻常以意想不到的方式出現(整數常數、size_t 等函式庫型別、隱式轉換),是難以察覺的 bug 與安全漏洞來源;Java 等多數語言乾脆不提供 unsigned(其 >> 保證為 arithmetic shift、>>> 為 logical shift)(p.120)。
• unsigned 的正當用途:把 word 視為純位元集合(Boolean 旗標打包)、位址、模運算與 multiprecision 算術套件(p.120)。
• Practice 2.44 精選判斷(w=32):(x*x) >= 0 非恆真(乘法溢位可為負);x+y == uy+ux 恆真(加法位元層級相同);x < 0 || -x <= 0 恆真(TMin 取負仍 TMin ≤ 0);x > 0 || -x >= 0 非恆真(x = TMin 時兩邊皆偽)。

Exam/Test Patterns

Related Notes

• 02-Information-Representation/02-Integer-Representations
• 02-Information-Representation/01-Information-Storage-and-Bits
• 02-Information-Representation/04-Floating-Point
• 03-Machine-Level-Programs/02-Data-Movement-and-Arithmetic
• 03-Machine-Level-Programs/06-Buffer-Overflow-and-Pointer-Safety
• 02-Information-Representation/Practice-Information-Representation