我一直在阅读有关div和mul汇编操作的信息，我决定通过用 C 编写一个简单的程序来查看它们的实际效果：
文件划分.c
#include <stdlib.h>
#include <stdio.h>
int main()
{
size_t i = 9;
size_t j = i / 5;
printf("%zun",j);
return 0;
}
然后生成汇编语言代码：
gcc -S division.c -O0 -masm=intel
但是查看生成的division.s文件，它不包含任何div操作！相反，它用位移位和魔术数字做某种黑魔法。下面是一个计算i/5的代码片段：
mov rax, QWORD PTR [rbp-16] ; Move i (=9) to RAX
movabs rdx, -3689348814741910323 ; Move some magic number to RDX (?)
mul rdx ; Multiply 9 by magic number
mov rax, rdx ; Take only the upper 64 bits of the result
shr rax, 2 ; Shift these bits 2 places to the right (?)
mov QWORD PTR [rbp-8], rax ; Magically, RAX contains 9/5=1 now,
; so we can assign it to j
这是怎么回事？为什么 GCC 根本不使用div？它如何生成这个神奇的数字，为什么一切正常？
整数除法是现代处理器上可以执行的最慢的算术运算之一，延迟高达数十个周期，吞吐量较差。 (对于 x86，请参阅 Agner Fog 的说明表和微拱指南)。
如果您提前知道除数，则可以通过将除数替换为一组具有等效效果的其他运算(乘法、加法和移位)来避免除法。即使需要多次操作，它通常仍然比整数除法本身快得多。
以这种方式实现 C/运算符，而不是使用涉及div的多指令序列，这只是 GCC 除以常量的默认方式。 它不需要跨操作进行优化，甚至不会更改任何内容以进行调试。 (不过，使用-Os表示较小的代码大小确实会让GCC使用div。 使用乘法逆而不是除法就像使用lea而不是mul和add
因此，只有在编译时不知道除数时，您才会在输出中看到div或idiv。
有关编译器如何生成这些序列的信息，以及让您自己生成这些序列的代码(除非您使用的是 braindead 编译器，否则几乎肯定是不必要的)，请参阅 libdivide。
除以5 与乘以 1/5 相同，这与乘以 4/5 并向右移动 2 位相同。相关值以十六进制CCCCCCCCCCCCCCCD，如果放在十六进制点之后，则为 4/5 的二进制表示(即五分之四的二进制0.110011001100重复出现 - 请参阅下文了解原因)。我想你可以从这里拿走它！您可能想查看定点算法(但请注意，它在末尾四舍五入为整数)。
至于为什么，乘法比除法快，当除数固定时，这是一条更快的路线。
请参阅倒数乘法，这是一个教程，详细介绍了它的工作原理，并用定点进行了解释。 它显示了查找倒数的算法如何工作，以及如何处理有符号除法和模。
让我们考虑一下为什么0.CCCCCCCC...(十六进制)或0.110011001100...二进制是 4/5。将二进制表示除以 4(右移 2 位)，我们将得到0.001100110011...通过琐碎的检查可以添加原始表示得到0.111111111111...，这显然等于 1，就像十进制中的0.9999999...等于 1 一样。因此，我们知道x + x/4 = 1，所以5x/4 = 1，x=4/5。然后用十六进制表示为四舍五入的CCCCCCCCCCCCD(因为超出最后一个存在的二进制数字将是1)。
一般来说，乘法比除法快得多。因此，如果我们能侥幸乘以倒数，我们可以显着加快除以常数的速度。
一个问题是我们不能准确地表示倒数(除非除法是 2 的幂，但在这种情况下，我们通常可以将除法转换为位移)。因此，为了确保答案正确，我们必须小心，确保倒数中的错误不会导致最终结果中的错误。
-3689348814741910323 是 0xCCCCCCCCCCCCCCCD 这是一个刚刚超过 4/5 的值，以 0.64 个固定点表示。
当我们将一个 64位整数乘以一个 0.64 的不动点数时，我们得到 64.64 的结果。我们将值截断为 64 位整数(有效地将其四舍五入为零)，然后执行进一步的移位，除以 4 并再次截断 通过查看位级别，很明显我们可以将两个截断视为单个截断。
这显然至少给了我们除以 5 的近似值，但它是否给了我们一个正确舍入到零的确切答案？
为了获得确切的答案，误差需要足够小，以免将答案推过舍入边界。
除以 5 的确切答案将始终具有 0、1/5、2/5、3/5 或 4/5 的小数部分。因此，乘法和移位结果中小于 1/5 的正误差永远不会将结果推过舍入边界。
常量的误差为 (1/5) *2-64。i的值小于 264，因此乘法后的误差小于 1/5。除以 4 后，误差小于 (1/5) * 2−2。
(1/5) * 2−2<1/5 所以答案将始终等于做一个精确的除法并四舍五入到零。
不幸的是，这并不适用于所有除数。
如果我们尝试将 4/7 表示为 0.64 的不动点数，并从零四舍五入，我们最终会得到 (6/7) *2-64的误差。乘以略低于 264的 i 值后，我们最终得到的误差略低于 6/7，除以 4 后，我们最终得到的误差略低于 1.5/7，大于 1/7。
因此，要正确实现除以 7，我们需要乘以 0.65 的不动点数。我们可以通过乘以定点数的较低 64 位，然后添加原始数字(这可能会溢出到进位)然后通过进位进行旋转来实现这一点。
这是一个算法文档的链接，该算法生成我在Visual Studio中看到的值和代码(在大多数情况下)，并且我认为这些值和代码仍在GCC中用于将变量整数除以常量整数。
http://gmplib.org/~tege/divcnst-pldi94.pdf
在文章中，一个 uword 有 N 位，一个 udword 有 2N 位，n = 分子 = 除数，d = 分母 = 除数，l 最初设置为 ceil(log2(d))，shpre 是预移位(在乘法之前使用)= e = d 中尾随零位的数量，shpost 是后移位(乘法后使用)，prec 是精度 = N - e = N - shpre。目标是使用移位前、乘法和移位后优化 n/d 的计算。
向下滚动到图 6.2，它定义了如何生成 udword 乘数(最大大小为 N+1 位)，但没有清楚地解释该过程。我将在下面解释这一点。
图4.2 和图 6.2 显示了如何将大多数除数的乘数减少到 N 位或更小的乘数。等式4.5解释了图4.1和4.2中用于处理N+1位乘法器的公式是如何推导的。
在现代 X86 和其他处理器的情况下，乘法时间是固定的，因此预移位对这些处理器没有帮助，但它仍然有助于将乘法器从 N+1 位减少到 N 位。我不知道GCC或Visual Studio是否已经取消了X86目标的预移位。
回到图 6.2。只有当分母(除数)> 2^(N-1) 时(当 l == N => mlow = 2^(2N)时)，mlow 和 mhigh 的分子(除数)才能大于 udword，在这种情况下，n/d 的优化替换是比较(如果 n>=d，q = 1，否则 q = 0)，因此不会生成乘数。mlow 和 mhigh 的初始值为 N+1 位，两个 udword/uword 除法可用于生成每个 N+1 位值(mlow 或 mhigh)。以 64 位模式下的 X86 为例：
; upper 8 bytes of dividend = 2^(ℓ) = (upper part of 2^(N+ℓ))
; lower 8 bytes of dividend for mlow = 0
; lower 8 bytes of dividend for mhigh = 2^(N+ℓ-prec) = 2^(ℓ+shpre) = 2^(ℓ+e)
dividend dq 2 dup(?) ;16 byte dividend
divisor dq 1 dup(?) ; 8 byte divisor
; ...
mov rcx,divisor
mov rdx,0
mov rax,dividend+8 ;upper 8 bytes of dividend
div rcx ;after div, rax == 1
mov rax,dividend ;lower 8 bytes of dividend
div rcx
mov rdx,1 ;rdx:rax = N+1 bit value = 65 bit value
您可以使用 GCC 对此进行测试。您已经看到了如何处理 j = i/5。看看如何处理 j = i/7(应该是 N+1 位乘法器的情况)。
在大多数当前的处理器上，乘法具有固定的时序，因此不需要预移位。对于 X86，最终结果是大多数除数的双指令序列，以及除数(如 7)的五指令序列(为了模拟 N+1 位乘法器，如 pdf 文件的等式 4.5 和图 4.2 所示)。示例 X86-64 代码：
; rbx = dividend, rax = 64 bit (or less) multiplier, rcx = post shift count
; two instruction sequence for most divisors:
mul rbx ;rdx = upper 64 bits of product
shr rdx,cl ;rdx = quotient
;
; five instruction sequence for divisors like 7
; to emulate 65 bit multiplier (rbx = lower 64 bits of multiplier)
mul rbx ;rdx = upper 64 bits of product
sub rbx,rdx ;rbx -= rdx
shr rbx,1 ;rbx >>= 1
add rdx,rbx ;rdx = upper 64 bits of corrected product
shr rdx,cl ;rdx = quotient
; ...
为了解释 5 指令序列，一个简单的 3 指令序列可能会溢出。设 u64() 表示高 64 位(商所需的全部)
mul rbx ;rdx = u64(dvnd*mplr)
add rdx,rbx ;rdx = u64(dvnd*(2^64 + mplr)), could overflow
shr rdx,cl
为了处理这种情况，cl = post_shift-1。 rax = 乘数 - 2^64，RBX = 股息。 u64() 是高 64 位。请注意，rax = rax<<1 - rax。商数为：
u64( ( rbx * (2^64 + rax) )>>(cl+1) )
u64( ( rbx * (2^64 + rax<<1 - rax) )>>(cl+1) )
u64( ( (rbx * 2^64) + (rbx * rax)<<1 - (rbx * rax) )>>(cl+1) )
u64( ( (rbx * 2^64) - (rbx * rax) + (rbx * rax)<<1 )>>(cl+1) )
u64( ( ((rbx * 2^64) - (rbx * rax))>>1) + (rbx*rax) )>>(cl ) )
mul rbx ; (rbx*rax)
sub rbx,rdx ; (rbx*2^64)-(rbx*rax)
shr rbx,1 ;( (rbx*2^64)-(rbx*rax))>>1
add rdx,rbx ;( ((rbx*2^64)-(rbx*rax))>>1)+(rbx*rax)
shr rdx,cl ;((((rbx*2^64)-(rbx*rax))>>1)+(rbx*rax))>>cl
我会从一个稍微不同的角度回答：因为它是允许这样做的。
C 和 C++ 是针对抽象机器定义的。编译器按照 as-if 规则将抽象机器转换为具体机器。
- 允许编译器进行任何更改，只要它不更改抽象机器指定的可观察行为。没有合理的期望编译器会以最直接的方式转换你的代码(即使许多 C 程序员都假设这一点)。通常，这样做是因为编译器希望与直接方法相比优化性能(如其他答案中详细讨论的那样)。 如果在任何情况下编译器将
- 正确的程序"优化"为具有不同可观察行为的内容，那就是编译器错误。
- 我们的代码中任何未定义的行为(有符号整数溢出是一个经典示例)和此合约都是无效的。