Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Multiplication of two integers using bitwise operators

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

like image 841
SuperMan Avatar asked Dec 16 '10 00:12

SuperMan


People also ask

How do you do Bitwise multiplication in Python?

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.

How do you multiply by 10 Bitwise Operators?

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.

How do you use a shift operator to multiply by 2?

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.

How do shift operators multiply?

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.


1 Answers

#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

like image 179
zengr Avatar answered Sep 18 '22 22:09

zengr