在C语言中使用移位运算符的乘法和除法真的更快吗?

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

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

等等。

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

当前回答

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

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和迭代器。)

2011-06-15 12:35:57

其他回答

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.

2011-06-15 16:29:18

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

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

2011-06-15 11:35:53

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

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

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

2011-06-15 13:48:49

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

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

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

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