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

我们知道,要计算整数x/2,我们只需为x*2编写类似的y=x/2;;但优秀的程序员使用位操作来计算这一点。

他们只是y = x >> 1;

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

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


解决方案

这个问题已经在荒唐的鱼儿博客上得到了回答:http://ridiculousfish.com/blog/posts/will-it-optimize.html

  1. 除以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代码。下面的示例说明了Divide运算符的用途(始终来自同一文档):

遗憾的是,您的优化不符合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 
", div8(x) );
    printf("rs : %d 
", 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指令,它将检查奇偶校验位,如果数字为负数,则在右移3个单位之前将1 << (n-1) = 7与x相加。

相关文章