Binary multiplication as combination of addition and left shift

Question

A left shift of a binary number is shifting each bit one place to the left, and appending a 0 bit as the least significant bit. (The left shift of 1011 is 10110.) Can multiplication of any two binary numbers, for instance multiplication of 1101 by 110001, be implemented as a combination of additions and left shifts?

Answer 1

Everything is binary, leftshift of $10101$ denoted as $l(10101) = 101010$, note that $10*x = l(x)$. The basic idea is that you split one of the numbers up and use the distributive law. So your example would look like this:

\begin{eqnarray*} 1101 \cdot 110001 &=& 1101 \cdot (1 + 10000 + 100000) \\ &=& 1101 \cdot (1^0 + 10^4 + 10^5) \\ &=& 1101 \cdot 1^0 + 1101 \cdot 10^4 + 1101 \cdot 10^5 \\ &=& l^0(1101) + l^4(1101) + l^5(1101) \\ &=& 1101 + l(l(l(l(1101)))) + l(l(l(l(l(1101))))) \end{eqnarray*}

Answer 2

It’s basically a variant of the usual pencil-and-paper algorithm for multiplication, carried out in base two. A pencil-and-paper multiplication might look like this:

    110001  
      1101  
    ------  
    110001  
  110001  
 110001  
----------  
1001111101

You can break it up into left shifts and additions as follows. For each $1$ in the multiplier you’ll have a copy of the multiplicand left-shifted a number of times corresponding to the power of $2$ represented by that $1$. Here, for instance, the three $1$s in $1101$ represent $2^3,2^2$, and $2^0$, so you’ll have copies of $110001$ left-shifted $3$, $2$, and $0$ times. Those (in the opposite order) are the three product rows in the multiplication, the ones between the two horizontal lines. Once you have those, you simply add two of them, then add the next one to that partial sum, and keep going until you’re done.