30

I am working through a problem which I was able to solve, all but for the last piece—I am not sure how one can do multiplication using bitwise operators:

0*8 = 0

1*8 = 8

2*8 = 16

3*8 = 24

4*8 = 32

Is there an approach to solve this?

0

10 Answers 10

52

To multiply by any value of 2 to the power of N (i.e., 2^N), shift the bits N times to the left.

0000 0001 = 1

times 4 = (2^2 => N = 2) = 2 bit shift : 0000 0100 = 4

times 8 = (2^3 -> N = 3) = 3 bit shift : 0010 0000 = 32

etc..

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. I.e.,

since: 17 = 16  + 1
thus:  17 = 2^4 + 1

therefore: x * 17 = (x * 16) + x in other words 17 x's

Thus to multiply by 17, you have to do a 4 bit shift to the left, and then add the original number again:

==> x * 17 = (x * 16) + x
==> x * 17 = (x * 2^4) + x
==> x * 17 = (x shifted to left by 4 bits) + x

so let x = 3 = 0000 0011

times 16 = (2^4 => N = 4) = 4 bit shift : 0011 0000 = 48

plus the x (0000 0011)

I.e.,

    0011 0000  (48)
+   0000 0011   (3)
=============
    0011 0011  (51)

Charles Petzold has written a fantastic book 'Code' that will explain all of this and more in the easiest of ways. I thoroughly recommend this.

1
  • right. it's not quite the same thing though. what if you want to multiply 3*17 Sep 15, 2010 at 21:45
18

To multiply two binary encoded numbers without a multiply instruction. It would be simple to iteratively add to reach the product.

unsigned int mult(x, y)
unsigned int x, y;
{
    unsigned int reg = 0;

    while(y--)
        reg += x;
    return reg;
}

Using bit operations, the characteristic of the data encoding can be exploited. As explained previously, a bit shift is the same as multiply by two. Using this an adder can be used on the powers of two.

// multiply two numbers with bit operations

unsigned int mult(x, y)
unsigned int x, y;
{
    unsigned int reg = 0;

    while (y != 0)
    {
        if (y & 1)
        {
            reg += x;
        }
        x <<= 1;
        y >>= 1;
    }
    return reg;
}
2
  • What programming language? C? Aug 24 at 19:59
  • OK, the OP has left the building: "Last seen more than 10 years ago" Aug 24 at 20:00
3

You'd factor the multiplicand into powers of 2.
3*17 = 3*(16+1) = 3*16 + 3*1 ... = 0011b << 4 + 0011b

2
  • If this approach is used, doesn't that mean that multiplying a number by (2^n)-1 would be the most work for a processor?
    – user4531029
    Sep 24, 2016 at 20:23
  • One might ask himself how to get the splitted powers of 2 in an easy way... This is what stackoverflow.com/a/28158393/6280369 does... so in addition given answer: 3*17 = ??? => 17 = b10001 = 16*1 + 8*0 + 4*0 +2*0 +1*1 => 3*17 = 1*1*3 + 0*2*3+0*4*3+0*8*3+1*16*3 (multiplying by powers of 2 is easy: shifting left 'power' times, simply said add a zero) = 1*3 + 1*3*2*2*2*2 = b11 + b110000 = b110011 = 3 + 48 = 51
    – WiRa
    Nov 16, 2018 at 8:43
3

Use:

public static int multi(int x, int y) {
    boolean neg = false;
    if(x < 0 && y >= 0) {
        x = -x;
        neg = true;
    }
    else if(y < 0 && x >= 0) {
        y = -y;
        neg = true;
    }else if(x < 0 && y < 0) {
        x = -x;
        y = -y;
    }

    int res = 0;
    while(y != 0) {
        if((y & 1) == 1)
            res += x;
        x <<= 1;
        y >>= 1;
    }
    return neg ? (-res) : res;
}
1
1

I believe this should be a left shift. 8 is 2^3, so left shift 3 bits:

2 << 3 = 8

1
  • 10
    Shouldn't it be 2 << 3 = 16? 2 = 00000010, therefore, if you left shift the number '2' three times you would get 00010000 = 16 (not 8). Oct 5, 2015 at 2:55
0

Using a bitwise operator reduces the time complexity.

In C++:

#include<iostream>
using name space std;

int main(){
   int a, b, res = 0;           // read the elements
   cin>>a>>b;

   // find the small number to reduce the iterations

   small = (a<b)?a:b;           // small number using ternary operator
   big = (small^a)?a:b;         // big number using bitwise XOR operator

   while(small > 0)
   {
      if(small & 1)
      {
         res += big;
      }
      big = big << 1;           // it increases the number << is big * (2 power of big)
      small = small >> 1;       // it decreases the number >> is small / (2 power of small)
   }
   cout<<res;
}

In Python:

a = int(input())
b = int(input())
res = 0

small = a if(a < b) else b
big  = a if(small ^ a) else b

def multiplication(small, big):
    res = 0
    while small > 0:
        if small & 1:
            res += big
        big = big << 1
        small = small >> 1

        return res

 answer = multiplication(small, big)
 print(answer)
0

I was working on a recursive multiplication problem without the * operator and came up with a solution that was informed by the top answer here.

I thought it was worth posting because I really like the explanation in the top answer here, but wanted to expand on it in a way that:

  1. Had a function representation.
  2. Handled cases where your "remainder" was arbitrary.

This only handles positive integers, but you could wrap it in a check for negatives like some of the other answers.

Python:

def rec_mult_bitwise(a,b):
    # Base cases for recursion
    if b == 0:
        return 0
    if b == 1:
        return a

    # Get the most significant bit and the power of two it represents
    msb = 1
    pwr_of_2 = 0
    while True:
        next_msb = msb << 1
        if next_msb > b:
            break
        pwr_of_2 += 1
        msb = next_msb
        if next_msb == b:
            break

    # To understand the return value, remember:
    # 1: Left shifting by the power of two is the same as multiplying by the number itself (ie x*16=x<<4)
    # 2: Once we've done that, we still need to multiply by the remainder, hence b - msb
    return (a << pwr_of_2) + rec_mult_bitwise(a, b - msb)
0
0

Use:

-(int)multiplyNumber:(int)num1 withNumber:(int)num2
{
    int mulResult = 0;
    int ithBit;

    BOOL isNegativeSign = (num1 < 0 && num2 > 0) ||
                          (num1 > 0 && num2 < 0);
    num1 = abs(num1);
    num2 = abs(num2);

    for(int i=0; i<sizeof(num2)*8; i++)
    {
        ithBit = num2 & (1<<i);
        if(ithBit > 0)
        {
            mulResult += (num1 << i);
        }

    }

    if (isNegativeSign)
    {
        mulResult = ((~mulResult) + 1);
    }

    return mulResult;
}
1
-1

I have just realized that this is the same answer as the previous one. LOL sorry.

public static uint Multiply(uint a, uint b)
{
   uint c = 0;
   while(b > 0)
   {
      c += ((b & 1) > 0) ? a : 0;
      a <<= 1;
      b >>= 1;
   }
   return c;
}
1
  • 3
    Welcome to Stack Overflow. If this is a duplicate answer then you can help manage the site by deleting your own post
    – Alex S
    Aug 20, 2015 at 19:39
-1
def multiply(x, y):
     return x << (y >> 1)

You would want to halve the value of y, hence y shift bits to the right once (y >> 1) and shift the bits again x times to the left to get your answer x << (y >> 1).

1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.