Bitshift to multiply by any number

Question

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?

Answer 1

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.