Multiplying two numbers using only the "left shift" operator

I looked at the link, but couldn't find where it says the text you have quoted. Regardless, with what it says & for what you're asking for, i.e., multiplying by using just the shift operator, I believe it means that it works only for multiplying each power of $2$ by left shifting by that power value. You can then use the procedures & code in the link to add the numbers without using arithmetic operators, but with this also using bitwise XOR and AND.

With your example, note that $7 = 2^2 + 2^1 + 2^0$ and $3 = 2^1 + 2^0$. Let's say we start with $7$. Note that $7 \times 3$ is $7 \times \left(2^1 + 2^0\right)$. We use the distribution property to get that $7 \times 3 = 7 \times 2^1 + 7 \times 2^0$. For the first term, we can do a left-shift by $1$ bit, the add this to the original value as the second term is already $7$. As such, we get the result to be $\left(2^3 + 2^2 + 2^1\right) + \left(2^2 + 2^1 + 2^0\right)$, with this in decimal being $14 + 7 = 21$.

Alternatively, if we started with $3 = 2^1 + 2^0$, we would use that $7 = 2^2 + 2^1 + 2^0$ to do the multiplications & addition to get that $7 \times 3 = \left(2^3 + 2^2\right) + \left(2^2 + 2^1\right) + \left(2^1 + 2^0\right) = 21$. In this case, the terms are different, and there are $3$ instead of $2$, but the sum is still the same of course.


For example, to multiply $7 \times 3$, write both in binary : $$ 7 = 111 \quad; \quad 3 = 11 $$

Now, the point is, imagine doing long multiplication with these numbers : $$ \require{enclose} \begin{array}{} \ \ \ \ 111 \\[-3pt] \underline{\times \ \ \ 11 }\\[-3pt] \ \ \ \ 111 \\[-3pt] \underline{\ \ 1110} \\[-3pt] \underline{10101}(=21) \end{array} $$

The idea is this : $3$ has ones in both its units and "twos" position, so we shift $7$ by $0$, then $7$ by $1$, and add them up.

Now, imagine doing this for numbers with many zeros. For example , for : $$ 1010 = 10 \quad ; \quad 11 = 1011 $$

Then : $$ \require{enclose} \begin{array} \ \ \ \ \ \ \ \ 1010 \\[-3pt] \underline{\ \times \ 1011} \\[-3pt] \ \ \ \ \ \ \ 1010 \\[-3pt] \ \ \ \ \ 10100 \\[-3pt] \ \ \ \color{blue}{000000} \\[-3pt] \underline{\ 1010000} \\[-3pt] \underline{\ 1101110} \end{array} $$

Which amounts to adding $1010$'s left shifts zero times, one time and three times. Note that these are exactly the positions at which $1011$ has a one.

We will reverse the above and look at it :

$$ \require{enclose} \begin{array} \ \ \ \ \ \ \ \ 1011 \\[-3pt] \underline{\ \times \ 1010} \\[-3pt] \ \ \ \ \ \ \ \color{blue}{0000} \\[-3pt] \ \ \ \ \ {10110} \\[-3pt] \ \ \ \color{blue}{000000} \\[-3pt] \underline{\ 1011000} \\[-3pt] \underline{\ 1101110} \end{array} $$

Which is equivalent to adding $1011$ left-shifted exactly once and thrice, which are exactly the positions at which $1010$ has a one.

The above suggests a strategy for multiplying binary numbers $a$ and $b$ :

  • Find the positions at which $b$ has a one. Call these positions $p_1,p_2,...,p_n$.

  • Consider the binary numbers formed by left-shifting $a$ by $p_1, p_2,..,p_n$.

  • Add all these numbers, to get the answer.

Note that this does not involve "hard" multiplication, because the left shift is technically multiplication by powers of $2$ but (as for powers of $10$ in the decimal case) is easily performed, and we are reduced to the far easier operation of addition of the left shifts.

This technique often appears in books that cover quick multiplication techniques, especially by numbers which are close to powers of $2$.

EDIT: For Vakil's $20 \times 13$, I will first wrote down what he does, then how he gets the answer : $$ \begin{array}{rrr} 0 && 20 && 13 \\ 1 && 40 && 6 \\ 2 && 80 && 3 \\ 3 && 160 && 1 \\[1pt] \end{array} $$

Then he adds $160+80+20 = 260$, the right answer.

In procedure , this is what is happening :

  • On the first line we write the two numbers, and then indicate it as row number zero.

  • Then, in the next row we double the number in the second entry, divide the third entry by $2$ and round down , and indicate it as row number $1$.

  • We do this until we reach $1$ as the third entry of some row.

  • Now, in the second column, pick all entries such that the corresponding third entry is odd. So we picked $160$ because $1$ is odd, picked $80$ because $3$ is odd, did not pick $40$ as $6$ is even and picked $20$ as $13$ is odd.

  • Add those entries to get the answer.

How does this work? Let us write the same numbers above in binary to see what is happening : $$ \begin{array}{rrr} 0 && 10100 && 1101 \\ 1 && 101000 && 110 \\ 2 && 1010000 && 11 \\ 3 && 10100000 && 1 \\[1pt] \end{array} $$

We add $10100$ because $1101$ ends with $1$. We add $1010000$ because $11$ ends with $1$. We add $10100000$ because $1$ ends with $1$. We do not add $101000$ because $110$ ends with $0$.

Now it is fairly obvious how this algorithm comes to our rescue. The "division by two" step is nothing but "removing the last bit" in binary. Now, we focus on the last bit of the new number, and if this is $1$ we add that entry on the second row, otherwise we leave it. Again we divide by $2$, thus removing the last bit, etc.

I think from here you can figure out how the algorithm works, and how it corresponds to what I wrote earlier.

Tags:

Computer Science

Number Theory

Related

Showing that $\frac{\mathbb{R}[x]}{\langle x \rangle}$ and $\frac{\mathbb{R}[x]}{\langle x-1 \rangle}$ are not isomorphic as $\mathbb{R}[x]$ modules. Disprove or prove using delta-epsilon definition of limit that $\lim_{(x,y) \to (0,0)}{\frac{x^3-y^3}{x^2-y^2}} = 0$ Variance of sine and cosine of a random variable Integral $\int_0^{2π} e^{e^{ix}} dx$ non isomorphism between $A^1$ and zero set of $y^2-x^3=0$'s coordinate ring by cohomology argument? Computing the index $\left(\mathbb Z\left[\frac{1+\sqrt{5}}{2}\right]:\mathbb Z \left[\sqrt{5}\right]\right)$? Sets that are both Sum-free and Product-free Can we prove that infinite many primes begin with any given digitstring? Prove that the maximum score difference between two consecutive teams in a tournament with $n$ teams is $n$ When does the game end? How to prove closure property for $x\cdot y = \frac{x + y}{1 + \frac{xy}{c^2}}$? Is there a group $G$ and subgroup $H$, such that there exists $g\in G$ with $gHg^{-1} \subset H$ and $|H:gHg^{-1}|$ is infinite?

Recent Posts