Friday, September 16, 2011

Adobe Question: Multiply two numbers using bitwise operators

Solution:

A =            101
B =              10
                  -------
                    000
                  101x             x here denotes a left shift by 1 bit.
                  -------
Result =      1010

The magic is to check for the last bit of B. If the last bit is 1, then add ‘A’ to result else do nothing. And after every check right shift ‘B’ by 1 bit and left shift ‘A’ by 1 bit.

To add two numbers using bitwise, you need to implement the full adder where you calculate sum and carry as below:
Sum = A xor B (A ^ B)
Carry = A and B (A & B)


Source:
int bitwiseMultiply(int a, int b)
{
int result = 0;
while ( b != 0)
{
if ( b & 1)
{
result = sum( a, result);
}
a = a << 1; b = b >> 1;
}
return result;
}

int sum (int a, int b)
{
int sum = 0;
int carry = 0;
while ( a )
{
carry = a & b;
sum = a ^ b;
carry = carry << 1;
a = carry;
}
return sum;
}

No comments:

Post a Comment