C 語言優化：32 位整數除以/乘以 520 的最高效位運算實現

現代編譯器（GCC/Clang/MSVC）在優化級別 -O2 以上會自動將除以常數優化為乘法+移位組合，**手寫位運算通常不如編譯器生成的代碼**，且可讀性極差。但理解其原理有助於嵌入式無編譯器優化場景或面試考察。

數學分解原理

520 = 512 + 8 = 2⁹ + 2³

• 乘法： x * 520 = (x << 9) + (x << 3) — 兩次移位一加法，無溢出風險（32 位有符號數最大 2¹⁴⁷，遠超範圍）。
• 除法： 無法直接用移位組合精確等價。編譯器通常使用「魔數乘法 + 移位」模擬除法：

  // GCC 生成的近似除以 520 序列 (x86-64)
  mov eax, edi
  mov edx, 0x88888889  // 魔數 ≈ 2³² / 520
  mul edx              // edx:eax = x * 魔數
  shr edx, 3           // 結果在 edx
  mov eax, edx
  ret
  

文中給出的「手寫優化」分析

// 文中除法公式：X = A>>9 - (A - (A>>6)<<6) >> 3
// 即：A/512 - ((A % 64) / 8)  — 此公式**錯誤**，非等價於 A/520
// 反例：A=520 → 520>>9=1, (520%64)=8, 8/8=1 → 1-1=0，實際 520/520=1

文中乘法公式 X = A<<9 + A<<3 雖正確，但編譯器生成的 lea eax, [rax*8 + rax*512]（單指令）更優。

最佳實踐建議

1. 直接寫 x * 520 / x / 520，開啟 -O2 -march=native，信任編譯器。
2. 嵌入式無優化編譯器時，乘法用移位加法；除法**查閱編譯器生成的魔數序列**或使用庫函數 div，切勿自行推導錯誤公式。
3. 關鍵路徑性能敏感時，使用 Godbolt Compiler Explorer 對比手寫 vs 編譯器輸出彙編，實測基準。

過早優化是萬惡之源，可讀性與正確性優先，性能瓶頸經 Profile 確認後再針對性優化。