c++ - 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

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

5. Division by 2 to right shift

Will GCC transform an integer division by 2 to a right shift?

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

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

The right shift operator is equivalent to division that rounds towards negative infinity, but normal division rounds towards zero. Thus the proposed optimization will produce the wrong result for odd negative numbers.

The result can be "fixed up" by adding the most significant bit to the numerator before shifting, and gcc does this.

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

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

In C89, division of integers involving negative operands could round upward or downward in an implementation-defined manner; the intent was to avoid incurring overhead in run-time code to check for special cases and enforce specific behavior. In Fortran, however, the result will always truncate toward zero, and the overhead seems to be acceptable to the numeric programming community. Therefore, C99 now requires similar behavior, which should facilitate porting of code from Fortran to C. The table in §7.20.6.2 of this document illustrates the required semantics.

您的优化在 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。