例如,乘法和除法可以使用位运算符来实现

i*2 = i<<1
i*3 = (i<<1) + i;
i*10 = (i<<3) + (i<<1)

等等。

用say (i<<3)+(i<<1)乘10是否比直接用i*10更快?有没有什么输入是不能用这种方法乘或除的?


当前回答

除了所有其他好的答案,让我指出当你指除法或乘法时不使用shift的另一个原因。我从未见过有人因为忘记乘法和加法的相对优先级而导致错误。我曾经见过,当维护程序员忘记了通过移位的“乘法”在逻辑上是乘法,但在语法上与乘法的优先级不同时,就会引入错误。X * 2 + z和X << 1 + z非常不同!

如果你处理的是数字,那就使用算术运算符,比如+ - * / %。如果您正在处理比特数组,请使用& ^ | >>这样的比特旋转操作符。不要把它们混在一起;一个表达式如果同时具有位旋转和算术,那么这个表达式就是一个等待发生的错误。

其他回答

Python测试对相同的随机数执行相同的乘法1亿次。

>>> from timeit import timeit
>>> setup_str = 'import scipy; from scipy import random; scipy.random.seed(0)'
>>> N = 10*1000*1000
>>> timeit('x=random.randint(65536);', setup=setup_str, number=N)
1.894096851348877 # Time from generating the random #s and no opperati

>>> timeit('x=random.randint(65536); x*2', setup=setup_str, number=N)
2.2799630165100098
>>> timeit('x=random.randint(65536); x << 1', setup=setup_str, number=N)
2.2616429328918457

>>> timeit('x=random.randint(65536); x*10', setup=setup_str, number=N)
2.2799630165100098
>>> timeit('x=random.randint(65536); (x << 3) + (x<<1)', setup=setup_str, number=N)
2.9485139846801758

>>> timeit('x=random.randint(65536); x // 2', setup=setup_str, number=N)
2.490908145904541
>>> timeit('x=random.randint(65536); x / 2', setup=setup_str, number=N)
2.4757170677185059
>>> timeit('x=random.randint(65536); x >> 1', setup=setup_str, number=N)
2.2316000461578369

因此,在python中做移位而不是用2的幂来做乘法/除法,会有轻微的改进(~10%用于除法;~1%的乘法)。如果它不是2的幂,可能会有相当大的放缓。

同样,这些#将根据你的处理器、编译器(或解释器——为了简单起见,在python中这样做)而改变。

和其他人一样,不要过早地优化。编写可读性非常强的代码,如果不够快就进行分析,然后尝试优化慢的部分。请记住,编译器在优化方面比您做得更好。

这取决于处理器和编译器。一些编译器已经通过这种方式优化代码了,其他的还没有。 因此,每次需要以这种方式优化代码时,您都需要检查。

除非您迫切需要优化,否则我不会为了节省汇编指令或处理器周期而打乱源代码。

Shift和整数乘法指令在大多数现代cpu上具有相似的性能——在20世纪80年代,整数乘法指令相对较慢,但通常情况下不再是这样。整数乘法指令可能有更高的延迟,所以仍然可能有移位更可取的情况。同样的情况下,你可以让更多的执行单元忙(尽管这是有利有弊)。

整数除法仍然相对较慢,所以使用shift代替2的幂除法仍然是一种胜利,大多数编译器将其作为一种优化来实现。但是请注意,要使这种优化有效,红利需要是无符号的,或者必须已知是正的。对于负红利,移位和除法是不相等的!

#include <stdio.h>

int main(void)
{
    int i;

    for (i = 5; i >= -5; --i)
    {
        printf("%d / 2 = %d, %d >> 1 = %d\n", i, i / 2, i, i >> 1);
    }
    return 0;
}

输出:

5 / 2 = 2, 5 >> 1 = 2
4 / 2 = 2, 4 >> 1 = 2
3 / 2 = 1, 3 >> 1 = 1
2 / 2 = 1, 2 >> 1 = 1
1 / 2 = 0, 1 >> 1 = 0
0 / 2 = 0, 0 >> 1 = 0
-1 / 2 = 0, -1 >> 1 = -1
-2 / 2 = -1, -2 >> 1 = -1
-3 / 2 = -1, -3 >> 1 = -2
-4 / 2 = -2, -4 >> 1 = -2
-5 / 2 = -2, -5 >> 1 = -3

所以如果你想帮助编译器,那么确保变量或表达式在被除数显式无符号。

我同意德鲁·霍尔的明确回答。不过,答案可能需要一些额外的注释。

对于绝大多数软件开发人员来说,处理器和编译器已经不再与问题相关。我们大多数人远远超出了8088和MS-DOS。它可能只与那些仍在开发嵌入式处理器的人有关……

在我的软件公司,Math (add/sub/mul/div)应该用于所有数学。 当数据类型之间转换时应该使用Shift。字节长度为n>>8,而不是n/256。

这完全取决于目标设备、语言、目的等。

像素压缩显卡驱动程序?很有可能,是的!

.NET业务应用程序为您的部门?根本没必要去调查。

对于一款面向移动设备的高性能游戏来说,这可能是值得一试的,但前提是要进行更简单的优化。