Optimize integer multiplication with +/-1

Is it possible to optimize multiplication of an integer with -1/1 without using any multiplication and conditionals/branches?

Can it be done only with bitwise operations and integer addition?

Edit: The final goal is to optimize a scalar product of two integer vectors, where one of the vectors has only -1/1 values.

i = ~i + 1;

-O3

5 Answers
5

Most modern processors have an ALU with a fast multiplier (meaning it takes about the same time to add two numbers as to multiply them, give or take one CPU clock), so doing anything but for (i=0;i<VectorLength;++i) { p += (x[i] * y[i]) ; } isn't likely to help. However, try a simple if and see if that gives any benefits gained from the CPU's branch prediction:

for (i=0;i<VectorLength;++i) { p += (x[i] * y[i]) ; }

if

for (i=0;i<VectorLength;++i) { p += (y[i]<0) ? -x[i] : x[i] ; }


In any case, if the CPU has fast multiply, doing any trick that involves more than one ALU operation (e.g., negation followed by addition, as in some of the examples given here) will more likely cause loss of performance compared to just one multiplication.

Yes, for instance, the following function returns a*b, where b is either +1 or -1:

a*b

b

+1

-1

int mul(int a, int b)
{
int c[3] = { -a, 0, +a };

return c[1+b];
}


or if both a and b are restricted to +-1:

a

b

+-1

int mul(int a, int b)
{
int c[5] = { +1, 0, -1, 0, +1 };

return c[a+b+2];
}


Yet another variant without memory access (faster than the ones above):

int mul(int a, int b)
{
return 1 - (signed)( (unsigned)(a+1) ^ (unsigned)(b+1) );
}


This answer works with any signed integer representation (sign-magnitude, ones' complement, two's complement) and does not cause any undefined behaviour.

However, I cannot guarantee that this will be faster than normal multiplication.

mul(INT_MIN, 1)

int Multiplication(int x, int PlusOrMinusOne)
{
PlusOrMinusOne >>= 1; //becomes 0 or -1
//optionally build 2's complement (invert all bits plus 1)
return (x ^ PlusOrMinusOne) + (PlusOrMinusOne & 1);
}


Here a nice resource for such Bit Twiddling Hacks.

PlusOrMinusOne

Strictly speaking, no, because C allows for three different integer representations:

There is a proposal to strictly make it two's complement but until that makes it into the standard, you don't know what your negative numbers look like, so you can't really do too many bit hacks with them.

Less strictly speaking, most implementations use two's complement, so it is reasonably safe to use the hacks shown in other answers.

Assuming 2's compliment for integers:

int i1 = ...; // +1 or -1
int i2 = ...; // +1 or -1
unsigned u1 = i1 + 1; // 0 or 2
unsigned u2 = i2 + 1; // 0 or 2
unsigned u = u1 + u2; // 0 or 2 or 4: 0 and 4 need to become 1, 2 needs to become -1
u = (u & ~4); // 0 is 1 and 2 is -1
int i = u - 1; // -1 is 1 and 1 is -1
i = ~i + 1; // -1 is -1 and 1 is 1 :-)


The same as one-liner:

int i = ~(((i1 + i2 + 2) & ~4) - 1) + 1;


The following is true for i1 and i2 being either +1 or -1:

i1

i2

+1

-1

i == i1 * i2


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.