CareerCup

public int multiply(int a, int b){
int c = a/2;
int d = a%2;
int result;
for(int i =0;i<c;i+=2)
result += d*2;
if(d>0)
result +=d;
return result ;
}

Suppose A and B are the two numbers to be multiplied. Look at the binary representation of B. If bit position i of B is set, we want to multiply A by 2^i (i.e. multiply A by 2, i times). Do the preceding for all bits of B, then add up all the results to get the desired product. Pseudo-code follows:

Proc Multiply(A, B):
  result <- 0
  A_shift <- A
  For i <- 0 to most significant bit index of B:
    If bit i of B is set:
      result <- result + A_shift
    EndIf
    A_shift <- A_shift * 2
  EndFor
  Return result
EndProc

So the first solution (by Anonymous) is wrong--if a is even, d will always be 0, so result will be 0.

The second solution (by Bullocks) seems correct, but the problem is that his program does not really show how to get a binary representation of a number, how to get a single bit from that number, etc. All these can be obtained by just multiplying and dividing by 2 but doing this is not trivial and would make the code really complicated.

So here is a simple solution that relies only on division by 2, multiplication by 2, and addition of 2 numbers.

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;
}

#define MULTIPLYBYTWO(x) ((x) * 2)
#define DIVIDEBYTWO(x) ((x) / 2)
#define ADDTWO(x, y) ((x) + (y))
#define REMAINDER(x) ((x) % 2)

int multiplyWithLimitation(int p, int q)
{
	if(q == 1)
		return p;

	if(REMAINDER(q) == 0)
		return multiplyWithLimitation(MULTIPLYBYTWO(p), DIVIDEBYTWO(q));
	else
		return (p + multiplyWithLimitation(MULTIPLYBYTWO(p), DIVIDEBYTWO(q)));
}