[Math] Binary multiplication as combination of addition and left shift

binarybinary operations

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?

Best Answer

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

Related Question