How can I multipy two integers using bitwise operators?
I found an implementation here. Is there a better way of implementing multiplication?
For example: 2 * 6 = 12 must be performed using bitwise operators.
NOTE: Numbers are arbitrary, not power of 2
To multiply by any value of 2 to the power of N (i.e. 2^N) shift the bits N times to the left. To divide shift the bits to the right. The bits are whole 1 or 0 - you can't shift by a part of a bit thus if the number you're multiplying by is does not factor a whole value of N ie. ie.
Here we need to perform 10 operations. A better solution is to use bit manipulation. We have to multiply n with 10 i.e; n*10, we can write this as n*(2+8) = n*2 + n*8 and since we are not allowed to use multiplication operator we can do this using left shift bitwise operator. So n*10 = n<<1 + n<<3.
And multiplication with a number is equivalent to multiplication with powers of 2. Powers of 2 can be obtained using left shift operator. Check for every set bit in the binary representation of m and for every set bit left shift n, count times where count if place value of the set bit of m and add that value to answer.
The number to the left of the operator is shifted the number of places specified by the number to the right. Each shift to the left doubles the number, therefore each left shift multiplies the original number by 2. Use the left shift for fast multiplication or to pack a group of numbers together into one larger number.
#include <stdio.h> int main(void) { int a, b, result; printf("Enter the numbers to be multiplied:"); scanf("%d%d", &a, &b); // a > b result = 0; while (b != 0) // Iterate the loop till b == 0 { if (b & 1) // Bitwise & of the value of b with 1 { result = result + a; // Add a to result if b is odd . } a <<= 1; // Left shifting the value contained in 'a' by 1 // Multiplies a by 2 for each loop b >>= 1; // Right shifting the value contained in 'b' by 1. } printf("Result: %d\n",result); }
Source
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With