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

Question 1

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) :

enter image description here

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.

Question 2

You should code what you mean, and optimize when you need to do it.

As far as I know, the difference is for signed numbers, where the behavior is undefined. This is likely historical due to the fact that other signbit mechanisms existed than 2's compliment, but in effect that means compilers can use instructions that may not behave how you expect when optimizing.

Question 3

It depends.

In general, bit manipulation is faster than arithmetic, especially multiplication and division. However, many—if not most—optimizing compilers will do the right thing for speed so it does not matter which is written.

The 1978 Pascal compiler for the CDC Cyber generated code to shift and add for multiplies which involved a constant with 1 or 2 bits. For example:

 x := somevar * 10;    /* 10 has two bits set */

would generate code equivalent to

 x := (somevar << 1) + (somevar << 3);   /*  *2 + *8 */

This was substantially faster on a Cyber than using the integer multiply instruction.

Question 4

As per nos, good programmers do not shift instead of multiplying and dividing: even when it does the same thing, it's no faster and more arcane.

Also it doesn't always do the same thing.

Whether shift right is arithmetic or logical depends on your CPU architecture: C allows either. So -23 >> 1 is permitted to give a positive result.

Question 5

x/2 is not equal to x >> 1 for negative numbers. Anyway, practically every compiler will replace multiplication or division by the power of two to bit manipulation automatically if it is possible.

Question 6

The entire premise of this question smells of a premature micro-optimization.

When you are writing code, you write it to be clear. If you are multiplying by a number, show the operation as multiplication.

The exception comes when/if a performance barrier is hit and it is determined (through profiling) that your code needs to be adjusted to an "uglier" version (e.g. using bitshifts instead of multiplication and division). Unless you have run into such a performance issue (not likely), there is no reason to use bitshifts when you mean to use multiplication (or division).

Question 7

The evaluation of expressions depends on the processor architecture, platform architecture and the compiler.

In theory, x >> 1 is the same as x / 2, for all unsigned integers.
If the compiler is smart enough or the optimizations are set correctly, the compiler should generate the same executable code for each, provided your process has shift operations.

Also, x << 1 and x * 2 should be the same for all unsigned integers.

Some compilers may not recognize the same and actually perform multiplication for x * 2 and division for x / 2.

The truth will be in the assembly language generated by your compiler.

The bigger issue is in readability. Most people are familiar with multiplication as it is taught early in schools. Binary shifting is not common to most people. I still get questioned by programmers about the shift operations. When in doubt, choose readability over performance.

Question 8

CPU get a logic circuit to multiply numbers, in intel x86 it is MUL instruction. Good programmer do code like this and wrap the whole thing decently.

But you surely missing the logic for checking overflow by assuming x<1 = x*2, and it works only on unsigned integer. You cannot divide and multiply a negative number by x>1 or x<1, because the rightmost bit is the bit for +/-.

Question 9

Let me demonstrate on an example:

int f(int n){
  if(n<=0) return 33;
  if((n*2)<=0) return 42;
  return 0;
}
int g(int n){
  if(n<=0) return 33;
  if((n<<1)<=0) return 42;
  return 0;
}

You might assume that both functions do the same thing. However, let us look at the generated asm for f:

testl   %edi, %edi
movl    $0, %edx
movl    $33, %eax
cmovg   %edx, %eax
ret

and g:

testl   %edi, %edi
movl    $33, %eax
jle .L5
addl    %edi, %edi
movl    $0, %edx
movb    $42, %al
testl   %edi, %edi
cmovg   %edx, %eax
.L5:
rep ret

As you notice, the compiler was able to remove the second comparison for f but not for g. The reason is that signed multiplication may not overflow while bit operations may. Trying to be clever made your code slower. By the way, note that the compiler found it clever to replace n<<1 with n+n...

Question 10

For x86 architectures, considering compilers like gcc or VS the difference is not that obvious; actually some programmers would consider using >> or << instead of / or * a form of obfuscation.

The difference becomes apparent for embedded systems where you have different architectures and compilers. It all comes down to what instructions are available on a particular architecture and how smart the compiler is.

Let me elaborate: what are the things you need to consider for any operation a op b ? well the very minimum you should consider the data type of the operands and of the result. Why is that important? Because integer numbers are represented differently than decimal numbers and of course there is the matter of overflow ( 16bit * 16 bit = 32 bit usually). Let's take multiplication: on some architectures you have instructions for multiplications for several operands like:

  16 bit * 16 bit = 32 bit
  16 bit * 16 bit = 16 bit
  16 bit * 32 bit = 32 bit
  ....

Depending on how you write your code and how smart the compiler is the generated code will consist of a certain number of instructions (the smaller this number, the faster the code executes).

So far the same is true for both *,/ and >>,<<.

Multiplication is usually supported in the hardware and you have one instruction to get the result (unless you are dealing with data types which the architecture does not support natively and the instruction has to be emulated - but that is more complicated). Division however is more expensive and is usually emulated: successive subtractions in a repetitive loop. Thus a lot more instructions to get the result.

Some compilers are smart enough and analyze the code, generating shift operations for division/ multiplication with an immediate value power of two; but writing code like a=2; c= b*a; can put even the smartest compiler in a difficult position.

Shift on the other hand is more straight forward: you are guaranteed to have the instruction supported and usually the result is the same size as the operand ( 16bi >> 1 = 16bit).

Considering all of that, you are usually helping the compile generate better, faster code when you use shift operations instead of multiplication/division