Bitshift times any number

Question

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

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

I know that the left offset is multiplied by a multiple of 2, and the right offset divides by 2, but I don't know how to generalize it.

---

What about negative numbers? Convert to two additions and perform the same procedure?

( EDIT: Well, I got this, it doesn’t matter. You convert into two additions, and then go according to the number from left to right, and not from right to left.)

---

Now the tricky part appears. We can use only 3 operators.

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

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

Where x is the number I multiply. But these are 7 operators - how can I condense this to use only 3?

Answer 1

As far as I know, there is no easy way to reproduce in the general case using only 3 operators.

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

Answer 2

It is called shift-and-add. Wikipedia has a good explanation:

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

EDIT: To answer your other question, yes, the translation will work for two compliments. But you need to sign renew it long enough to hold the entire product. (assuming what you want)

EDIT2: If both operands are negative, only two compliment both of them from the start, and you don’t have to worry about that.

Answer 3

Here's an example of multiplying by 3:

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

(where I assume x also unsigned ).

Hope you can generalize this.

Answer 4

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

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

I do not know C, so I am not embarrassed by suggesting code.