CODEWITHSUNDEEP
cbitwise-operators
Doe Jensen
Doe Jensen

Reputation: 41

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.

Upvotes: 4

Views: 699

Answers (5)

DaBler
DaBler

Reputation: 2853

Yes, for instance, the following function returns a*b, where b is either +1 or -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:

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.

Upvotes: 4

Leo K
Leo K

Reputation: 5354

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 += (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.

Upvotes: 4

alk
alk

Reputation: 70951

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:

i == i1 * i2

Upvotes: 0

mrks
mrks

Reputation: 8343

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

  • Signed magnitude
  • Ones' complement
  • Two’s complement

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.

Upvotes: 0

user5329483
user5329483

Reputation: 1272

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.

Upvotes: 1

Related Questions