Question

下面展示的是怎样用乘法来优化除法，其中借助了 2^n 的阶乘

M 是一个 magic 系数

M 的计算过程

因此这些代码片段通常具有这样的形式

n 可以是任意数，可能是 32（那么这样运算结果的高位部分从 EX 或者 RDX 寄存器中获取），可能是 31（这种情况下乘法结果的高位部分结果右移）

n 的选取是为了减少错误。

当进行有符号数除法运算，乘法结果的符号也会被放到输出结果中。

下面来看看不同之处。

#!bash
int f3_32_signed(int a)
{
    return a/3;
};
unsigned int f3_32_unsigned(unsigned int a)
{
    return a/3;
};

在无符号版本的函数中，magic 系数是 0xAAAAAAAB，乘法结果被 2^3*3 除。

在有符号版本的函数中，magic 系数是 0x55555556，乘法结果被 2^32 除。

符号来自于乘法结果：高 32 位的结果右移 31 位（将符号位放在 EAX 中最不重要的位置）。如果最后结果为负，则会设置为 1。

清单 14.4：MSVC 2012/OX

#!bash
_f3_32_unsigned     PROC
        mov     eax, -1431655765        ; aaaaaaabH
        mul     DWORD PTR _a$[esp-4]    ; unsigned multiply
        shr     edx, 1
        mov     eax, edx
        ret     0
_f3_32_unsigned ENDP

_f3_32_signed PROC
        mov     eax, 1431655766         ; 55555556H
        imul    DWORD PTR _a$[esp-4]    ; signed multiply
        mov     eax, edx
        shr     eax, 31                 ; 0000001fH
        add     eax, edx                ; add 1 if sign is negative
        ret     0
_f3_32_signed ENDP