Bitshift to multiply by any number

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开发者_如何学Python 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?

---

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.

---

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.

---

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)

---

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.

---

Numbers that would work with using only 3 operators (a shift, plus or minus, and another shift) is limited, but way more than the 3, 17 and 60 mentioned above. If a number can be represented as (2^x) +/- (2^y) it can be done with only 3 operators.