CODEWITHSUNDEEP
performanceintegerbit-manipulationflipsign
eold
eold

Reputation: 6042

How to flip the sign of an integer value using some constant and operator(s) without multiplication/branching

I am looking for an expression which would enable me to write with the following properties:

f(x, SOME_CONSTANT) -> returns -x (or any negative value)
f(x, SOME_CONSTANT2) -> returns x (or any positive value)
f(0, SOME_CONSTANT) -> returns 0
f(0, SOME_CONSTANT2) -> returns 0

without multiplication/branching, as efficient as possible.

At first glance x ^ 0x80000000 seems like a candidate, but it doesn't work when x is 0.

Upvotes: 3

Views: 5888

Answers (2)

eold
eold

Reputation: 6042

Ok, I finally figured out how to do this efficiently:

Java:

int f(int x, int y) {
  return (((x >> 31) | ((unsigned)-x >> 31)) ^ y) - y;
}

C/C++:

int f(int x, int y) {
  return (((x > 0) - (x < 0)) ^ y) - y;
}

These above functions return -sgn(x) y is -1 and sgn(x) otherwise.

Or, if we just need to work for every value other then -2^31 (minimum unsigned int value), with the benefit of preserving the absolute value, this is the function which flips the sign, depending on the variable y:

int f(int x, int y) {
    return (x ^ y) - y; // returns -x for y == -1, x otherwise
}

The derivation: -x == ~x + 1 == (x ^ 0xFFFFFFFF) + 1 == (x ^ -1) + 1 == (x ^ -1) - (-1). Substituting -1 with y, we obtain a two-variable formula which has an interesting property that returns unchanged x if y is set to 0, because neither (x ^ 0) nor subtracting 0 changes the result. Now the corner case is if x is equal to 0x8000000 when this formula doesn't work. This can be fixed by applying the sgn(x) function, so we have (sgn(x) ^ y) - y). Finally, we replace the sgn(x) functions with the well-known formulas which do not use branching.

Upvotes: 2

mark
mark

Reputation: 5070

Here's a rather terse expression that will solve the problem:

return ((x < 0 ^ y) & x!=0) << 31 | (x!=0) << 31 >> 31 & 0x7fffffff & x | x==0x80000000 ;

This will work for 32 bit 2's complement integers, where x is the input, and y is either 1 or 0. 1 means return the opposite sign of x, 0 means return the same sign as x.

Here's a lengthier version of that expression in function f(). I've added some test cases to verify. 

#include <limits.h>
#include <stdio.h>

int bitsm1 = 31;
int rightbits = 0x7fffffff;


int f (x, y) {
  int sign_x = x < 0;
  int signtemp = sign_x ^ y; 
  int notzero = x!=0;
  int v = notzero << bitsm1;
  v = v >> bitsm1;
  v = v & rightbits;
  int b = v & x;
  int c = (signtemp & notzero) << bitsm1;
  int z = c | b;
  int res = z | (x==INT_MIN);
  return res;
}


int main () {
 printf("%d\n", f(0,0)); // 0
 printf("%d\n", f(0,1)); // 0
 printf("%d\n", f(1,0)); // +
 printf("%d\n", f(1,1)); // -
 printf("%d\n", f(-1,0)); // -
 printf("%d\n", f(-1,1)); // +
 printf("%d\n", f(INT_MAX,0)); // +
 printf("%d\n", f(INT_MAX,1)); // -
 printf("%d\n", f(INT_MIN,0)); // -
 printf("%d\n", f(INT_MIN,1)); // +


 return 0;
}

Upvotes: 0

Related Questions