問題來源
《深入理解計算機系統》（CSAPP）P215 頁：
y（64位）= y高位 × 2^32 + y低位，x 為 32位
x × y = x × (y高位 × 2^32) + x × y低位
為什麼 x × y 最大需要 96 位？
直觀理解：位數相加原理
二進制乘法位數規律：m 位數 × n 位數，結果最多 m+n 位。
- 十進制類比：3 位數 × 2 位數（如 999 × 99 = 98901），結果最多 5 位 = 3+2
- 二進制同理：32 位 × 64 位 → 最多 96 位
數學嚴格證明
無符號數情況
- 32 位無符號數最大值：
2^32 - 1
- 64 位無符號數最大值：
2^64 - 1
- 乘積最大值：
(2^32 - 1) × (2^64 - 1) = 2^96 - 2^32 - 2^64 + 1
2^96 - 2^32 - 2^64 + 1 < 2^96，但 ≥ 2^95（當兩數均為最大值時）- 因此需要 **96 位** 才能無溢出表示
有符號數情況（補碼）
- 範圍：
-2^31 ~ 2^31-1 和 -2^63 ~ 2^63-1
- 最小乘積：
(-2^31) × (-2^63) = 2^94（需 95 位含符號位）
- 最大乘積：
(2^31-1) × (2^63-1) < 2^94
- 極端情況：
(-2^31) × (2^63-1) = -2^94 + 2^31（需 95 位）
- **結論：有符號 32×64 乘法需 95 位（含符號位），通常分配 96 位對齊**
硬體實現視角
| 指令集 | 32×32→64 | 32×64→96 | 64×64→128 |
|---|
| x86 (32位模式) | MUL (EDX:EAX) | 需多指令組合 | 不直接支援 |
| x86-64 | MUL (RDX:RAX) | MUL + 額外邏輯 | MUL (RDX:RAX) |
| ARM64 | UMULL | UMULL + UMLAL | UMULL (高64:低64) |
| RISC-V | MULHU/MUL | 多指令序列 | MULHU/MUL |
CSAPP 書中分解邏輯解析
x * y = x * (y_high * 2^32 + y_low)
= (x * y_high) * 2^32 + (x * y_low)
// 項1: x (32位) * y_high (32位) → 64位結果，左移32位 → 佔用 96位空間
// 項2: x (32位) * y_low (32位) → 64位結果，佔用低 64位
// 相加：96位 + 64位 → 最終 96位結果
書中將 64 位數拆為高 32 位 + 低 32 位，利用 32×32→64 位硬體乘法器分步計算，最終拼湊 96 位結果，這正是編譯器生成大整數乘法代碼的標準做法。
總結
m 位 × n 位 → 最多 m+n 位 是二進制乘法的基本定理。32 位 × 64 位 = 96 位，無關具體數值，僅由位寬決定。CSAPP 通過高低位分解展示了編譯器如何利用固定寬度乘法器實現大位寬乘法，這是理解計算機算術、編譯器代碼生成、密碼學大數運算的基石知識。
- 上一篇文章： Struts2 配置錯誤導致 NoSuchMethodException：action 方法映射機制深度解析
- 下一篇文章： Linux 消息隊列編程：多進程群聊模型中如何正確清空隊列
Copyright ©
程式碼之家 All Rights Reserved
