在C中使用移位运算符的乘法和除法实际上更快吗？

Question

例如，可以使用位运算符来实现乘法和除法i*2 = i<<1i*3 = (i<<1) + i;i*10 = (i<<3) + (i<<1)等等。使用说(i<<3)+(i<<1)乘以10 真的比i*10直接使用要快吗？是否存在无法以这种方式相乘或除法的输入？

Answer 1

简短答案：不太可能。

长答案：您的编译器中包含一个优化器，该优化器知道如何以目标处理器体系结构所能达到的速度快速进行乘法。最好的选择是清楚地告诉编译器您的意图（即i * 2而不是i << 1），然后让它决定最快的汇编/机器码序列。处理器本身甚至可能已将乘法指令实现为一系列移位和微码加法运算。

最重要的是-不要花很多时间担心这个问题。如果您要转移，那就转移。如果要乘，就乘。做语义上最清晰的事情-您的同事以后会感谢您。或者，更可能的是，如果以后否则诅咒您。

Answer 2

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

unsigned

hash( char const* s )

{

    unsigned h = 0;

    while ( *s != '\0' ) {

        h = 127 * h + (unsigned char)*s;

        ++ s;

    }

    return h;

}

和

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”的原因是因为它已经超过15年了。std::string今天，我显然会使用和迭代器。）

Answer 3

除了这里所有其他好的答案之外，让我指出在表示除法或乘法时不使用移位的另一个原因。我从未见过有人通过忘记乘法和加法的相对优先级来引入错误。当维护程序员忘记通过移位进行“乘法”在逻辑上是乘法，但在语法上却没有与乘法相同的优先级时，我已经看到了引入的错误。x * 2 + z而且x << 1 + z有很大的不同！

如果您正在处理数字，请使用算术运算符，例如+ - * / %。如果您正在处理位数组，请使用位旋转运算符，例如& ^ | >>。不要混在一起；一个既有点摇摆又有算术的表达式是一个等待发生的错误。