Multiplication between two numbers

Question

I have an assignment to build a function that multiplies 2 integer numbers and without using * or '-'. I can only use '+' '/' and '%'.

I noticed a lot of people are using shifting methods but i cant use without because we didn't learn it yet.

And as much as I can do it without 1 while loop easily the trick is it's supposed to be in n log n or log n runtime efficiency.

No list no arrays either though I don't see any way of using them anyway.

Is there any possible way of doing it ???

Answer 1

Here is another quick and dirty solution without recursivity that complies with the OP's requirement:

int Multiply(int a, int b)
{
  int result = 0;
  while (b > 0)
  {
    if (b % 2 != 0)
      result += a;

    a += a;
    b /= 2;
  }
  return result;
}

It's basically the same algorithm as the one in chmike's answer.

I didn't bother about the complexity but it looks pretty much like some O(log n).

It's definitely not working with negative values for b, I leave fixing this as an exercise.