變量乘常量

• 常量為2的冪

乘法將會被替換為執行周期更短的移位指令。

int fun(int n) {
    return n * 16;
}
// mov eax, n
// shl eax, 4

• 常量為非2的冪

因為 thumb 和 x86 指令集的差異，安卓平臺上處理的更好一些。

我并不推薦你把自己當成編譯器，看到算式想著怎么轉成匯編，而是推薦記下這種算法，看到計算過程知道怎么轉成原式，當然也不追求100%還原，邏輯一致即可。

編譯器會對非2的冪進行拆解，例如：

• n * 15 = n * 16 - n = n << 4 - n
• n * 12 = n * 3 * 4 = (n << 1 + n) << 2

int value = n * 15;
// rsb.w r0, r1, r1, lsl #4

int value = n * 12;
// add.w r0, r1, r1, lsl #1

當然 windows 平臺也不是一無是處，某些乘法會通過 lea 將兩條指令合并成一條。

• n * 4 + 5 = lea edx, [ecx * 4 + 5]

printf("%d", n * 4 + 5);
// mov ecx, n
// lea edx, [ecx * 4 + 5]
// push edx

至于值為不可拆分的素數，就改用 mul 指令。

變量乘變量

這一步沒有什么優化空間，因為都是未知的，只能老老實實用 mul 指令。

int fun(int n, int m) {
    return n * m;
}
// mov eax, n
// mov ecx, m
// imul ecx

除法

在看下面內容之前，不妨再問問自己，真的了解除法嗎？除法的本質是什么？

ok，現在是復習時間，簡單總結一下以下兩個問題。

• 符號問題
  1. 兩個無符號整數相除，結果依然是無符號
  2. 兩個有符號整數相除，結果依然是有符號
  3. 混除，參數全被當成無符號計算，結果是無符號
• 取整問題
  1. 向下取整 —— floor 函數 存在誤差 => ( - a / b ) + ( a / b ) != - ( a / b ) - ( a / b )
  2. 向上取整 —— ceil 函數 存在誤差 => ( - a / b ) != - ( a / b )
  3. 向零取整 —— 截斷除法(Truncate)，可以理解為放棄小數部分，只取整數部分，可以在任何情況保持恒等，大部分語言用的都是截斷除法

除數為無符號數

• 大數（負數）

在無符號中，負數的值是很大的，例如 -8 = 0xFFFFFFF8。

而除以這種大數，只能出現兩種情況，1或 0，換個思路來想就可以寫成這樣：[被除數] >= [除數] ? 1 : 0

我們來看看 thumb 下是怎么優化的？

UINT value = (UINT)n / -8;
// cmn.w r0, #9    ; cmp r0, -9
// it hi
// movhi r1, #1    ; n > -9 ? 1 : 0

他這里做了一個小小的變形：[被除數] > [除數 - 1] ? 1 : 0，邏輯上仍然成立。

• 2的冪

簡單的移位

UINT value = (UINT)n / 4;
// lsrs r1, r0, #2

• 非2的冪

接下來就要引入一個非常魔幻的設定，magic number。說來這個魔數，依稀記得早在幾年前的知乎上看到過一篇文章，講的是雷神之錘游戲引擎就使用了這么一個魔數，那時的cpu是非常低效的，而為了避免使用除法這種 cpu 周期偏長的指令，天才的程序員們想出了各種奇技淫巧，其中最為后人津津樂道的就是游戲中對平方根倒數的優化，將計算過程等價替換為加法和移位操作，損失少量的精度來換取絕對的性能。

我們這里的魔數稍有不同，它是用來優化除法的，而且邏輯上也相對容易理解一些，廢話不多說，進入正題。

對于普通除法，我們可以得到以下的換算：（x => 被除數變量，c => 除數常量，M => 魔數）

假設用 M 代替 2^n / c 這個 Magic 變量，于是有：

也就是說，除法將會被轉會成 (x * M) >> n 的邏輯進行運算，至于 M 和 n 值怎么來的，我們不關心，這是編譯器根據除數算出來的最優值，會盡力保證偏差達到最小，我們要做的是認出魔數和移了多少位，然后根據 m = 2^n/c 公式求得原本的除數 c = 2^n/m

公式來源于《C++反匯編與逆向分析技術揭秘》，真的是非常非常的細，書中整個推導過程很完整，很建議各位去仔細研讀一遍

以下代碼為例：

printf("%u", (unsigned)argc / 3);
// mov eax, 0xAAAAAAAB   ; M
// mul [argc]            ; edx:eax = argc * M
// shr edx, 1            ; edx = argc * M >> 32 >> 1
// push edx