Ygthkb

At Geeks for Geeks, I came across a question "Add two numbers without using arithmetic operators", which basically states that you can multiply two numbers using the left shift operator. I am confused how that can be accomplished. I am trying to understand the logic here. It states that

We can solve this problem with the shift operator. The idea is based
on the fact that every number can be represented in binary form. And
multiplication with a number is equivalent to multiplication with
powers of 2. Powers of 2 can be obtained using left shift operator.

I dont understand what the above means. I know that left shifting by 1 is like multiplying by 2, and left shifting by 2 is is like multiplying that number by 4. However, I am confused at how I can use left shift to evaluate something like 7 * 3 ?

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.

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^0right)$. 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^1right) + left(2^2 + 2^1 + 2^0right)$, 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^2right) + left(2^2 + 2^1right) + left(2^1 + 2^0right) = 21$. In this case, the terms are different, and there are $3$ instead of $2$, but the sum is still the same of course.