Loading... 在前一篇文章中，对编译器正整数除法优化进行了分析，其思路是转化为与magic number的乘法以及右移运算。 其核心公式为：$\lceil\frac{n}{d}\rceil = \lceil\frac{ n\times m } {2^{N+l}}\rceil$。 但是我们的关注点，是将二进制代码转化为伪代码。 因此，对于其二进制代码的还原，有如下几种类型： ### 1.直接右移 表现形式：`shr ecx,5 `或 `n>>5`。 对应伪代码：$\frac{n}{2^{5}}$ ### 2.乘法及右移运算 表现形式： ```汇编 mov r13d, 1374389535 mov eax, ebx mul r13d shr edx, 5 ``` 对应伪代码：$\frac{n}{d}=\frac{n}{100}$ > 上图对应的 $m=1374389535$，$l=5$，$N=32$。 > > 计算$d$：$d=\lceil \frac{2^{N+l}}{m}\rceil=100$ ### 3. 乘法、减法、加法、及右移运算 表现形式： ```汇编 mov eax,24924925h mul eax,ecx sub ecx,edx shr ecx,1 lea eax,[edx+ecx] shr eax,2 ``` 对应伪代码分析：$\frac{n}{d} = \frac{n}{7}$ > 对应上图的$m=24924925$，$l=3$，$N=32$。也就是如下形式的变种： > > $$ > Uint32 t = muluh(n, m - (Uint64(1) << 32);\quad \quad > return (n + t) >> l; > > $$ > > 因此，$m=24924925+2^{32}=4319892221$ > > 从而：$d =\frac{2^{N+l}}{m}=7$ ### 4.总结 总结来说，对于除法乃至取余运算，最佳的方式是将被除数设定为 $2^k$的形式，以实现最少CPU运算。 最后修改：2021 年 04 月 16 日 06 : 54 PM © 允许规范转载