InterviewSolution
Saved Bookmarks
InterviewSolution
| 1. |
Multiply two numbers using bitwise operators. |
|
Answer» The Russian peasant algorithm is an intriguing method. The goal is to keep doubling the first number while HALVING the second until the second number NEVER becomes 1. Then add the first number to the RESULT anytime the second number becomes odd during the OPERATION (result is initialised as 0). // C++unsigned int multiply(unsigned int x, unsigned int y){ int ans = 0; // initialise the ans variable // While the second number is not equal to 1 while (y > 0) { // If second number is odd, we will add the first number to ans if (y & 1) ans = ans + x; // then multiply the first number by 2 and divide the second number by 2 x = x << 1; y = y >> 1; } return ans;}
If y is even, the value of x*y is (x*2)*(y/2); otherwise, the value is ((x*2)*(y/2) + x. We keep multiplying 'x' by 2 and dividing 'y' by 2 in the while loop. We add 'x' to 'ans' if 'y' is odd in the loop. The ANSWER is obtained when the value of 'y' equals 1, and the value of 'ans' + 'x' equals 1. When 'y' is a power of two, the 'ans' remains 0 and the multiplication is done by 'x'. |
|