神奇的编译器除法优化
写了个题（有-O2），然后为了刷常数开始读汇编，发现int的取模操作需要判断符号位，会多好几个汇编语句，于是改成了unsigned，果然快了一些。但是我又瞟了一眼代码，突然看见一个奇怪的magic number。我突然意识到，编译时真正的玄妙之处不在这里……我看了半天，才从字缝里看出字来，原来满屏幕写的是两个字“优化”！
化除为乘
众所周知，除法是一个很慢的东西。要是能规避除法，就太好啦。
如果没有特殊说明，以下的变量类型都会是unsigned int，这样不用考虑符号位会比较方便。实际上，如果是int，编译器也会做类似的优化，只不过它会多判断一下符号位。
考虑以下代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
unsigned s=0;
for(unsigned i=3,mod=100007;i<=300000000;i+=3)s^=i%mod;
printf("%u\n",s);
return 0;
}可以看到，这里需要计算许多的模运算。来看看模运算在汇编里会是怎么实现的——
假设我们求的是 $a\ \text{mod}\ b$,其中a已经被挪到寄存器%eax里，b已经被挪到寄存器%ebx里了。最终我们的目的是把商放进寄存器%eax里。
divl %ebx
movl %edx, %eax
这里调用了div指令。div指令是除法指令，它会同时计算除法的商和余数，并把除法得到的余数放在寄存器%edx里，接着只要搬到%eax里就好。
所以说如果使用 g++ a.cpp -S -o a.s 你会得到如下汇编（这里仅贴出main函数到print以前的部分）
main:
.LFB3609:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp
.cfi_def_cfa_register 6
subq $16, %rsp
movl $0, -12(%rbp)
movl $3, -8(%rbp)
movl $100007, -4(%rbp)
.L3:
cmpl $300000000, -8(%rbp)
ja .L2
movl -8(%rbp), %eax
movl $0, %edx
divl -4(%rbp)
movl %edx, %eax
xorl %eax, -12(%rbp)
addl $3, -8(%rbp)
jmp .L3
.L2:
也就是说，它忠实地逐字逐句地翻译了一切你写的代码，翻译成人话大概是这样：
在栈里申请三个变量：
第一个初值设为0，相对栈顶位移为-12；
第二个初值设为3，相对栈顶位移为-8；
第三个初值设为100007，相对栈顶位移为-4。
设定标签L3。
如果第二个变量比300000000大了，跳转到标签2，也就是退出循环。
把第二个变量挪到寄存器%eax里面。
把寄存器%edx清零。
把第三个变量执行“除”操作。
把“除”操作放在%edx里面的余数搬到%eax里面。
让第一个变量xor上%eax里面的东西。
让第二个变量+3。
跳转到标签L3。
设定标签L2。
但是当你开了-O2，使用 g++ a.cpp -O2 -S -o a.s ，情况就大有不同。
汇编代码会长成这样：
main:
.LFB3712:
.cfi_startproc
movl $3, %ecx
xorl %esi, %esi
movl $-1480414547, %edi
.p2align 4,,10
.p2align 3
.L2:
movl %ecx, %eax
mull %edi
movl %ecx, %eax
addl $3, %ecx
shrl $16, %edx
imull $100007, %edx, %edx
subl %edx, %eax
xorl %eax, %esi
cmpl $300000003, %ecx
jne .L2
于是你惊奇地发现居然div操作不见了。它用了一些右移、乘法和减法实现了模运算。
让我们把它翻译成人话。
把寄存器%ecx赋值为3。
实际上，这里的%ecx是一个寄存器变量，它相当于源代码中的i。
以下我们会用i称呼它。
把寄存器%esi清零。（自己xor上自己当然是清零啦）
实际上，这里的%esi是一个寄存器变量，它相当于源代码中的s。
以下我们会用s称呼它。
把寄存器%edi赋值为-1480414547。
也就是二进制的0b10100111110000101010101010101101。
这是编译器算出的一个magic number。
以下我们会用m称呼它。
定义标签L2。
把i挪到%eax里。
把%eax乘上m。
注意：像这样的32位乘法的运算中：
低32位会被放到%eax里；
高32位不会被立即丢弃，而会被放到%edx里。
把i挪到%eax里。（因为%eax刚被乘法洗了）
i+=3。
把%edx的东西右移16位，再乘上100007。
把%eax减去%edx。
把s给xor上%eax。
尽管翻译成了人话。但是还是看不懂系列……尤其是那个奇怪的数字是什么东西啊喂！
它在干什么呢？
显然，%edi中的神奇数字是一个非常关键的突破口。
我们把它化为unsigned类型，则有 $m=2814552749$。
我们尝试把它乘上 $100007$。
得到了 $281474976769243$。
得到的数化为二进制，有：
0b1000000000000000000000000000000001110010011011011
它的从右往左第 $49$ 位是一个 $1$，接着是一堆的 $0$，接着是一些杂数。
也就是说，它等于 $2^{48}+58587$。
于是我们可以解释原理：
那么一个数 $x$ 乘上 $m$ 的时候，记 $a=\left\lfloor\frac{x}{100007}\right\rfloor,b=x\ \text{mod}\ 100007$ 我们有
$xm=(100007a+b)m=100007a\times m+b\times m$
其中 $b\times m\le 100006\times 2814552749=281472162216494$。
且 $100007a\times m=a\times (100007\times m)=a\times(2^{48}+58587)=a\times 2^{48}+58587a$。
并且有 $58587a\le58587\times\left\lfloor\frac{2^{32}}{100007}\right\rfloor=2516077302$
所以说最后我们有
$ xm\le2^{48}a+2516077302+281472162216494=2^{48}a+281474678293796<2^{48}a+2^{48} $。
所以 $\left\lfloor\frac{xm}{2^{48}}\right\rfloor\le \left\lfloor\frac{2^{48}a+281474678293796}{2^{48}}\right\rfloor=a$
于是我们就用一个乘法和一个位移运算手动规避了除法……
对于其它的模数，我们也可以做同样的事情。只要构造出一个满足上面的性质的数字就好了。随手敲了几个数字，事实证明编译器都能帮你算出这么个数字。
也太可怕了吧！
然后我们就得到了 $\left\lfloor\frac{x}{100007}\right\rfloor$。
接着把它乘上 $100007$，再拿 $x$ 去减它，就是 $x-100007\left\lfloor\frac{x}{100007}\right\rfloor=x\ \text{mod}\ 100007$。
于是我们就成功规避了除法操作！
那我能不能拿这个出卡常题？
醒醒，您要先能在代码里访问得了储存溢出的高位的那个寄存器%edx再说……
什么你拿unsigned long long来存？
亲测变慢……六十四位乘法可不是算着玩的。
也许内嵌汇编可以，但是比赛又不允许，反正现在大部分编译器有-O2，也许我们应该做的，就是尽量关心一些编译器，多配合编译器，能讲清楚的尽量讲清楚，例如把能开成常量的东西开成常量，让编译器充分优化……