Yahoo Interview Question
Software Engineer / DevelopersSuppose 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)));
}
public int multiply(int a, int b){
- Anonymous September 13, 2010int 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 ;
}