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

Question

我知道如何为2的权力做到这一点,所以这不是我的问题.

例如,如果我想使用位移而不是整数除法找到5%的数字,我将如何计算？

因此,我可以做(x*100 >> 11)而不是(x*20/19).现在这不对,但它很接近,我通过反复试验来到它.我如何确定最可能使用的精确班次？

Answer 1

最好的方法是让编译器为你做.你只是写

a/b

用您选择的语言,并编译器生成位twiddling.

编辑(我希望你不介意,我正在为你的答案添加强化:

#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)来正确舍入高阶结果.

Answer 2

这没有任何意义,因为你要做的事情不会优化最终的过程!

嘿,我没有在你的问题中随处阅读你有意优化的内容.

无论"有用性"如何,电气工程人员永远不会感到好奇.我们就像你在新闻中读到的强迫性强迫性囤积者,他们将阁楼,酒窖,卧室和起居室堆放起来,他们相信这些垃圾有时会派上用场.至少在我不到30年前在英格兰学校就读的情况就是如此.我鼓励你继续寻求囤积"无用"的知识,这些知识几乎没有优化你的生活或生活方式的可能性.为什么依靠编译器,你可以通过手工编码算法来做到这一点？!呀？你知道,有点冒险吗？Ok enuf表达了对你追求知识表示不屑的人.

回想一下你的中学,你被教导做分工的方式？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.

我希望我上面的二进制操作不会有错误或拼写错误.如果是这样,千万道歉.

Answer 3

假设你有表达式a = b / c.正如hroptatyr所提到的,乘法非常快(并且它比分裂快得多).因此,基本思想是将分裂转换为乘法,如:a = b * (1/c).

现在,我们仍然需要划分计算收件人1/c,所以这只有在c知道apriori的情况下才有用.虽然浮点运算是不够的,对于intereges我们必须使用一个技巧:我们可以使用的值的倒数c的值some_big_number / c,从而最终我们将计算a2 = b * (some_big_number / c),等于some_big_number * b/c.因为我们对价值感兴趣b/c,所以我们必须将最终结果除以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向零舍入).

Answer 4

如果你对它背后的数学感兴趣,请阅读Henry S. Warren的Hacker's Delight.

如果您对优化代码感兴趣,只需编写人类最容易阅读的内容.例如:

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

使用时编译此函数时g++ -O2,它不会进行实际除法,而是进行一些魔术乘法,位移和校正.

Answer 5

一般来说：

• 获得数字的质因数分解，您将 N 分解为 2^k * 其余，然后您可以对两次幂使用位移。示例：20 = 2^2 * 5，因此要乘以 20，您需要乘以 5，然后使用位移位<< 2
• 要在非二次幂上使用位移位，请观察奇数的以下情况l：a * l = a * (l - 1) + a现在l - 1是偶数，因此分解为二次幂，位移位“技巧”适用于此。

除法可以类似地构建。