計算機系統原理（十）二進制整數乘法與除法運算原理

引言

加法是運算基礎，減法、乘法可歸約為加法，唯除法不可。理解運算抽象特性有助於跨平台程序編寫。

無符號乘法

兩個 w 位無符號數相乘，結果可能需 2w 位。實際截斷保留低 w 位：pro mod 2^w。

補碼乘法

補碼乘法建立在無符號乘法基礎上：真實乘積 pro，結果為 U2T_w(pro mod 2^w)。證明關鍵：2^w mod 2^w = 0，故補碼與無符號乘法低 w 位相同，可共用指令。

乘法優化：移位與加法

利用 x * 2^k = x << k，將乘法分解為移位加減。例：x * 17 = (x << 4) + x；x * 14 = (x << 4) - (x << 1)。但視硬體速度決定是否優化。

無符號除法與右移優化

除法不滿足分配律。無符號數除以 2^k 等價於邏輯右移 k 位：⌊x/2^k⌋ = x >> k。證明利用等比數列求和說明低位捨入部分 < 1。

補碼除法的偏置修正

補碼負數算術右移非向零捨入（如 -17/8 = -2，但 -17 >> 3 = -3）。修正：被除數加上 y-1（偏置），即 ⌈x/y⌉ = ⌊(x+y-1)/y⌋。驗證：(-17+7) >> 3 = -2，符合向零捨入。

小結

整數運算專題完結。下一章進入浮點數世界。