# Binary multiplication as combination of addition and left shift

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?

• Sure: that’s basically just the usual pencil-and-paper algorithm for multiplying two numbers, carried out in base two. – Brian M. Scott Aug 25 '16 at 17:45
• can you elaborate @Brian M. Scott ? – Ahashan Alam Sojib Aug 25 '16 at 17:48

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*}

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.