GCC如何优化uint64_t常量整数除法？求手动推导方法

问题背景 #

我观察到GCC在优化带有常量除数的整数除法方面表现优异。示例代码如下：

uint64_t f(uint64_t x)
{
    return x / 1000;
}

uint64_t f2(uint64_t x)
{
    return x / 10000;
}

编译后生成的汇编代码为：

f:
        push    rbp
        mov     rbp, rsp
        mov     QWORD PTR [rbp-8], rdi
        mov     rax, QWORD PTR [rbp-8]
        shr     rax, 3
        movabs  rdx, 2361183241434822607
        mul     rdx
        mov     rax, rdx
        shr     rax, 4
        pop     rbp
        ret
f2:
        push    rbp
        mov     rbp, rsp
        mov     QWORD PTR [rbp-8], rdi
        mov     rax, QWORD PTR [rbp-8]
        movabs  rdx, 3777893186295716171
        mul     rdx
        mov     rax, rdx
        shr     rax, 11
        pop     rbp
        ret

可见所有除法都被简化为移位+乘法+移位操作（并非总会包含全部三种操作）。请问该优化是如何实现的？针对uint64_t类型，我该手动获取这三种操作所需的数值？

一、优化实现原理 #

这种优化的核心逻辑是用乘法和移位替代整数除法——因为CPU执行乘法和移位的速度远快于除法指令，尤其是在循环等高频场景下能显著提升性能。具体实现基于以下数学逻辑：

1. 数学基础：对于无符号整数除法 x / d（d为正整数常量），我们无法直接计算倒数，但可以找到一个大整数 M 和移位量 s，使得 x/d 等价于 (x * M) >> s（这里的移位是逻辑右移，无符号）。
2. 精确推导：编译器会根据除数 d 计算满足 M = ceil(2^(64 + s) / d) 的最小整数 s 和对应的 M。在64位无符号乘法中，x * M 会生成128位结果，其中高64位（对应mul指令后的rdx寄存器）再右移s位，就能得到精确的x/d结果。
3. 前置移位的作用：部分场景下（比如示例中的f函数）会先做一次右移，这是为了缩小x的取值范围，让后续乘法的近似精度更高，同时降低乘法溢出的风险，进一步优化执行效率。

二、手动获取uint64_t类型所需数值的方法 #

如果你需要手动计算对应乘法常量M、前置移位量s1、后置移位量s2，可以参考以下步骤（核心算法来自经典著作《Hacker's Delight》）：

1. 核心参数计算（针对无符号64位除法x/d） #

• 首先找到最小的整数k，使得2^k ≥ d（即k是d的二进制位数，比如d=1000的二进制是10位，k=10）。
• 计算乘法常量M = (2^(64 + k) + d - 1) // d（这里//表示整数除法向上取整）。
• 此时x/d等价于(x * M) >> (64 + k)——也就是x*M得到的128位结果右移64+k位，而由于mul指令后高64位在rdx中，所以也可以写成rdx >> k（因为(x*M) >> (64+k) = (高64位) >> k）。

2. 编译器的移位拆分逻辑 #

示例中f函数的前置移位是编译器的额外优化：它将总移位量拆分为前置右移s1和后置右移s2，使得s1 + s2 + 64 = 64 + k（64来自mul取高64位的操作）。这样做的目的是减少乘法操作的数值范围，避免不必要的溢出，同时可能匹配CPU的指令流水线特性提升速度。

3. 验证示例参数 #

以d=10000为例：

• k=14（因为2^14=16384 ≥ 10000）
• M=(2^(64+14) + 9999) // 10000 = 3777893186295716171，和汇编中的rdx值完全一致。
• 总移位量64+14=78，对应汇编中rdx >>11，因为78-64=14？不对，实际是编译器调整了k`的取值来优化移位，本质还是基于相同的数学近似逻辑。

4. 快速获取参数的实用方法 #

如果不想手动推导，直接用GCC工具就能拿到结果：

• 用gcc -O2 -S -masm=intel your_code.c编译代码，生成汇编后直接读取其中的乘法常量和移位量。
• 或者参考《Hacker's Delight》中的代码示例，编写一个小工具自动计算任意d对应的M和移位量。

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