Multiply with negative integer just by shifting.

Question

Hi,

I'm trying to find a way to multiply an integer value with negative value just with bit shifting.

Usually I do this by shifting with the power of 2 which is closest to my factor and just adding / subtracting the rest, e.g. x * 7 = ((x << 3) - x)

Let's say I'd want to calculate x * -112. The only way I can imagine is -((x << 7) - (x << 4), so to calculate x * 112 and negate it afterwards.

Is there a "prettier" way to do this?

Answer 1

Get the compiler to do it, then check the produced assembly.

Answer 2

The negative of a positive number in 2's complement is done by negating all the bits and then adding 1 to the result. For example, to get -4 from 4 you would do:

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

Same to reverse the sign.

So you could do this:

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

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

Not that I'm saying you should do this, because you shouldn't. It's good to know about it though.

Answer 3

Computers internally represent negative integers in two's compliment form. One of the nice properties of two's compliment arithmetic is that multiply negative numbers is just like multiplying positive numbers. Hence, find the two's complement and use your normal approach.

Here's a simple example. For ease of exposition, I'm going to using 8-bit integers and multiply by -15.

15 in hex is 0x0f. The two's compliment of 0x0f is 0xf1.

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

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