x/2和x >> 1或x*2和x << 1的差值,其中x是整数

Question

正如我们所知的计算整数x/2,我们只是y=x/2;为x*2 编写类似的东西; 但优秀的程序员使用位操作来计算它.

他们只是这样做 y = x >> 1;

这两种方法有什么区别吗？差异,我的意思是所需的时间/空间/内存的差异或两者完全相同(即x/2由x >> 1实现)？

也是乘法/除法与其他数字而不是2实现相同的方式(即5*5 = 10*2 + 5*1 = 10 << 1 + 5 = 25)？

Answer 1

这个问题已在ridiculousfishblog上得到解答:http://ridiculousfish.com/blog/posts/will-it-optimize.html

5. 分2到右移

GCC会将整数除以2变换为右移吗？

int halve_it(int x) {
   return x / 2;
}

int halve_it(int x) {
   return x >> 1;
}

右移运算符相当于向负无穷大舍入的除法,但正常除法向零舍入.因此,所提出的优化将对奇数负数产生错误的结果.

通过在移位之前将最高有效位添加到分子,可以"固定"结果,并且gcc执行此操作.

优秀的程序员让编译器优化他们的代码,除非他们遇到性能损失.

编辑:既然你要求官方消息来源,让我们引用C99的标准理由文件.你可以在这里找到它:http://www.open-std.org/jtc1/sc22/wg14/www/docs/C99RationaleV5.10.pdf

在C89中,涉及负操作数的整数划分可以以实现定义的方式向上或向下舍入; 目的是避免在运行时代码中产生开销以检查特殊情况并强制执行特定行为.但是,在Fortran中,结果将始终截断为零,并且数字编程社区似乎可以接受开销.因此,C99现在需要类似的行为,这应该有助于将代码从Fortran移植到C.本文档的第7.20.6.2节中的表说明了所需的语义.

你的优化在C89中是正确的,因为它让编译器按照自己的意愿去做.但是,C99引入了一个符合Fortran代码的新约定.以下是除法运算符的预期示例(始终来自同一文档):

不幸的是,您的优化不符合C99标准,因为它没有给出x = -1的正确结果:

#include <stdio.h>

int div8(int x)
{
    return x/3;
}

int rs8( int x )
{
    return x >> 3;
}

int main(int argc, char *argv[])
{
    volatile int x = -1;
    printf("div : %d \n", div8(x) );
    printf("rs : %d \n", rs8(x) );

    return 0;
}

Result:
div : 0 
rs : -1 
[Finished in 0.2s]

如果查看已编译的代码,可以发现一个有趣的区别(使用g ++ v4.6.2编译):

0040138c <__Z4div8i>:
  40138c:   55                      push   %ebp
  40138d:   89 e5                   mov    %esp,%ebp
  40138f:   8b 45 08                mov    0x8(%ebp),%eax
  401392:   85 c0                   test   %eax,%eax
  401394:   79 03                   jns    401399 <__Z4div8i+0xd>
  401396:   83 c0 0f                add    $0x7,%eax
  401399:   c1 f8 04                sar    $0x3,%eax
  40139c:   5d                      pop    %ebp
  40139d:   c3                      ret    

0040139e <__Z3rs8i>:
  40139e:   55                      push   %ebp
  40139f:   89 e5                   mov    %esp,%ebp
  4013a1:   8b 45 08                mov    0x8(%ebp),%eax
  4013a4:   c1 f8 03                sar    $0x3,%eax
  4013a7:   5d                      pop    %ebp
  4013a8:   c3                      ret  

行401392,有一条test指令,它将检查奇偶校验位,如果数字为负,则1 << (n-1) = 7在右移3个单位之前将加到x.

Answer 2

您应该编写您的意思,并在需要时进行优化.

据我所知,不同之处在于有符号数,行为未定义.这可能是历史性的,因为存在其他标志位机制而不是2的赞美,但实际上这意味着编译器可以使用在优化时可能无法按预期运行的指令.