彙編除法筆記---如何用移位替代除法

前言

除法的指令周期比較長，用移位後乘法替代除法可以很有效的優化算法，本文用以小結，附有執行個體（都是release版本的執行個體以及自己畫的圖），希望在寫作之餘加深了解

整數的除法

（1）有符号除法，除數為2^n

數學公式為：如果x>=0,x/2^n=x>>n ; 如果x<0,x/2^ n=(x+(2^n-1))>>n

下面為x/4的例子：

以-4/4為例子：

ps：1.負數在編譯器中以補碼儲存
    2.負數取反符号位不變
    3.edx=0xffffffff其實也就是-1
           

（2）有符号除法，除數為-2^n

同（1），差別在彙編代碼在計算後用neg eax将結果取反，并沒有先識别被除數的正負

（3）有符号除法，除數為正非2^n

優化公式1：x>=0,則x/o=x*c>>32/64>>n
		 如果x<0,則x/o=(x*c>>32/64>>n)+1
		 
優化公式2：x>=0,則x/o=(x*c>>32/64)+x>>n
		 如果x<0,則x/o=(x*c>>32/64)+x>>n+1
           

下面是x/7的執行個體：

c為MAGIC_NUM , n為右移總次數

ps:優化公式括号内是優先計算的公式，之外按從左到右的順序處理(+x>>n指先加x再右移n)
           

（下面這張解析圖又是幾天之後重新審視後做的筆記了，但優化公式2并未給以證明，因為當時直接代入執行個體時也無法得到正确解，感覺有備援步驟，是以不予推導解析）

對于優化公式1的解析圖，字不好看多多

（4）有符号除法，除數為負非2^n

優化公式1：x>=0,則x/o=x*c>>32/64>>n
		 如果x<0,則x/o=(x*c>>32/64>>n)+1
		 
優化公式2：x>=0,則x/o=(x*c>>32/64)+x>>n
		 如果x<0,則x/o=(x*c>>32/64)+x>>n+1
           

（5）無符号除法，除數為2^n

用移位指令替代除法
           

（6）無符号除法，除數為非2^n的情況a

優化公式：x/o=x*c>>32/64>>n
           

（7）無符号除法，除數為非2^n的情況b

優化公式：x/o=(x-(x*c>>32/64)>>n1)+(x*c>>32/64)>>n2
           

總結

所有用移位和加減法運算替換除法指令的操作本質上都是用多個2^n數來替代被除數

隔兩天更新彙編取餘優化算法，一個人研究算法屬實太占時間了@.@