Why does division and multiplication by 2 use the shift operator rather than division operator?

Question

While looking at the code in C for division/multiplication by 2, it is found that shift operator is used rather than division operator. What is the advantage of using shift over division operator?

Answer 1

Multiplication is complex typically... unless one of the multiplicands is the base the numbers are in themselves.

When working with base 10 math, multiplying by 10 is trivial: "append the same number of zeros as the 10 has". 2 * 10 = 20 and 3 * 100 = 300

This is very easy for us. The exact same rule exists in binary.

In binary, 2 * 3 = 6 is 10 * 11 = 110, and 4 * 3 = 12 is 100 * 11 = 1100.

For a system already working with bits (ANDs and ORs), operations such as shift and roll already exist as part of the standard tool set. It just happens that translating N * 2^M into binary becomes shift N by M places

If we are doing something that isn't a power of 2 in binary, we've got to go back to the old fashioned multiply and add. Granted, binary is a bit 'easier', but a bit more tedious at the same time.

11 * 14 becomes (from Wikipedia on binary multiplier - a good read as it links to other multiplication algorithms for binary... shifting powers of two is still much easier):

       1011   (this is 11 in decimal)
     x 1110   (this is 14 in decimal)
     ======
       0000   (this is 1011 x 0)
      1011    (this is 1011 x 1, shifted one position to the left)
     1011     (this is 1011 x 1, shifted two positions to the left)
  + 1011      (this is 1011 x 1, shifted three positions to the left)
  =========
   10011010   (this is 154 in decimal)

You can see, we're still doing shifts, and adds. But lets change that to 11 * 8 to see how easy it becomes and why we can just skip to the answer:

       1011   (this is 11 in decimal)
     x 1000   (this is  8 in decimal)
     ======
       0000   (this is 1011 x 0)
      0000    (this is 1011 x 0, shifted one position to the left)
     0000     (this is 1011 x 0, shifted two positions to the left)
  + 1011      (this is 1011 x 1, shifted three positions to the left)
  =========
   1011000   (this is 88 in decimal)

By just skipping to that last step, we have drastically simplified the entire problem without adding lots of 0s that are still 0s.

---

Dividing is the same thing as multiplying, just the reverse. Just as 400 / 100 can be summarized as 'cancel the zeros', so too can this be done in binary.

Using the example of 88 / 8 from the above example

         1011 r0
     ________
1000 )1011000
      1000
      ----
       0110
       0000
       ----
        1100
        1000
        ----
         1000
         1000
         ----
         0000

You can see the steps in the long way of doing long division for binary is again quite tedious, and for a power of two, you can just skip to the answer by in effect, canceling the zeros.

(as a side note, if this is an interesting area for you, you may find browsing the binary tag on Math.SE, well... interesting.)

Answer 2

This a specific optimization that is made in the case that the programmer knows the divisor will be a power of 2.

If the divisor is anything but a power of 2, then this optimization is not possible and code must be rewritten to use regular division.

So, for example, if we have a function that is

dividebyNumberOFWeekendDays ( dividend )

Return dividend >> 1;

We had better hope that our magic number of weekend days never becomes something other than a power of two because then we need to rewrite and unit test the function all over again.

Answer 3

If you write

 b=a/2;

you have to trust the compiler for optimizing it to a "shift" operation on the machine code level (which is typically faster that a general division instruction). And about 25 years ago, when I started working with C compilers, you could not be sure that the compiler worked like this. Today, any decent C compiler knows how to optimize this (at least, when you don't disable the optimizer).

If, however, you write

 b=a>>1;

you can be (almost) sure that the compiler generates a shift operation, if you activate the optimizer or not.

Answer 4

The simple answer is: performance. Shifting is much faster than division.

It may be that the author of the C code did optimize the division/multiplication because shifting does the same as dividing/multiplying by 2 (or by powers of 2) but is faster about 100 times on most of the CPUs. But in most modern C compilers this optimization is done by compiler itself.