performance - primaria - Cómo voltear el signo de un valor entero usando alguna constante y operador(es) sin multiplicación/ramificación

division de fracciones inversas

Question

Estoy buscando una expresión que me permita escribir con las siguientes propiedades:

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

sin multiplicación / ramificación, lo más eficiente posible.

A primera vista, x ^ 0x80000000 parece ser un candidato, pero no funciona cuando x es 0.

Answer 1

Aquí hay una expresión bastante escueta que resolverá el problema:

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

Esto funcionará para los enteros complementarios de 32 bits 2, donde x es la entrada, e y es 1 o 0. 1 significa devolver el signo opuesto de x, 0 significa devolver el mismo signo que x.

Aquí hay una versión más larga de esa expresión en la función f (). He agregado algunos casos de prueba para verificar.

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

Answer 2

Ok, finalmente descubrí cómo hacerlo de manera eficiente:

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

Estas funciones anteriores devuelven -sgn(x) y es -1 y sgn(x) contrario.

O bien, si solo necesitamos trabajar para cada valor distinto de -2 ^ 31 (valor mínimo mínimo sin firmar), con la ventaja de preservar el valor absoluto, esta es la función que invierte el signo, dependiendo de la variable y:

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

La derivación : -x == ~ x + 1 == (x ^ 0xFFFFFFFF) + 1 == (x ^ -1) + 1 == (x ^ -1) - (-1). Sustituyendo -1 con y, obtenemos una fórmula de dos variables que tiene una propiedad interesante que devuelve x sin cambios si y se establece en 0, porque ni (x ^ 0) ni resta 0 cambia el resultado. Ahora el caso de la esquina es si x es igual a 0x8000000 cuando esta fórmula no funciona. Esto se puede solucionar aplicando la función sgn (x), entonces tenemos (sgn(x) ^ y) - y) . Finalmente, reemplazamos las funciones sgn (x) con las fórmulas bien conocidas que no usan ramificación.