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

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

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

据我所知,在一些机器上,乘法运算可能需要16到32个机器周期。是的,根据机器类型,位移运算符比乘除运算符快。

然而,某些机器确实有它们的数学处理器,其中包含乘法/除法的特殊指令。

In the case of signed integers and right shift vs division, it can make a difference. For negative numbers, the shift rounds rounds towards negative infinity whereas division rounds towards zero. Of course the compiler will change the division to something cheaper, but it will usually change it to something that has the same rounding behavior as division, because it is either unable to prove that the variable won't be negative or it simply doesn't care. So if you can prove that a number won't be negative or if you don't care which way it will round, you can do that optimization in a way that is more likely to make a difference.

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

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

只是一个具体的衡量点:许多年前,我对两个进行了基准测试 我的哈希算法的版本:

unsigned
hash( char const* s )
{
    unsigned h = 0;
    while ( *s != '\0' ) {
        h = 127 * h + (unsigned char)*s;
        ++ s;
    }
    return h;
}

and

unsigned
hash( char const* s )
{
    unsigned h = 0;
    while ( *s != '\0' ) {
        h = (h << 7) - h + (unsigned char)*s;
        ++ s;
    }
    return h;
}

在我对它进行基准测试的每台机器上,第一台机器的速度至少和 第二。有些令人惊讶的是,它有时更快(例如在一个 Sun Sparc)。当硬件不支持快速乘法(和 大多数当时没有),编译器将转换乘法 转换成移位和加/减的适当组合。因为它 知道了最终的目标,它有时可以在少于指令的情况下这样做 当你明确地写出移位和加法/减法时。

请注意,这是15年前的事了。希望编译器 从那以后就越来越好了,所以你可以指望 编译器做正确的事情,可能比你做的更好。(另外, 这段代码看起来如此C'ish的原因是因为它是15年前的事情了。 显然,我今天会使用std::string和迭代器。)