如何使用位移操作代替整数除法？

Question

我知道如何处理二的幂，所以这不是我的问题。

例如，如果我想使用位移而不是整数除法来找到一个数的5％，该怎么计算？

因此，我可以使用(x * 100 >> 11)代替(x * 20 / 19).现在这不正确，但它接近，并且我是通过试验和错误得出的。 如何确定要使用的最精确移位？

- glutz78

---

为什么？这是为了优化吗？你正在优化什么？你确定它需要被优化吗？ - Jonathan Grynspan

你为什么认为这是可能的？ - mikerobi

@Jonathan：+1；无论是什么，那都不是优化... :) - Amadan

@Potatoswatter：不，x * 100 >> 11 是 x * 100 / 2048，即 x * .048828125，这是对5%的合理近似。如brainjam所指出的那样，x * 102 >> 11 更好，但是 x * 51 >> 10 同样好且更不容易溢出，而 x * 205 >> 12 的误差要小得多。 - Ben Voigt

此外，这有时是一种有效的优化方法。如果您必须将大量值乘以相同但可变的分数，则将除法转换为复杂的乘法可以提高性能。 - Potatoswatter

Answer 1

最好的方法是让编译器替你完成。你只需写：

a/b

使用您选择的编程语言，编译器将生成位操作。

编辑（希望您不介意，我在加强您的答案：

#include <stdio.h>

int main(int argc, char **argv) {
  printf("%d\n", argc/4);
}

显然，最快的方法是argc>>2。让我们看看会发生什么：

        .file   "so3.c"
        .section        .rodata
.LC0:
        .string "%d\n"
        .text
.globl main
        .type   main, @function
main:
        pushl   %ebp
        movl    %esp, %ebp
        andl    $-16, %esp
        subl    $16, %esp
        movl    8(%ebp), %eax
        movl    %eax, %edx
        sarl    $31, %edx
        shrl    $30, %edx
        leal    (%edx,%eax), %eax
        sarl    $2, %eax
        movl    %eax, %edx
        movl    $.LC0, %eax
        movl    %edx, 4(%esp)
        movl    %eax, (%esp)
        call    printf
        leave
        ret
        .size   main, .-main
        .ident  "GCC: (Ubuntu 4.4.3-4ubuntu5) 4.4.3"
        .section        .note.GNU-stack,"",@progbits

没错，这就是它：sarl $2, %eax

编辑2（抱歉再提一句，但20/19有点复杂...）

我刚刚将argc*20/19替换为argc/4，以下是得出的数学结果：

0000000100000f07        shll    $0x02,%edi
0000000100000f0a        movl    $0x6bca1af3,%edx
0000000100000f0f        movl    %edi,%eax
0000000100000f11        imull   %edx
0000000100000f13        sarl    $0x03,%edx
0000000100000f16        sarl    $0x1f,%edi
0000000100000f19        subl    %edi,%edx

因此，该过程为

• 将输入乘以4（shll）
• 加载（movl 0x...）并通过固定点分数进行乘法（imull），得到64位结果（这是32位代码）
• 将结果的高32位除以8（sarl），注意处理负数的方式
• 将结果的低32位除以INT_MAX（sarl），以获取0或-1
• 通过添加1（减去-1），正确地对高位结果进行舍入，如果必要的话。

- High Performance Mark

---

+1 - 手动计算每个细节都是一项费力的工作，学习过程中最好的方法是查看编译后的输出。 - Potatoswatter

我添加了编译器输出，以展示你是多么正确！ - SingleNegationElimination

@Potatoswatter：我从你的努力中获得了很多声望，感觉有点不好意思。虽然不是非常糟糕，但也让我有点失眠。 - High Performance Mark

@Mark：哎，如果我花时间用一般性的术语来描述它，那会更有帮助。让声誉实际上决定任何事情是没有意义的。 - Potatoswatter

Answer 2

这没有意义，因为你试图做的并没有优化结果的过程！！！

嘿，我在你的问题中没有看到你有意愿进行优化。

电气工程师永远不会停止好奇心，无论“有用性”如何。我们就像强迫性的沉迷者，他们收集各种物品，你可以在新闻中读到他们把阁楼、地下室、卧室和客厅都堆满了垃圾，他们相信某一天这些东西会有用。至少在我30年前上工程学院时是这样的。我鼓励你继续探索收集“无用”的知识，即使它似乎对优化你的生活或生活方式几乎没有可能性。为什么要依赖编译器，当你可以通过手写算法来完成呢？！是吗？要有一点冒险精神，你知道的。 好了，够了，别再批评那些对你追求知识表示轻蔑的人了。

还记得你在初中时学习除法的方法吗？例如437/24。

  _____
24|437


   018
  -----
24|437
   24
  -----
   197
    24
  -----
     5

被除数为437，除数为24，商为18，余数为5。在填写税表时，您需要填写从股票“分红”中获得的利润，这是一个错误的名称。您在税表中填写的是单个巨大被除数的商的倍数。您没有收到全部的被除数，而是其中的一部分 - 否则，这意味着您拥有该股票的100％。

     ___________
11000|110110101



      000010010
     -----------
11000|110110101 
      11000
     ----------
      000110101 remainder=subtract divisor from dividend
       11000000 shift divisor right and append 0 to quotient until
        1100000 divisor is not greater than remainder.
         110000 Yihaa!
     ----------
         000101 remainder=subtract shifted divisor from remainder
          11000 shift divisor right and append 0 to quotient until
           1100 divisor is not greater than remainder.
     ----------
               oops, cannot shift anymore.

你可能已经知道，上述是真正的除法。这是通过减去一个移位的除数来实现的。

你想要的是仅仅通过移位被除数来实现相同的结果。不幸的是，除非除数是2的指数幂（2、4、8、16），否则无法做到这一点。这是二进制算术的一个显而易见的事实。或者说，我不知道是否有任何方法可以在不使用近似和内插技术的情况下完成它。

因此，你必须使用被除数移位和真正的除法的组合。 例如：

24 = 2 x 2 x 2 x 3

首先，使用二进制位移将437除以8得到010010，然后使用真实的除法将其除以3：

   010010
  --------
11|110110
   11
   -------
     011
      11
     -----
        0

这意味着010010 = 18。

完成了。

如何确定24 = 2^8 x 3？

通过向右移动11000，直到遇到1。

这意味着，您可以将被除数向右移动与将除数移动相同的次数，直到除数遇到1。

因此，显然，如果除数是奇数，则此方法将不起作用。 例如，对于除数25，它将不起作用，但对于除数50，它将起点作用。

也许有一些预测性的方法可以将诸如13之类的除数插入到2^3=8和2^4=16之间。如果有，我不熟悉。

您需要探索的是使用数字系列。例如，除以25：

 1    1    1     1     1
__ = __ - ___ - ___ + ___ -  ... until the precision you require.
25   16   64    128   256

其中序列的一般形式为

1    1      b1              bn
_ = ___ + _______ + ... + ______
D   2^k   2^(k+1)         2^(k+n)

其中bn为-1、0或+1。

我希望上面的二进制操作没有错误或笔误。如果有的话，请多多包涵。

- Blessed Geek

Answer 3

假设您有表达式a = b / c。如hroptatyr所提到的，乘法非常快（比除法快得多）。因此，基本思路是将除法转换为乘法，如下：a = b * (1/c)。

现在，我们仍然需要使用除法计算倒数1/c，因此这只适用于已知c的情况。虽然对于浮点运算来说足够了，但对于整数运算，我们必须使用另一个技巧：我们可以使用值some_big_number / c的倒数作为c的倒数，这样最终我们将计算a2 = b * (some_big_number / c)，它等于some_big_number * b/c。因为我们关心的是b/c的值，所以必须将最终结果除以some_big_number。如果some_big_number被选择为2的幂，则最终的除法将很快。

例如：

// we'll compute 1/20 of the input
unsigned divide_by_20(unsigned n){
    unsigned reciprocal = (0x10000 + 20 - 1) / 20; //computed at compile time, but you can precompute it manually, just to be sure
    return (n * reciprocal) >> 16;
}

编辑：这种方法的好处是，您可以通过选择校正（在本例中为20-1以向零舍入）来选择除法的任何舍入方法。

- ruslik

---

对于有符号值，除以65536而不是移位16位，编译器将转换为移位和修复。 - ergosys

@ergosys 应该是除以65536u。否则，即使编译器将其优化为移位操作，它仍会生成额外的代码来处理有符号整数的除法。这是在除以整数常量的代码中常见的缺陷。 - undefined

Answer 4

如果您对其背后的数学感兴趣，请阅读Henry S. Warren的《Hacker's Delight》。

如果您对优化的代码感兴趣，只需编写最易于人类阅读的内容。例如：

int five_percent(int x) {
  return x / 20;
}

当您使用g++ -O2编译此函数时，它不会进行实际的除法运算，而是进行一些神奇的乘法、位移和校正。

- Roland Illig

Answer 5

您不能仅使用移位完成所有操作，您需要使用“神奇”的除数（请参阅《黑客的乐趣》）。神奇除法是通过将一个数字乘以另一个适当大的数字，并以一种使得答案为除法的方式滚动它来工作的（mul/imul比div/idiv更快）。这些神奇常数对于每个质数只有唯一的值，多个常数需要移位。例如：在32位上，无符号除以3可以表示为x * 0xAAAAAAAB，除以6可以表示为(x * 0xAAAAAAAB) >> 1，除以12需要移2位，24需要移3位等（它是几何级数3 * (2 ^ x)，其中0 <= x < 32）

- Necrolis

Answer 6

假设您想通过将x乘以y并移位n来近似5％的x。由于5％是1/20，且a>>n = a/2^n，您需要解决以下问题：

x/20 ≈ x*y/2^n（符号“≈”表示“大约相等”）

这简化为：

y ≈ 2^n/20

因此，如果n=11，则

y ≈ 2^n/20 = 2048/20 =102 + 8/20

因此，我们可以将y设置为102，这实际上比您通过试错找到的100更好。

一般来说，我们可以尝试不同的n值，看是否能得到更好的答案。

我已经为分数1/20解决了这个问题，但您应该能够按照相同的方法解决任何分数p/q的问题。

- brainjam

Answer 7

一般而言：

• 获取数字的质因数分解，将 N 分解为 2^k * rest，然后可以在这两个幂上使用位移。例如：20 = 2^2 * 5，所以要乘以二十，你需要先乘以 5，然后使用位移 << 2
• 对于非二次幂的位移操作，观察以下奇数 l 的情况：a * l = a * (l - 1) + a，现在 l - 1 是偶数，因此可以分解为一个二次幂，对其应用位移“技巧”。

除法可以类似地构造。

- hroptatyr

---

这没有意义。乘以5包括任何移位<<2的成本。这里的目标是使用一到两个指令乘以任何有理数，而不是分解数字并使用无限数量的指令。 - Potatoswatter

谁说的？原帖的作者想知道如何将整数乘法转换为位移，我刚刚描述了一般的步骤。 - hroptatyr

哦，顺便说一下，在你测量之前不要评判，我刚刚发现在我的CPU上使用imul需要3个周期，而我的解决方案使用shl和add只需要2个周期。 - hroptatyr

一个 shl 和一个 add 只能实现乘以5的操作。你仍然需要另一个指令来再次进行移位。编译器应该足够聪明，能够判断出是否真的需要 imul 指令，如果不需要就不生成它，尽管为了可移植性，它可能没有针对你的芯片进行特殊优化，而更高的指令计数可能会导致其他拥堵。 - Potatoswatter

无论如何，问题并不在于替换乘法而是除法，你根本没有解决这个问题。这需要获取乘法的高位结果，这不能使用C运算符表示。（至少，不能获得整数寄存器的完整宽度。）这是一个定点数学技巧。 - Potatoswatter