How can i multiply and divide with only using bit shifting and adding?

Question

How can i multiply and divide with only using bit shifting and adding?

Answer 1

X * 2 = 1 bit shift left
X / 2 = 1 bit shift right
X * 3 = shift left 1 bit and then add X

Answer 2

1. A left shift by 1 position is analogous to multiplying by 2. A right shift is analogous to dividing by 2.
2. You can add in a loop to multiply. By picking the loop variable and the addition variable correctly, you can bound performance. Once you've explored that, you should use Peasant Multiplication

Answer 3

x << k == x multiplied by 2 to the power of k
x >> k == x divided by 2 to the power of k

You can use these shifts to do any multiplication operation. For example:

x * 14 == x * 16 - x * 2 == (x << 4) - (x << 2)
x * 12 == x * 8 + x * 4 == (x << 3) + (x << 2)

To divide a number by a non-power of two, I'm not aware of any easy way, unless you want to implement some low-level logic, use other binary operations and use some form of iteration.

Answer 4

Take two numbers, lets say 9 and 10, write them as binary - 1001 and 1010.

Start with a result, R, of 0.

Take one of the numbers, 1010 in this case, we'll call it A, and shift it right by one bit, if you shift out a one, add the first number, we'll call it B, to R.

Now shift B left by one bit and repeat until all bits have been shifted out of A.

It's easier to see what's going on if you see it written out, this is the example:

      0
   0000      0
  10010      1
 000000      0
1001000      1
 ------
1011010

Answer 5

To multiply in terms of adding and shifting you want to decompose one of the numbers by powers of two, like so:

21 * 5 = 10101_2 * 101_2             (Initial step)
       = 10101_2 * (1 * 2^2  +  0 * 2^1  +  1 * 2^0)
       = 10101_2 * 2^2 + 10101_2 * 2^0 
       = 10101_2 << 2 + 10101_2 << 0 (Decomposed)
       = 10101_2 * 4 + 10101_2 * 1
       = 10101_2 * 5
       = 21 * 5                      (Same as initial expression)

(_2 means base 2)

As you can see, multiplication can be decomposed into adding and shifting and back again. This is also why multiplication takes longer than bit shifts or adding - it's O(n^2) rather than O(n) in the number of bits. Real computer systems (as opposed to theoretical computer systems) have a finite number of bits, so multiplication takes a constant multiple of time compared to addition and shifting. If I recall correctly, modern processors, if pipelined properly, can do multiplication just about as fast as addition, by messing with the utilization of the ALUs (arithmetic units) in the processor.