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

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非常不同!

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

其他回答

移位通常比指令级的乘法快得多,但你可能会浪费时间做过早的优化。编译器可以在编译时很好地执行这些优化。自己做会影响可读性,而且可能对性能没有影响。如果您已经进行了概要分析并发现这是一个瓶颈,那么这样做可能是值得的。

实际上,这种被称为“魔法除法”的除法技巧实际上可以产生巨大的收益。同样,你应该首先分析它是否需要。但是如果你真的使用它,周围有一些有用的程序可以帮助你弄清楚相同的除法语义需要什么指令。这里有一个例子:http://www.masm32.com/board/index.php?topic=12421.0

我从MASM32上的OP线程中引用了一个例子:

include ConstDiv.inc
...
mov eax,9999999
; divide eax by 100000
cdiv 100000
; edx = quotient

会产生:

mov eax,9999999
mov edx,0A7C5AC47h
add eax,1
.if !CARRY?
    mul edx
.endif
shr edx,16

不要这样做,除非你绝对需要这样做,并且你的代码意图是移位而不是乘法/除法。

在典型的日子里,你可能会节省一些机器周期(或松弛,因为编译器更知道优化什么),但成本并不值得——你把时间花在小细节上而不是实际的工作上,维护代码变得更加困难,你的同事会诅咒你。

对于高负载计算,您可能需要这样做,其中每个节省的周期意味着几分钟的运行时。但是,您应该一次优化一个地方,并每次都进行性能测试,看看您是否真的使它更快了,还是破坏了编译器逻辑。

刚刚在我的机器上编译了这个:

int a = ...;
int b = a * 10;

当分解它时会产生输出:

MOV EAX,DWORD PTR SS:[ESP+1C] ; Move a into EAX
LEA EAX,DWORD PTR DS:[EAX+EAX*4] ; Multiply by 5 without shift !
SHL EAX, 1 ; Multiply by 2 using shift

这个版本比纯移位和加法的手工优化代码更快。

你永远不知道编译器会得到什么,所以最好只是简单地写一个普通的乘法,让它按自己想要的方式优化,除非在非常精确的情况下,你知道编译器无法优化。

如果在gcc编译器上比较x+x, x*2和x<<1语法的输出,那么在x86汇编中会得到相同的结果:https://godbolt.org/z/JLpp0j

        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], edi
        mov     eax, DWORD PTR [rbp-4]
        add     eax, eax
        pop     rbp
        ret

因此,您可以认为gcc足够聪明,可以独立于您输入的内容确定自己的最佳解决方案。

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中这样做)而改变。

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