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

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

等等。

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


当前回答

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

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

其他回答

简单回答:不太可能。

长一点的回答: 你的编译器有一个优化器,它知道如何像你的目标处理器体系结构一样快速地进行乘法运算。最好的办法是清楚地告诉编译器你的意图(即i*2而不是i << 1),让它决定最快的汇编/机器码序列是什么。甚至有可能处理器本身已经将乘法指令实现为微码中的移位和加法序列。

总之,不要花太多时间担心这个。如果你想换,那就换。如果你想乘,那就乘。做语义上最清楚的事情——你的同事以后会感谢你的。或者,更有可能的是,如果你不这样做,之后会诅咒你。

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

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

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

实际上,这种被称为“魔法除法”的除法技巧实际上可以产生巨大的收益。同样,你应该首先分析它是否需要。但是如果你真的使用它,周围有一些有用的程序可以帮助你弄清楚相同的除法语义需要什么指令。这里有一个例子: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

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

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

如果在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足够聪明,可以独立于您输入的内容确定自己的最佳解决方案。