我了解如何以 2 的幂来执行此操作，所以这不是我的问题。
例如，如果我想使用位移而不是整数除法来查找数字的 5%，我将如何计算呢？
所以我可以用 (x * 100 >> 11) 代替 (x * 20 / 19)。现在这是不对的，但它已经接近了，我通过反复试验得出了它。我将如何确定最可能使用的精确班次？
问问题
20739 次
7 回答
22
最好的方法是让编译器为你做这件事。你只需写
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）来正确舍入高阶结果。
于 2010-10-03T17:11:24.643 回答
8
这是没有意义的，因为您尝试做的事情并没有优化结果过程！！！
嘿，我没有在您的问题中看到您打算优化的任何地方。
无论“有用”如何，Electrical Engg 人都不会停止好奇。我们就像那些你在新闻中读到的东西的强迫症囤积者，他们把阁楼、地窖、卧室和客厅里堆满了他们认为有一天会派上用场的垃圾。至少在不到 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。
我希望我上面的二进制操作不会有错误或拼写错误。如果是这样，成千上万的道歉。
于 2010-10-03T21:08:40.983 回答
7
假设你有表达式a = b / c。正如 hroptatyr 所提到的，乘法非常快（而且比除法快得多）。所以基本思想是将除法转换为乘法，例如：a = b * (1/c)。
现在，我们仍然需要除法来计算倒数1/c，所以这只有在c先验已知的情况下才有效。虽然对于浮点计算就足够了，但对于 intereges，我们必须使用另一个技巧：我们可以使用 value 的值的倒数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为了舍入到零）。
于 2010-10-03T19:39:33.220 回答
6
如果您对其背后的数学感兴趣，请阅读Henry S. Warren的 Hacker's Delight。
如果您对优化代码感兴趣，只需编写人类最容易阅读的内容。例如：
int five_percent(int x) {
return x / 20;
}
当您使用 编译此函数时g++ -O2，它不会进行实际除法，而是进行一些魔术乘法、位移和校正。
于 2010-10-03T22:09:48.580 回答
3
你不能用轮班来做所有事情，你需要使用“魔法”除数（见黑客的喜悦）。魔术除法的工作原理是将一个数字乘以另一个适当大的数字，然后将其翻转以产生除法的答案（mul/imul 比 div/idiv 快）。魔术常数仅对每个素数唯一，倍数需要移位，例如：无符号除以 3 可以表示（在 32 位上）x * 0xAAAAAAAB，除以 6 将(x * 0xAAAAAAAB) >> 1除以 12 将移位 2、24 除以 3 等（其几何级数3 * (2 ^ x)，其中 0 <= x < 32)
于 2010-10-03T20:22:38.050 回答
2
假设您想通过乘以 y 并移动 n 来近似 x 的 5%。由于 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 解决这个问题。
于 2010-10-03T19:28:16.733 回答
0
一般情况下：
- 获得数字的素数分解，您将 N 分解为 2^k * rest，然后您可以对两个幂使用位移。示例：20 = 2^2 * 5，所以要乘以 20，您需要乘以 5，然后使用位移
<< 2 - 要对非二次幂使用位移，请注意以下奇数
l：a * l = a * (l - 1) + a，现在l - 1是偶数，因此分解为二次幂，位移“技巧”适用于此。
可以类似地构造除法。
于 2010-10-03T17:05:50.773 回答