Multiply without multiply Write the fastest (best big-O) and smallest multiplication algorithm for positive integers, without using multiplication operators. You are only allowed addition, subtraction, logical functions (AND, OR, XOR, NOT), bit shift, bit rotate, bit flip/set/clear and bit test. Your program should be capable of multiplying 16-bit numbers to produce a 32-bit result. Take input on stdin, separated by commas, spaces or new lines (your choice), but make it clear how to input the data.

Example input/output:

734 929
681886
C, 84 83 78 Characters
 
m;main(a,b){for(scanf(&quot;%d%d&quot;,&amp;a,&amp;b);a;b+=b)a&amp;1?m+=b:0,a&gt;&gt;=1;printf(&quot;%d\n&quot;,m);}

In a more readable form
m;main(a,b)
{
    scanf(&quot;%d%d&quot;,&amp;a,&amp;b);
    while (a)
    {
        if (a&amp;1)
           m+=b;
        a&gt;&gt;=1;
        b+=b;
    }
    printf(&quot;%d\n&quot;,m);
}

The algorithm is better known as the Ethiopian Multiplication or the Russian Peasant Multiplication.Here’s the algorithm :

Let the two numbers to be multiplied be a and b.
If a is zero then break and print the result.
If a is odd then add b to the result.
Half a, Double b. Goto Step 2.