当前位置：文江博客话题详情

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

发布于 2024-09-26 06:11:51 字数 174 浏览 3 评论 0原文

我知道如何计算 2 的幂，所以这不是我的问题。

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

所以我可以用 (x * 100 >> 11) 代替 (x * 20 / 19)。现在这是不对的，但已经很接近了，我通过反复试验得出了它。我如何确定最可能使用的精确移位？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

过期情话 2024-10-03 06:11:51

最好的方法是让编译器为你做这件事。您只需用您选择的语言编写

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

EDIT 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）来正确舍入高位结果。

Best approach is to let the compiler do it for you. You simply write

a/b

in your language of choice, and the compiler generates the bit twiddling.

EDIT (I hope you don't mind, i'm adding reinforcement to your answer:

#include <stdio.h>

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

Obviously, the fastest thing to do is argc>>2. Lets see what happens:

        .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

yup, there it is, sarl $2, %eax

EDIT 2 (Sorry to pile on, but 20/19 is a bit more complicated…)

I just substituted argc*20/19 for argc/4 and this is the math that comes out:

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

So, the process is

Multiply input by 4 (shll)
Load (movl 0x...) and multiply by (imull) a fixed-point fraction obtaining a 64-bit result (this is 32-bit code)
Divide high-order 32 bits of result by 8 (sarl), note how this handles negative numbers
Divide low-order 32 bits of result by INT_MAX (sarl) to obtain either 0 or -1
Correctly round the high-order result by adding 1 (subtracting -1) if necessary.

回复收藏 0 原文

还给你自由 2024-10-03 06:11:51

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

嘿，我没有在你的问题中读到你打算优化的任何地方。

无论“有用”如何，电气工程人永远不会停止好奇。我们就像你在新闻中读到的那些物品的强迫性囤积者，他们在阁楼、地窖、卧室和客厅里堆放着垃圾，他们相信有一天会派上用场。至少不到 30 年前我在 Engg 学校时是这样。我鼓励你继续寻求积累“无用”的知识，这些知识似乎对优化你的生活或生活方式几乎没有可能。当你可以通过手工编码的算法来完成它时，为什么还要依赖编译器呢？！啊？有点冒险精神，你知道。好吧，讨厌那些对你追求知识表示蔑视的人。

还记得在中学时，你是如何学习除法的吗？ 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。

我希望上面的二进制操作不会出现错误或拼写错误。如果是这样，成千上万的道歉。

It makes no sense because what you are trying to do does not optimise the resulting process!!!

Hey, I did not read anywhere in your question that you had intention to optimise.

Electrical Engg people never stop being curious regardless of "usefulness". We are like compulsive obsessive hoarders of items of whom you read in the news where they stack their attics, cellars, bedrooms and living rooms up with junk which they believe would come in handy one day. At least that was the case when I was in Engg school a little less than 30 years ago. I encourage you to continue in your quest to hoard up "useless" knowledge that appears to have little possibilities of optimising your life or life-style. Why depend on the compiler when you can do it by hand-coded algorithm?! Yah? Be a little adventurous, you know. Ok enuf dissing people who express disdain at your pursuit of knowledge.

Recall in your middle-school, the way you were taught to do your division? 437/24, e.g.

  _____
24|437


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

The number which is subject to division, 437, is called the dividend. 24 is the divisor, the result 18 is the quotient, and 5 is the remainder. Like when you file your taxes, you need to fill in profits you had gained from stock "dividends", which is a misnomer. What you fill into the tax form is a multiple of the quotient of a single huge chunk of dividend. You did not receive the dividend, but portions of dividend - otherwise, it would mean you owned 100% of the stock.

     ___________
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.

The above, as you might already know, is TRUE division. Which is achieved by subtracting by a shifted divisor.

What you want is to achieve the same thing by simply shifting the dividend. That, unfortunately cannot be done unless the divisor is a exponential power of 2 (2,4,8,16). Which is an obvious fact of binary arithmetic. Or, at least I am not aware of any method that can do it without approximation and intrapolative techniques.

Therefore, you have to use a combination of dividend shift and true division.
e.g.

24 = 2 x 2 x 2 x 3

First, divide 437 by 8 using binary shift to get 010010 and then use true division to divide by 3:

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

which works out to 010010 = 18.

Voila.

How do you determine 24 = 2^8 x 3?

By shifting 11000 rightwards until you hit a 1.

Which means, you could shift the dividend the same number of times as you would shift the divisor until the divisor hits a 1.

Therefore, obviously, this method would not work if a divisor is odd.
e.g., it will not work for divisor 25, but it will work a little for divisor 50.

May be, there are predictive methods that could interpolate a divisor like 13 to be between 2^3=8 and 2^4=16. If there are, I am not familiar with them.

What you need to explore is using a number series. For example dividing by 25:

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

where the general form of the series is

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

where bn is either -1, 0 or +1.

I hoping my binary manipulation above would not have errors or typos. If so, thousands apologies.

回复收藏 0 原文

掩饰不了的爱 2024-10-03 06:11:51

假设您有表达式a = b / c。正如 hroptatyr 提到的，乘法相当快（而且比除法快得多）。因此基本思想是将除法转换为乘法，例如：a = b * (1/c)。

现在，我们仍然需要除法来计算倒数 1/c，因此只有在先验已知 c 的情况下这才有效。虽然对于浮点计算来说已经足够了，但是对于整数，我们必须使用另一个技巧：我们可以使用 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 用于向零舍入）。

Suppose you have the expression a = b / c. As hroptatyr mentioned, the multiplication is quite fast (and it's much faster than division). So the basic idea is to transform the division into multiplication like : a = b * (1/c).

Now, we still need division for computation of reciprical 1/c, so this would work only if c is known apriori. While for floating point computation it's enough, for intereges we have to use another trick: we can use for reciprocal of the value of c the value some_big_number / c, so that finally we'll compute a2 = b * (some_big_number / c), that is equal to some_big_number * b/c. Because we're interested in value of b/c, we have to divide the final result by some_big_number. If it's choosed to be a power of 2, then the final division would be fast.

ex:

// 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;
}

EDIT: a good part of this method is that you can choose any rounding method for the divison by choosing the correction (in this case it was 20 - 1 for rounding towards zero).

回复收藏 0 原文

逆流 2024-10-03 06:11:51

如果您对其背后的数学感兴趣，请阅读 Henry S. Warren 所著的黑客之乐。

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

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

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

If you are interested in the math behind it, read Hacker's Delight by Henry S. Warren.

If you are interested in optimized code, just write what is most easy to read by humans. For example:

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

When you compile this function using g++ -O2, it will not do an actual division but some magic multiplication, bit-shifting and correction instead.

回复收藏 0 原文

扛刀软妹 2024-10-03 06:11:51

你不能用轮班来做所有事情，你需要使用“神奇”除数（看看黑客的喜悦）。魔法除法的工作原理是将一个数字乘以另一个适当大的数字，然后将其滚动以得出除法的答案（mul/imul 比 div/idiv 更快）。魔法常量仅对每个质数是唯一的，倍数需要移位，例如：无符号除以 3 可以表示为（在 32 位上）x * 0xAAAAAAAB，除以 6 将表示为 ( x * 0xAAAAAAAB) >>> 1 除以 12 将移位 2、24 除以 3 等（其几何级数 3 * (2 ^ x)，其中 0 <= x < 32）

回复收藏 0 原文

不羁少年 2024-10-03 06:11:51

假设您想通过乘以 y 并移位 n 来近似 x 的 5%。由于 5% 是 1/20，并且 a>>n = a/2ⁿ，因此您需要求解

x/20 ≈ x*y/2ⁿ （符号“≈”表示“大约等于”）

，可简化为

y ≈ 2ⁿ/20

因此，如果 n=11，则

y ≈ 2ⁿ/20 = 2048/20 =102 + 8/20

所以我们可以设置 y=102，这实际上比你通过反复试验找到的 100 更好。

一般来说，我们可以玩一下n，看看能否得到更好的答案。

我已经针对分数 1/20 计算出了这个结果，但是您应该能够通过遵循相同的方法针对任何分数 p/q 计算出这个结果。

回复收藏 0 原文

小糖芽 2024-10-03 06:11:51

一般而言：

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

除法可以类似地构建。

回复收藏 0 原文

~没有更多了~