为什么GCC在执行整数除法时使用奇数乘法？
我一直在阅读关于div和mul汇编操作，我决定通过在C：
文件分割
#include <stdlib.h> #include <stdio.h> int main() { size_t i = 9; size_t j = i / 5; printf("%zu\n",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的指令表和微指南 ）。
如果提前知道除数，则可以通过将其replace为具有相同效果的其他操作（乘法，加法和移位）来避免该除法。 即使需要几个操作，它仍然比整数部分本身快得多。
以这种方式实现C /运算符，而不是使用涉及div的多指令序列，只是GCC用常量进行除法的默认方式。 它不需要跨操作优化，即使debugging也不会改变任何东西。 （使用小代码大小的-Os确实可以让GCC使用div 。）使用乘法反而不是除法，就像使用lea代替mul并add
因此，如果在编译时不知道除数，则只会倾向于在输出中看到div或idiv 。
有关编译器如何生成这些序列的信息，以及让您自己生成这些序列的代码（除非使用braindead编译器，几乎肯定是不必要的），请参阅libdivide 。
除以5就等于乘以1/5，这与乘以4/5和右移2位相同。 值是hex的0.110011001100 ，如果放在一个hex的点之后（即二进制五分之一是0.110011001100重复出现 – 见下面的原因），它是4/5的二进制表示。 我想你可以从这里拿走它！ 你可能想要检查一下定点算术 （尽pipe注意在最后四舍五入为整数）。
至于为什么，乘法比分割快，当除数是固定的，这是一个更快的路线。
请参阅“ 互惠乘法”，它是关于如何工作的详细写法教程 ，以定点说明。 它展示了如何find相互作用的algorithm，以及如何处理带符号的分割和模。
让我们考虑一下为什么0.CCCCCCCC... （hex）或0.110011001100...二进制是4/5。 将二进制表示除以4（右移2位），得到0.001100110011... ，通过平凡的检查可以得到原来的0.111111111111... ，这显然等于1，同样的方法是0.9999999...在十进制等于一个。 因此，我们知道x + x/4 = 1 ，所以5x/4 = 1 ， x=4/5 。 然后在hex中将其表示为CCCCCCCCCCCCD （因为超出最后一个的二进制数字将是1 ）。
-3689348814741910323是0xCCCCCCCCCCCCCCCD，它是在0.64定点上刚刚超过4/5的值。
当我们将64位整数乘以0.64的定点数时，我们得到了64.64的结果。 我们将值截断为64位整数（有效地将其舍入为零），然后执行进一步的移位，再除以4再截断。通过查看位级别，可以清楚地看到，我们可以将两个截断视为单个截断。
这显然给了我们至less一个5除法的近似值，但它是否给了我们一个正确的答案正确地舍入零？
为了得到一个确切的答案，错误需要足够小，不要在舍入边界上推回答。
5除法的确切答案总是有0,1 / 5,2 / 5,3 / 5或4/5的小数部分。 因此，乘积和移位结果中小于1/5的正误差绝不会将结果推到舍入边界上。
我们常数的误差是（1/5）* 2 -64 。 i的值小于2 64，因此乘法后的误差小于1/5。 除以4后，误差小于（1/5）* 2 -2 。
（1/5）* 2 -2 <1/5，所以答案总是等于做一个精确的划分和向零取整。
不幸的是，这并不适用于所有的因数。
如果我们试图用四舍五入的方法来代表4/7为0.64的定点数，那么我们最终会得到（6/7）* 2 -64的误差。 乘以一个小于2 64的i值后，我们将得到一个刚好在6/7以下的误差，在除以4之后，我们将得到一个大于1/7的刚好在1.5 / 7以下的误差。
所以为了正确执行分割，我们需要乘以一个0.65的定点数。 我们可以通过乘以我们定点数的低64位，然后加上原来的数字（这可能溢出到进位位），然后通过进位进行旋转。
这里是链接到一个algorithm的文档，它产生了我用Visual Studio看到的值和代码（在大多数情况下），并且我假设仍然在GCC中用一个常量整数除法variables整数。
在文章中，一个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显示了如何将乘数减less到大多数除数的N位或更less的乘数。 公式4.5解释了如何导出图4.1和4.2中用于处理N + 1位乘法器的公式。
回到图6.2。 只有除数> 2 ^（N-1）（当l == N时）分子才能大于udword，在这种情况下，n / d的优化replace是比较（如果n> = d，q = 1 ，否则q = 0），所以不会生成乘数。 mlow和mhigh的初始值将是N + 1位，并且可以使用两个udword / uword除法来产生每个N + 1位值（mlow或mhigh）。 以64位模式使用X86为例：
; upper 8 bytes of numerator = 2^(ℓ) = (upper part of 2^(N+ℓ)) ; lower 8 bytes of numerator for mlow = 0 ; lower 8 bytes of numerator for mhigh = 2^(N+ℓ-prec) = 2^(ℓ+shpre) = 2^(ℓ+e) numerator dq 2 dup(?) ;16 byte numerator divisor dq 1 dup(?) ; 8 byte divisor ; ... mov rcx,divisor mov rdx,0 mov rax,numerator+8 ;upper 8 bytes of numerator div rcx ;after div, rax == 1 mov rax,numerator ;lower 8 bytes of numerator div rcx mov rdx,1 ;rdx:rax = N+1 bit value = 65 bit value
你可以用GCC来testing。 你已经看到了如何处理j = i / 5。 看看如何处理j = i / 7（这应该是N + 1位乘法器的情况）。
