除法是现代处理器中最昂贵的操作之一。 您不必走太远就可以证明：Agner Fog [
1 ]广播说，在Intel / AMD处理器上，我们可以轻松地在25-119个时钟周期内获得Latency，而倒数在25-120之间。 翻译成俄语-
慢 ！ 但是，仍有机会避免代码中的除法指令。 在本文中，我将告诉您它是如何工作的，尤其是在现代编译器中（它们已经能够做到20年了），并且还将告诉您如何利用所获得的知识来使代码更好，更快，更强大。
实际上，我在说的是：如果除数在编译阶段是已知的，则可以用乘法和向右逻辑移位来代替整数除法（有时您完全可以不用它-我肯定是在谈论编程语言的实现）。 这听起来非常令人鼓舞：整数乘法和向右移位（例如，Intel Haswell）的操作将不超过5个时钟周期。 仍然仅了解例如如何通过将整数除以10来通过整数乘法和向右逻辑移位来获得相同的结果？ 这个问题的答案在于理解...定点算法（以下简称FPA）。 一些基础知识。
使用FP时，指数（指数2 =>点在数字的二进制表示形式中的位置）没有保存在数字中（与浮点算法不同，请参阅IEE754），但是它被认为是程序员已知的一些已达成共识的数量。 仅保留尾数（小数点后的尾数）。 一个例子：
0.1-以二进制表示法具有“无限表示法”，在上例中用括号表示-该部分将不时重复，以0.1的二进制FP表示法互相跟随。在上面的示例中，如果我们使用16位寄存器来存储FP编号，则无法在不损失精度的情况下将数字0.1的FP表示拟合到这样的寄存器中，这反过来将影响涉及该寄存器值的所有进一步计算的结果。
假设我们给了B一个16位的整数A和一个16位的小数部分。A与B的乘积得到一个整数部分为16位而小数部分为16位的数字。 显然，仅获得整数部分，您需要将结果向右移动16位。
恭喜，FPA的介绍已经结束。
我们形成以下假设：将整数除以10，我们需要将可除数与数字0.1的FP表示相乘，取整数部分和戴帽子的东西……等等……但是结果将是准确的，更准确地说是其整数部分吗？ -毕竟，我们记得，在我们的内存中仅存储了数字0.1的近似版本。 下面我写了数字0.1的三种不同表示形式：数字0.1的无限精确表示形式，在第16位后舍入不进行舍入，数字0.1的表示形式，在第16位之后进行舍入并舍入后即数字0.1的表示。
让我们估计截断数字0.1的错误：
为了使整数A乘以近似值0.1得出精确的整数部分，我们需要：
要么
使用第一个表达式更方便：when
我们总是会得到身份（但是，请注意，在这个问题的框架内，并非所有决定都绰绰有余）。 解决，我们得到
。 也就是说，将任意14位数字A乘以舍入并舍入到0.1的表示，总是得到精确的整数部分，这将通过将0.1无限精确地乘以A而得到。但是，按照惯例，我们将16位数字乘以这意味着，在我们的情况下，答案将是不准确的，并且我们不能通过舍入为0.1舍入来简单乘法。 现在，如果我们可以在FP表示中保存数字0.1而不是16位，而是19、20，那么一切都会好起来的。 毕竟我们可以！
我们仔细查看二进制表示形式-舍入为0.1舍入：最高的三个位为零，这意味着它们对乘法结果（新位）没有任何贡献。
因此，我们可以将数字向左移动三位，向上舍入，然后在进行乘法和逻辑右移之后，首先向左移动16位，然后向右移动3位（即通常一次乘以19位）-我们得到了所需的精确整数部分。 这种“ 19”位乘法正确性的证明与先前的相似，唯一的区别是，它可以正确地用于16位数字。 对于容量更大的数字，不仅对于除以10的数字，也是如此。
较早前，我曾写道，通常来说，您可以完全不做任何改变，而只限于乘法。 怎么了 鼓上的汇编程序x86 / x64：
在现代处理器中，有一个MUL命令（也有IMUL类似物，MULX-BMI2），该命令采用一个参数（例如32/64位），能够执行64/128位乘法，将结果分成两部分保存在两个寄存器中（最高32/64位）以及更小）：
MUL RCX ; RCX RAX, (128 ) RDX:RAX
假设将一些62位整数A存储在RCX寄存器中，并将舍入为0.1的舍入的64位FA表示存储在RAX寄存器中（请注意，没有左移）。 完成64位乘法之后，我们得到结果的最高64位存储在RDX寄存器中，或更确切地说，存储在整数部分中，这对于62位数字而言是精确的。 也就是说，不需要向右移动（SHR，SHRX）。 这种转移的存在会加载处理器的管道，而无论其是否支持OOOO：至少在这种依赖关系中很可能已经很长的链（也称为依赖链）中存在额外的依赖。 在这里，非常重要的一点是，现代编译器看到some_integer / 10形式的表达式时，会自动为整个可分割数字范围生成汇编代码。 也就是说，如果您知道自己始终有53位数字（这正是我的任务中所使用的方式），那么您仍然会获得额外的移位指令。 但是，既然您了解了它是如何工作的，那么您就可以轻松地用乘法代替除法运算，而不必依赖编译器的摆布。 顺便说一下，在C ++代码中获得64位乘积的高位是通过mulh之类的东西来实现的，根据asm代码，mulh应该等同于上面的{I} MUL {X}指令的行。
也许随着合同的到来（在C ++ 20中我们不在等待），情况会有所改善，在某些情况下，我们可以信任汽车！ 尽管这是C ++，但程序员负责这里的所有工作-并非如此。
上面描述的推理-适用于常量的任何因数，下面是有用链接的列表：
[1] https://www.agner.org/optimize/instruction_tables.pdf[2]比艾格纳·福格（Anerner Fogh）更加坚强[3]电报频道，其中包含有关Intel / AMD / ARM优化的有用信息[4]完全关于划分，但是用英语