Difference in x/2 and x>>1 or x*2 and x << 1 where x is an integer

bit-manipulation, c++, integer-division, multiplication

Solution

This question has been answered on the ridiculousfishblog : http://ridiculousfish.com/blog/posts/will-it-optimize.html

- 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.

Good programers let compilers optimize their code, unless they hit a performance penalty.

EDIT : Since you ask for official sources, let's quote the standard rationale document for C99. You find it here : 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.

Your optimization would have been correct in C89, since it let to the compiler to do as it wants. However, C99 introduce a new convention to comply with Fortran code. Here is an example of what is expected of the divide operator (always from the same document) :

Unfortunately your optimization does not comply with the C99 standard, since it does not give the right result for 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]

If you look at the compiled code, you can spot an interesting difference (compiled with 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  

line `401392`, there is a `test` instruction, which will check the parity bit and, if the number is negative, will add `1 << (n-1) = 7` to x before right-shifting by 3 units.

Problem

Original source