Bitshift to multiply by any number

8
votes

Using only adding, subtracting, and bitshifting, how can I multiply an integer by a given number?

For example, I want to multiply an integer by 17.

I know that shifting left is multiplying by a multiple of 2 and shifting right is dividing by a power of 2 but I don’t know how to generalize that.

What about negative numbers? Convert to two's complement and do the same procedure?

(EDIT: OK, I got this, nevermind. You convert to two's complement and then do you shifting according to the number from left to right instead of right to left.)

Now the tricky part comes in. We can only use 3 operators.

For example, multiplying by 60 I can accomplish by using this:

(x << 5) + (x << 4) + (x << 3) + (x << 2)

Where x is the number I am multiplying. But that is 7 operators - how can I condense this to use only 3?

4
cbit-manipulation
In general multiplications cannot be done in 3 operations of shifts, add/subtracts... But both 17 and 60 can be done in 3 operations. (hint: try a subtraction for 60) EDIT: I didn't see this was already answered. – Mysticial
they made the problems so the conveniently work in 3 operators haha. thanks for all the help. – Adam

4 Answers

13
votes

It's called shift-and-add. Wikipedia has a good explanation of this:

http://en.wikipedia.org/wiki/Multiplication_algorithm#Shift_and_add

EDIT: To answer your other question, yes converting to two's compliment will work. But you need to sign extend it long enough to hold the entire product. (assuming that's what you want)

EDIT2: If both operands are negative, just two's compliment both of them from the start and you won't have to worry about this.

7
votes

Here's an example of multiplying by 3:

unsigned int y = (x << 1) + (x << 0);

(where I'm assuming that x is also unsigned).

Hopefully you should be able to generalise this.

4
votes

17 = 16 + 1 = (2^4) + (2^0). Therefore, shift your number left 4 bits (to multiply by 2^4 = 16), and add the original number to it.

Another way to look at it is: 17 is 10001 in binary (base 2), so you need a shift operation for each of the bits set in the multiplier (i.e. bits 4 and 0, as above).

I don't know C, so I won't embarrass myself by offering code.

4
votes

As far as I know, there is no easy way to multiply in general using just 3 operators.

Multiplying with 60 is possible, since 60 = 64 - 4: (x << 6) - (x << 2)