Optimize integer multiplication with +/-1

  • A+
Category:Languages

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.

 


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]; } 

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.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: