Multiply with a negative integer by only shifting

Question

I am trying to find a way to multiply an integer value with a negative value with just a bit shift.

I usually do this by moving with a force of 2, which is closest to my coefficient, and just adding / subtracting the rest, for example. x * 7 = ((x << 3) - x)

Say I would like to calculate x * -112 . The only way I can imagine this -((x << 7) - (x << 4) , therefore, to calculate x * 112 and the subsequent negation.

Is there a nicer way to do this?

Answer 1

A negative value of a positive number in 2 complement is performed by negating all bits, and then adding 1 to the result. For example, to get -4 out of 4, you would do:

4 = 000...0100 in binary. ~4 = 111...1011. -4 = 111...1100.

Same as vice versa.

So you can do this:

(~((x << 7) - (x << 4))) + 1 .

Not necessarily prettier, but faster if you consider bitwise operations faster than arithmetic operations (especially multiplication) and ignore compiler optimization.

Not that I said that you should do this because you should not. Good to know about it though.

Answer 2

Get the compiler to do this, and then check the build.

Answer 3

Computers internally represent negative integers in two forms of compliment . One of the nice properties of two arithmetic arithmetic is that multiplying negative numbers is exactly the same as multiplying negative numbers. Therefore, find two additions and use your usual approach.

Here is a simple example. For convenience, I'm going to use 8-bit integers and multiply by -15.

15 in hexadecimal format - 0x0f. Two compliments of 0x0f are equal to 0xf1.

Since these are 8-bit integers, all arithmetic values ​​have mod 0xff. In particular, note that 0x100 * anything = 0.

 x * 0xf1 = x * (0x100 - 0x10 + 0x01) = -(x * 0x10) + x = -(x << 4) + x