Question

How can I perform multiplication without the '*' operator?

I was just going through some basic stuff as I am learning C. I came upon a question to multiply a number by 7 without using the * operator. Basically it's like this

      (x << 3) - x;

Now I know about basic bit manipulation operations, but I can't get how do you multiply a number by any other odd number without using the * operator? Is there a general algorithm for this?

 45  47854  45
1 Jan 1970

Solution

 59

Think about how you multiply in decimal using pencil and paper:

  12
x 26
----
  72
 24
----
 312

What does multiplication look like in binary?

   0111
x  0101
-------
   0111
  0000
 0111
-------
 100011

Notice anything? Unlike multiplication in decimal, where you need to memorize the "times table," when multiplying in binary, you are always multiplying one of the terms by either 0 or 1 before writing it down in the list addends. There's no times table needed. If the digit of the second term is 1, you add in the first term. If it's 0, you don't. Also note how the addends are progressively shifted over to the left.

If you're unsure of this, do a few binary multiplications on paper. When you're done, convert the result back to decimal and see if it's correct. After you've done a few, I think you'll get the idea how binary multiplication can be implemented using shifts and adds.

2010-01-15

Solution

 25

Everyone is overlooking the obvious. No multiplication is involved:

10^(log10(A) + log10(B))
2010-01-15