为什么除以 3 需要在 x86 上进行右移（和其他奇怪的事情）？
Why does division by 3 require a rightshift (and other oddities) on x86?
我有以下 C/C++ 函数：
unsigned div3(unsigned x) {
return x / 3;
}
When compiled using clang 10 在 -O3，这导致：
div3(unsigned int):
mov ecx, edi # tmp = x
mov eax, 2863311531 # result = 3^-1
imul rax, rcx # result *= tmp
shr rax, 33 # result >>= 33
ret
我的理解是：除以3相当于乘以乘法逆元3-1 mod 232 即 2863311531.
虽然有些事情我不明白：
- 为什么我们需要使用
ecx/rcx？ rax 不能直接乘以 edi 吗？
- 为什么我们要乘以 64 位 mode？
eax 和 ecx 相乘不是更快吗？
- 为什么我们使用
imul 而不是 mul？我以为 mod元数算术都是无符号的。
- 最后的33位右移是怎么回事？我以为我们可以删除最高的 32 位。
编辑 1
不明白我说的3-1mod232是什么意思的，我在说关于这里的乘法逆。
例如：
// multiplying with inverse of 3:
15 * 2863311531 = 42949672965
42949672965 mod 2^32 = 5
// using fixed-point multiplication
15 * 2863311531 = 42949672965
42949672965 >> 33 = 5
// simply dividing by 3
15 / 3 = 5
所以乘以 42949672965 实际上等同于除以 3。我假设 clang 的优化是基于 mod 元算法，而实际上它是基于定点算法。
编辑 2
我现在明白乘法逆只能用于无余数的除法。例如，1 乘以 3-1 等于 3-1，而不是零。只有定点运算具有正确的舍入。
不幸的是，clang 没有使用任何 modular 算法，在这种情况下它只是一个 imul 指令，即使它可以。以下函数与上面的编译输出相同。
unsigned div3(unsigned x) {
__builtin_assume(x % 3 == 0);
return x / 3;
}
（关于适用于每个可能输入的精确除法的定点乘法逆元的规范问答：Why does GCC use multiplication by a strange number in implementing integer division? - 不完全重复，因为它只涵盖数学，而不是一些实现细节，如寄存器宽度和 imul 与 mul.)
What's up with the 33-bit right shift at the end? I thought we can just drop the highest 32-bits.
而不是 3^(-1) mod 3 你必须更多地考虑 0.3333333 其中 . 之前的 0 位于高 32 位和 3333位于低32位。
这个定点运算没问题，但是结果明显移到rax的上半部分，所以CPU运算后必须把结果再向下移
Why are we using imul instead of mul? I thought modular arithmetic would be all unsigned.
没有 MUL 指令等同于 IMUL 指令。使用的 IMUL 变体需要两个寄存器：
a <= a * b
没有 MUL 指令可以做到这一点。 MUL 指令更昂贵，因为它们将结果作为 128 位存储在两个寄存器中。
当然，您可以使用遗留指令，但这不会改变结果存储在两个寄存器中的事实。
- Can't we multiply rax with edi directly?
我们不能imul rax, rdi因为调用约定允许调用者在RDI的高位留下垃圾；只有 EDI 部分包含该值。内联时这是一个non-issue；将 32 位寄存器 做 隐式 zero-extend 到完整的 64 位寄存器，因此编译器通常不需要额外的指令来 zero-extend 一个 32-位值。
（zero-extend进入不同的寄存器更好，因为 ，如果你不能避免的话）。
从字面上看你的问题，不，x86 没有任何乘法指令 zero-extend 他们的输入之一可以让你乘以 32 位和 64 位寄存器。两个输入的宽度必须相同。
- Why do we multiply in 64-bit mode?
（术语：所有这些代码都在 64 位 模式下运行 。你问的是为什么 64 位 operand-size.)
您可以 mul edi 将 EAX 与 EDI 相乘以获得 64 位结果拆分 EDX:EAX，但 mul edi 在 Intel CPU 上是 3 微指令，而大多数现代 x86-64 CPU 具有快速 64 位 imul。 （尽管 imul r64, r64 在 AMD Bulldozer-family 和一些 low-power CPU 上较慢。） https://uops.info/ and https://agner.org/optimize/ （指令表和微架构 PDF）
（有趣的事实：mul rdi 在 Intel CPU 上实际上 更便宜 ，只有 2 微指令。可能与不必对整数乘法单元的输出进行额外拆分有关，像 mul edi 必须将 64 位低半乘法器输出分成 EDX 和 EAX 两半，但这对于 64x64 => 128 位乘法器自然会发生。）
此外，您需要的部分在 EDX 中，因此您需要另一个 mov eax, edx 来处理它。 （同样，因为我们正在查看函数的 stand-alone 定义的代码，而不是在内联到调用方之后。）
GCC 8.3 和更早版本 did 使用 32 位 mul 而不是 64 位 imul (https://godbolt.org/z/5qj7d5)。当 Bulldozer-family 和旧的 Silvermont CPU 更相关时，这对 -mtune=generic 来说并不疯狂，但是对于最近的 GCC，这些 CPU 已经过时了，它的通用调整选择反映了这一点。不幸的是，GCC 还浪费了一条 mov 指令将 EDI 复制到 EAX，使这种方式看起来更糟：/
# gcc8.3 -O3 (default -mtune=generic)
div3(unsigned int):
mov eax, edi # 1 uop, stupid wasted instruction
mov edx, -1431655765 # 1 uop (same 32-bit constant, just printed differently)
mul edx # 3 uops on Sandybridge-family
mov eax, edx # 1 uop
shr eax # 1 uop
ret
# total of 7 uops on SnB-family
在 mov eax, 0xAAAAAAAB / mul edi 时只有 6 微指令，但仍然比：
差
# gcc9.3 -O3 (default -mtune=generic)
div3(unsigned int):
mov eax, edi # 1 uop
mov edi, 2863311531 # 1 uop
imul rax, rdi # 1 uop
shr rax, 33 # 1 uop
ret
# total 4 uops, not counting ret
不幸的是，64 位 0x00000000AAAAAAAB 不能表示为 32 位 sign-extended 立即数，因此 imul rax, rcx, 0xAAAAAAAB 不可编码。这意味着 0xFFFFFFFFAAAAAAAB.
- Why are we using imul instead of mul? I thought modular arithmetic would be all unsigned.
它是无符号的。输入的符号仅影响结果的高半部分，但 imul reg, reg 不会产生高半部分。只有 mul 和 imul 的 one-operand 形式是 NxN => 2N 的完全乘法，所以只有它们需要单独的有符号和无符号版本。
只有 imul 具有更快更灵活的 low-half-only 形式。关于 imul reg, reg 唯一带符号的是它根据低半部分的带符号溢出设置 OF。不值得花费更多的操作码和更多的晶体管来拥有一个 mul r,r，它与 imul r,r 的唯一区别是 FLAGS 输出。
Intel的手册(https://www.felixcloutier.com/x86/imul)甚至指出可以用于unsigned。
- What's up with the 33-bit rightshift at the end? I thought we can just drop the highest 32-bits.
不，没有乘数常数可以为每个可能的输入给出准确的正确答案 x 如果您以这种方式实现它。 “as-if" 优化规则不允许近似值，只允许为程序使用的每个输入产生完全相同的可观察行为的实现。在不知道 x 的 value-range 而不是 unsigned 的完整范围的情况下，编译器没有该选项。 （-ffast-math 仅适用于浮点数；如果您想要更快的整数数学近似值，请像下面这样手动编码）：
有关 fixed-point 编译器用于按编译时间常数进行精确除法的乘法逆方法的更多信息，请参见 Why does GCC use multiplication by a strange number in implementing integer division?。
有关此 not 在一般情况下工作的示例，请参阅我对 Divide by 10 using bit shifts? 上的一个答案的编辑，该答案提议
// Warning: INEXACT FOR LARGE INPUTS
// this fast approximation can just use the high half,
// so on 32-bit machines it avoids one shift instruction vs. exact division
int32_t div10(int32_t dividend)
{
int64_t invDivisor = 0x1999999A;
return (int32_t) ((invDivisor * dividend) >> 32);
}
它的第一个错误答案（如果你从 0 向上循环）是 div10(1073741829) = 107374183，而 1073741829/10 实际上是 107374182。（它向上取整而不是像 C 整数除法应该的那样向 0 取整。）
从你的编辑中，我看到你实际上是在谈论使用乘法结果的 low 一半，这显然适用于一直到 [=140 的精确倍数=].
正如你所说，当除法有余数时，它完全失败了，例如16 * 0xaaaaaaab = 0xaaaaaab0 截断为 32 位时，不是 5.
unsigned div3_exact_only(unsigned x) {
__builtin_assume(x % 3 == 0); // or an equivalent with if() __builtin_unreachable()
return x / 3;
}
是的，如果该数学计算成功，编译器使用 32 位 imul 实现该计算将是合法且最佳的。他们不寻找这种优化，因为它很少为人所知。 IDK 如果值得添加编译器代码来寻找优化，就编译时间而言，更不用说开发人员时间的编译器维护成本了。这不是运行时成本的 巨大 差异，而且很少有可能。不过还是不错的。
div3_exact_only:
imul eax, edi, 0xAAAAAAAB # 1 uop, 3c latency
ret
但是，这是您可以自己做的事情源代码，至少对于已知的类型宽度，如 uint32_t:
uint32_t div3_exact_only(uint32_t x) {
return x * 0xaaaaaaabU;
}
如果你看看我对上一个问题的回答：
Why does GCC use multiplication by a strange number in implementing integer division?
它包含一篇 link 的 pdf 文章来解释这一点（我的回答澄清了这篇 pdf 文章中没有很好解释的内容）：
https://gmplib.org/~tege/divcnst-pldi94.pdf
请注意，某些除数需要额外的一位精度，例如 7，乘数通常需要 33 位，乘积通常需要 65 位，但这可以通过处理 2^32 来避免如我之前的回答及以下所示，分别使用 3 条附加说明进行操作。
换成
看看生成的代码
unsigned div7(unsigned x) {
return x / 7;
}
为了解释这个过程，令 L = ceil(log2(divisor))。对于上面的问题，L = ceil(log2(3)) == 2。右移计数最初为 32+L = 34.
为了生成具有足够位数的乘数，生成了两个潜在的乘数：mhi 将是要使用的乘数，移位计数将为 32+L。
mhi = (2^(32+L) + 2^(L))/3 = 5726623062
mlo = (2^(32+L) )/3 = 5726623061
然后检查是否可以减少所需的位数：
while((L > 0) && ((mhi>>1) > (mlo>>1))){
mhi = mhi>>1;
mlo = mlo>>1;
L = L-1;
}
if(mhi >= 2^32){
mhi = mhi-2^32
L = L-1;
; use 3 additional instructions for missing 2^32 bit
}
... mhi>>1 = 5726623062>>1 = 2863311531
... mlo>>1 = 5726623061>>1 = 2863311530 (mhi>>1) > (mlo>>1)
... mhi = mhi>>1 = 2863311531
... mlo = mhi>>1 = 2863311530
... L = L-1 = 1
... the next loop exits since now (mhi>>1) == (mlo>>1)
因此乘数为 mhi = 2863311531，移位计数 = 32+L = 33。
在现代 X86 上，乘法和移位指令是常数时间的，因此将乘法器 (mhi) 减少到小于 32 位是没有意义的，所以上面的 while(...) 被更改为 if( ...).
在7的情况下，循环在第一次迭代时退出，需要3条额外的指令来处理2^32位，所以mhi <= 32位：
L = ceil(log2(7)) = 3
mhi = (2^(32+L) + 2^(L))/7 = 4908534053
mhi = mhi-2^32 = 613566757
设ecx = dividend，简单的方法可能会溢出：
mov eax, 613566757 ; eax = mhi
mul ecx ; edx:eax = ecx*mhi
add edx, ecx ; edx:eax = ecx*(mhi + 2^32), potential overflow
shr edx, 3
为避免潜在的溢出，请注意 eax = eax*2 - eax:
(ecx*eax) = (ecx*eax)<<1) -(ecx*eax)
(ecx*(eax+2^32)) = (ecx*eax)<<1)+ (ecx*2^32)-(ecx*eax)
(ecx*(eax+2^32))>>3 = ((ecx*eax)<<1)+ (ecx*2^32)-(ecx*eax) )>>3
= (((ecx*eax) )+(((ecx*2^32)-(ecx*eax))>>1))>>2
所以实际代码，使用 u32() 表示高 32 位：
... visual studio generated code for div7, dividend is ecx
mov eax, 613566757
mul ecx ; edx = u32( (ecx*eax) )
sub ecx, edx ; ecx = u32( ((ecx*2^32)-(ecx*eax)) )
shr ecx, 1 ; ecx = u32( (((ecx*2^32)-(ecx*eax))>>1) )
lea eax, DWORD PTR [edx+ecx] ; eax = u32( (ecx*eax)+(((ecx*2^32)-(ecx*eax))>>1) )
shr eax, 2 ; eax = u32(((ecx*eax)+(((ecx*2^32)-(ecx*eax))>>1))>>2)
如果需要余数，可以采用以下步骤：
mhi and L are generated based on divisor during compile time
...
quotient = (x*mhi)>>(32+L)
product = quotient*divisor
remainder = x - product
x/3 大约是 (x * (2^32/3)) / 2^32。所以我们可以执行一次 32x32->64 位乘法，取高 32 位，得到大约 x/3.
存在一些错误，因为我们无法精确乘以 2^32/3，只能乘以四舍五入为整数的数字。我们使用 x/3 ≈ (x * (2^33/3)) / 2^33 获得更高的精度。 （我们不能使用 2^34/3，因为它大于 2^32）。事实证明，这足以在所有情况下准确地获得 x/3。如果输入是 3k 或 3k+2.
，您可以通过检查公式给出结果 k 来证明这一点
我有以下 C/C++ 函数：
unsigned div3(unsigned x) {
return x / 3;
}
When compiled using clang 10 在 -O3，这导致：
div3(unsigned int):
mov ecx, edi # tmp = x
mov eax, 2863311531 # result = 3^-1
imul rax, rcx # result *= tmp
shr rax, 33 # result >>= 33
ret
我的理解是：除以3相当于乘以乘法逆元3-1 mod 232 即 2863311531.
虽然有些事情我不明白：
- 为什么我们需要使用
ecx/rcx？rax不能直接乘以edi吗？ - 为什么我们要乘以 64 位 mode？
eax和ecx相乘不是更快吗？ - 为什么我们使用
imul而不是mul？我以为 mod元数算术都是无符号的。 - 最后的33位右移是怎么回事？我以为我们可以删除最高的 32 位。
编辑 1
不明白我说的3-1mod232是什么意思的，我在说关于这里的乘法逆。 例如：
// multiplying with inverse of 3:
15 * 2863311531 = 42949672965
42949672965 mod 2^32 = 5
// using fixed-point multiplication
15 * 2863311531 = 42949672965
42949672965 >> 33 = 5
// simply dividing by 3
15 / 3 = 5
所以乘以 42949672965 实际上等同于除以 3。我假设 clang 的优化是基于 mod 元算法，而实际上它是基于定点算法。
编辑 2
我现在明白乘法逆只能用于无余数的除法。例如，1 乘以 3-1 等于 3-1，而不是零。只有定点运算具有正确的舍入。
不幸的是，clang 没有使用任何 modular 算法，在这种情况下它只是一个 imul 指令，即使它可以。以下函数与上面的编译输出相同。
unsigned div3(unsigned x) {
__builtin_assume(x % 3 == 0);
return x / 3;
}
（关于适用于每个可能输入的精确除法的定点乘法逆元的规范问答：Why does GCC use multiplication by a strange number in implementing integer division? - 不完全重复，因为它只涵盖数学，而不是一些实现细节，如寄存器宽度和 imul 与 mul.)
What's up with the 33-bit right shift at the end? I thought we can just drop the highest 32-bits.
而不是 3^(-1) mod 3 你必须更多地考虑 0.3333333 其中 . 之前的 0 位于高 32 位和 3333位于低32位。
这个定点运算没问题，但是结果明显移到rax的上半部分，所以CPU运算后必须把结果再向下移
Why are we using imul instead of mul? I thought modular arithmetic would be all unsigned.
没有 MUL 指令等同于 IMUL 指令。使用的 IMUL 变体需要两个寄存器：
a <= a * b
没有 MUL 指令可以做到这一点。 MUL 指令更昂贵，因为它们将结果作为 128 位存储在两个寄存器中。
当然，您可以使用遗留指令，但这不会改变结果存储在两个寄存器中的事实。
- Can't we multiply rax with edi directly?
我们不能imul rax, rdi因为调用约定允许调用者在RDI的高位留下垃圾；只有 EDI 部分包含该值。内联时这是一个non-issue；将 32 位寄存器 做 隐式 zero-extend 到完整的 64 位寄存器，因此编译器通常不需要额外的指令来 zero-extend 一个 32-位值。
（zero-extend进入不同的寄存器更好，因为
从字面上看你的问题，不，x86 没有任何乘法指令 zero-extend 他们的输入之一可以让你乘以 32 位和 64 位寄存器。两个输入的宽度必须相同。
- Why do we multiply in 64-bit mode?
（术语：所有这些代码都在 64 位 模式下运行 。你问的是为什么 64 位 operand-size.)
您可以 mul edi 将 EAX 与 EDI 相乘以获得 64 位结果拆分 EDX:EAX，但 mul edi 在 Intel CPU 上是 3 微指令，而大多数现代 x86-64 CPU 具有快速 64 位 imul。 （尽管 imul r64, r64 在 AMD Bulldozer-family 和一些 low-power CPU 上较慢。） https://uops.info/ and https://agner.org/optimize/ （指令表和微架构 PDF）
（有趣的事实：mul rdi 在 Intel CPU 上实际上 更便宜 ，只有 2 微指令。可能与不必对整数乘法单元的输出进行额外拆分有关，像 mul edi 必须将 64 位低半乘法器输出分成 EDX 和 EAX 两半，但这对于 64x64 => 128 位乘法器自然会发生。）
此外，您需要的部分在 EDX 中，因此您需要另一个 mov eax, edx 来处理它。 （同样，因为我们正在查看函数的 stand-alone 定义的代码，而不是在内联到调用方之后。）
GCC 8.3 和更早版本 did 使用 32 位 mul 而不是 64 位 imul (https://godbolt.org/z/5qj7d5)。当 Bulldozer-family 和旧的 Silvermont CPU 更相关时，这对 -mtune=generic 来说并不疯狂，但是对于最近的 GCC，这些 CPU 已经过时了，它的通用调整选择反映了这一点。不幸的是，GCC 还浪费了一条 mov 指令将 EDI 复制到 EAX，使这种方式看起来更糟：/
# gcc8.3 -O3 (default -mtune=generic)
div3(unsigned int):
mov eax, edi # 1 uop, stupid wasted instruction
mov edx, -1431655765 # 1 uop (same 32-bit constant, just printed differently)
mul edx # 3 uops on Sandybridge-family
mov eax, edx # 1 uop
shr eax # 1 uop
ret
# total of 7 uops on SnB-family
在 mov eax, 0xAAAAAAAB / mul edi 时只有 6 微指令，但仍然比：
# gcc9.3 -O3 (default -mtune=generic)
div3(unsigned int):
mov eax, edi # 1 uop
mov edi, 2863311531 # 1 uop
imul rax, rdi # 1 uop
shr rax, 33 # 1 uop
ret
# total 4 uops, not counting ret
不幸的是，64 位 0x00000000AAAAAAAB 不能表示为 32 位 sign-extended 立即数，因此 imul rax, rcx, 0xAAAAAAAB 不可编码。这意味着 0xFFFFFFFFAAAAAAAB.
- Why are we using imul instead of mul? I thought modular arithmetic would be all unsigned.
它是无符号的。输入的符号仅影响结果的高半部分，但 imul reg, reg 不会产生高半部分。只有 mul 和 imul 的 one-operand 形式是 NxN => 2N 的完全乘法，所以只有它们需要单独的有符号和无符号版本。
只有 imul 具有更快更灵活的 low-half-only 形式。关于 imul reg, reg 唯一带符号的是它根据低半部分的带符号溢出设置 OF。不值得花费更多的操作码和更多的晶体管来拥有一个 mul r,r，它与 imul r,r 的唯一区别是 FLAGS 输出。
Intel的手册(https://www.felixcloutier.com/x86/imul)甚至指出可以用于unsigned。
- What's up with the 33-bit rightshift at the end? I thought we can just drop the highest 32-bits.
不，没有乘数常数可以为每个可能的输入给出准确的正确答案 x 如果您以这种方式实现它。 “as-if" 优化规则不允许近似值，只允许为程序使用的每个输入产生完全相同的可观察行为的实现。在不知道 x 的 value-range 而不是 unsigned 的完整范围的情况下，编译器没有该选项。 （-ffast-math 仅适用于浮点数；如果您想要更快的整数数学近似值，请像下面这样手动编码）：
有关 fixed-point 编译器用于按编译时间常数进行精确除法的乘法逆方法的更多信息，请参见 Why does GCC use multiplication by a strange number in implementing integer division?。
有关此 not 在一般情况下工作的示例，请参阅我对 Divide by 10 using bit shifts? 上的一个答案的编辑，该答案提议
// Warning: INEXACT FOR LARGE INPUTS
// this fast approximation can just use the high half,
// so on 32-bit machines it avoids one shift instruction vs. exact division
int32_t div10(int32_t dividend)
{
int64_t invDivisor = 0x1999999A;
return (int32_t) ((invDivisor * dividend) >> 32);
}
它的第一个错误答案（如果你从 0 向上循环）是 div10(1073741829) = 107374183，而 1073741829/10 实际上是 107374182。（它向上取整而不是像 C 整数除法应该的那样向 0 取整。）
从你的编辑中，我看到你实际上是在谈论使用乘法结果的 low 一半，这显然适用于一直到 [=140 的精确倍数=].
正如你所说，当除法有余数时，它完全失败了，例如16 * 0xaaaaaaab = 0xaaaaaab0 截断为 32 位时，不是 5.
unsigned div3_exact_only(unsigned x) {
__builtin_assume(x % 3 == 0); // or an equivalent with if() __builtin_unreachable()
return x / 3;
}
是的，如果该数学计算成功，编译器使用 32 位 imul 实现该计算将是合法且最佳的。他们不寻找这种优化，因为它很少为人所知。 IDK 如果值得添加编译器代码来寻找优化，就编译时间而言，更不用说开发人员时间的编译器维护成本了。这不是运行时成本的 巨大 差异，而且很少有可能。不过还是不错的。
div3_exact_only:
imul eax, edi, 0xAAAAAAAB # 1 uop, 3c latency
ret
但是，这是您可以自己做的事情源代码，至少对于已知的类型宽度，如 uint32_t:
uint32_t div3_exact_only(uint32_t x) {
return x * 0xaaaaaaabU;
}
如果你看看我对上一个问题的回答：
Why does GCC use multiplication by a strange number in implementing integer division?
它包含一篇 link 的 pdf 文章来解释这一点（我的回答澄清了这篇 pdf 文章中没有很好解释的内容）：
https://gmplib.org/~tege/divcnst-pldi94.pdf
请注意，某些除数需要额外的一位精度，例如 7，乘数通常需要 33 位，乘积通常需要 65 位，但这可以通过处理 2^32 来避免如我之前的回答及以下所示，分别使用 3 条附加说明进行操作。
换成
看看生成的代码unsigned div7(unsigned x) {
return x / 7;
}
为了解释这个过程，令 L = ceil(log2(divisor))。对于上面的问题，L = ceil(log2(3)) == 2。右移计数最初为 32+L = 34.
为了生成具有足够位数的乘数，生成了两个潜在的乘数：mhi 将是要使用的乘数，移位计数将为 32+L。
mhi = (2^(32+L) + 2^(L))/3 = 5726623062
mlo = (2^(32+L) )/3 = 5726623061
然后检查是否可以减少所需的位数：
while((L > 0) && ((mhi>>1) > (mlo>>1))){
mhi = mhi>>1;
mlo = mlo>>1;
L = L-1;
}
if(mhi >= 2^32){
mhi = mhi-2^32
L = L-1;
; use 3 additional instructions for missing 2^32 bit
}
... mhi>>1 = 5726623062>>1 = 2863311531
... mlo>>1 = 5726623061>>1 = 2863311530 (mhi>>1) > (mlo>>1)
... mhi = mhi>>1 = 2863311531
... mlo = mhi>>1 = 2863311530
... L = L-1 = 1
... the next loop exits since now (mhi>>1) == (mlo>>1)
因此乘数为 mhi = 2863311531，移位计数 = 32+L = 33。
在现代 X86 上，乘法和移位指令是常数时间的，因此将乘法器 (mhi) 减少到小于 32 位是没有意义的，所以上面的 while(...) 被更改为 if( ...).
在7的情况下，循环在第一次迭代时退出，需要3条额外的指令来处理2^32位，所以mhi <= 32位：
L = ceil(log2(7)) = 3
mhi = (2^(32+L) + 2^(L))/7 = 4908534053
mhi = mhi-2^32 = 613566757
设ecx = dividend，简单的方法可能会溢出：
mov eax, 613566757 ; eax = mhi
mul ecx ; edx:eax = ecx*mhi
add edx, ecx ; edx:eax = ecx*(mhi + 2^32), potential overflow
shr edx, 3
为避免潜在的溢出，请注意 eax = eax*2 - eax:
(ecx*eax) = (ecx*eax)<<1) -(ecx*eax)
(ecx*(eax+2^32)) = (ecx*eax)<<1)+ (ecx*2^32)-(ecx*eax)
(ecx*(eax+2^32))>>3 = ((ecx*eax)<<1)+ (ecx*2^32)-(ecx*eax) )>>3
= (((ecx*eax) )+(((ecx*2^32)-(ecx*eax))>>1))>>2
所以实际代码，使用 u32() 表示高 32 位：
... visual studio generated code for div7, dividend is ecx
mov eax, 613566757
mul ecx ; edx = u32( (ecx*eax) )
sub ecx, edx ; ecx = u32( ((ecx*2^32)-(ecx*eax)) )
shr ecx, 1 ; ecx = u32( (((ecx*2^32)-(ecx*eax))>>1) )
lea eax, DWORD PTR [edx+ecx] ; eax = u32( (ecx*eax)+(((ecx*2^32)-(ecx*eax))>>1) )
shr eax, 2 ; eax = u32(((ecx*eax)+(((ecx*2^32)-(ecx*eax))>>1))>>2)
如果需要余数，可以采用以下步骤：
mhi and L are generated based on divisor during compile time
...
quotient = (x*mhi)>>(32+L)
product = quotient*divisor
remainder = x - product
x/3 大约是 (x * (2^32/3)) / 2^32。所以我们可以执行一次 32x32->64 位乘法，取高 32 位，得到大约 x/3.
存在一些错误，因为我们无法精确乘以 2^32/3，只能乘以四舍五入为整数的数字。我们使用 x/3 ≈ (x * (2^33/3)) / 2^33 获得更高的精度。 （我们不能使用 2^34/3，因为它大于 2^32）。事实证明，这足以在所有情况下准确地获得 x/3。如果输入是 3k 或 3k+2.
，您可以通过检查公式给出结果 k 来证明这一点