C/C++编译器对非2的幂整数除法的优化原理是什么？

x86 架构中idiv除法指令的执行延迟远高于乘法和移位指令，因此编译器会对编译期已知除数的整数除法做等价变换，用乘法+移位的组合替换除法指令，大幅提升运行性能。

核心变换逻辑 #

对于整数除法 a / b（b 为编译期确定的常量），可以通过定点数乘法等价转换：
我们选择一个足够大的 2 的整数次幂 2^n，计算 b 的倒数的定点数近似值 M = round(2^n / b)，此时 a / b 可以等价为 (a * M) >> n，只要 n 选取足够大，就能保证整数运算下的结果和原生除法完全一致。

你示例中是32位有符号整数除以3：

• 编译器选择 n = 32，计算得到 M = 2^32 / 3 ≈ 1431655766，也就是你看到的汇编中的立即数。

对应汇编逐行解释 #

int i;
i /=3;

对应的优化后汇编逻辑如下：

; 输入参数i存放在rsi寄存器中
mov     rax, rsi        ; 拷贝被除数i到rax寄存器，用于后续提取符号位
imul    rsi, rsi, 1431655766 ; 执行i * 1431655766，64位乘法结果保存在rsi中
sar     eax, 31         ; 对eax做算术右移31位，得到i的符号标记：i为负数时结果为-1，非负数时结果为0
shr     rsi, 32         ; 将乘法结果右移32位，等价于除以2^32，得到商的原始值
sub     esi, eax        ; 修正有符号数的符号误差，保证最终结果符合C语言除法向零取整的规则

补充说明 #

• 该优化仅适用于除数为编译期常量的场景，如果除数是运行时动态生成的变量，编译器仍会生成idiv指令完成除法。
• 无符号整数的同类优化不需要最后的符号修正步骤，逻辑更简单。
• 编译器内部已经预计算了所有常见除数对应的魔法数M和移位参数n，不需要在编译或运行时动态计算。

内容的提问来源于stack exchange，提问作者itzjackyscode