Multiplication using only 3 operations: x*2, x/2, and add(x, y)

You have a machine which can do only multiply by 2, divide by 2 and
Addition of 2 numbers. Write a detailed algorithm to multiply any two
numbers, in this kind of a machine.

public static int Multiply(int a, int b)
{
    if (a == 0 || b == 0) return 0;
    int result = 0;
    while (b > 0)
    {
        if (b % 2 != 0)     // the same as  if (b != (b / 2) * 2)
            result = result + a;
        a *= 2;
        b /= 2;
    }
    return result;
}

Leave a Reply

Your email address will not be published. Required fields are marked *