编译器对取余和除法运算的优化

2024-04-11

环境#

CompilerExplorer
x64 msvc v19.35

概述#

看到奇怪的位运算、魔数，就考虑求余和除法

知识点#

1. 算数右移和逻辑右移#

汇编语言中SAR和SHR指令都是右移指令，SAR是算数右移指令（shift arithmetic right），而SHR是逻辑右移指令（shift logical right）。
两者的区别在于SAR右移时保留操作数的符号，即用符号位来补足，而SHR右移时总是用0来补足。
例如10000000算数右移一位是11000000，而逻辑右移一位是01000000。

2. C标准的int#

#include<stdint.h> 就可以使用各种int类型

注意：long long int 才是64位的， long int 和 int相同，即 %lld 才是64位

3. 求余的优化——生成Magic Number#

小知识：取模!=取余
主要区别于负数Mod
进行求模运算时：c = [a/b] = -7 / 4 = -2（向负无穷方向舍入），
进行求余运算时：c = [a/b] = -7 / 4 = -1（向0方向舍入）；
求模时：r = a - c*b =-7 - (-2)*4 = 1，
求余时：r = a - c*b = -7 - (-1)*4 =-3。

1）当模数为2的N次幂#

无符号数很简单，右移N位即可

有符号数比较复杂

逻辑与——保留N个低位和符号位比如 Mod 4
```
int tmp = i & 0x8000000C
```
自减一
逻辑或——保留N个低位的值，其他都赋值1
自加一

代码如下：

int mod(int a)
{
    int tmp = a & 0x80000003;
    if (tmp >= 0) return tmp;
    tmp--;
    tmp = tmp | -4;
    tmp++;
    return tmp;
}

这里和李师傅讨论了一下，【自减一】和【自加一】只会影响边缘值，比如 -4 Mod -4

-4 是 0b11...1100，【减减】和【或】之后，会变成 0b11...1111，

此时【加加】就会得到0

2）非2次幂#

汇编语言IMUL指令：有符号数乘法

【PDF】DivcMore——来源

【知乎】【编译笔记】变量除以常量的优化（一）——无符号除法

知乎有个很精彩的定理证明，需要再次细看

除法的优化——除法变乘法加位移#

int foo() {
    extern int a;
    int b = a / 3;
    return b;
}

foo:
        movsx   rax, DWORD PTR a[rip]
        mov     rdx, rax
        imul    rax, rax, 1431655766
        sar     edx, 31
        shr     rax, 32
        sub     eax, edx
        ret

\(\frac{a}{b} = a \times \frac{1}{b} = a \times \frac{2^n}{b} \div 2^n = a \times \frac{2^n}{b} \gg n\)

然后因为 \(\frac{2^n}{b}\) 可以提前算，所以可以用这种方式进行优化