4
$\begingroup$

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?

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

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.