Condicional tridireccional en C++ para determinar la equivalencia de signo de dos números

Question

Necesito la forma más eficiente (en ciclos de CPU) para determinar si dos números tienen el mismo/diferente signo. Pero la trampa es que si cualquiera de los números es cero, necesito poder distinguirlo de los números con signos iguales/diferentes (es decir, cero se trata como un "tercer" signo). El siguiente código es similar a lo que necesito, pero los valores de retorno pueden ser cualquier cosa, siempre que solo haya tres valores de devolución distintos.

int foo(int x, int y) { 
    if (x * y > 0) return 1; 
    if (x * y < 0) return -1; 
    return 0; 
} 

Por mi problema específico, los valores están en el rango [-6, 6] y X se garantiza que no sea 0. he encontrado una solución para encontrar si dos números tienen el mismo signo, y lo alteró para obtener la siguiente solución.

return y? (((x^y) >= 0)? 1 : -1) : 0; 

Debe haber algunos bitops/comparaciones que dan resultados más rápidos que el uso de la multiplicación, la ramificación, las comparaciones.

Answer 1

Aquí es otra versión (con trucos de manipulación de bits feos, no portátiles):

int foo(int x, int y) { 
    return ((x^y) >> 4) - ((x^(-y)) >> 4); 
} 

Algunas explicaciones:

• ((x^y) >> 4) es -1 si exactamente uno de X e Y es negativo, de lo contrario es 0.
• ((x^(-y)) >> 4) se -1 si exactamente uno de x e -y es negativa, si no es 0.
• Si x> 0 ey> 0, la r esultado habrá 0 - (-1) = 1.
• Si x < 0 e Y < 0, el resultado será 0 - (-1) = 1.
• Si x> 0 y y = 0, la resultado será 0 - 0 = 0.
• Si x < 0 e y = 0, el resultado será (-1) - (-1) = 0.
• Si x> 0 ey < 0, la el resultado será (-1) - 0 = -1.
• Si x < 0 y y> 0, el resultado será (-1) - 0 = -1.

Asume una aritmética de dos complementos y asume que >> se desplaza con la extensión de signo.

Answer 2

Su ejemplo no funciona porque no se pone paréntesis alrededor (x^y)

Esto está funcionando:

return y? (((x^y) >= 0) ? 1 : -1) : 0; 

Creo que no se puede hacer mucho más rápido si quieres para devolver -1, 1 o 0. Esto se debe a que -1 es 11111111 y es bastante diferente de 0 y 1. Un conjunto de operaciones de bits que devolvería 11111111, 0 o 1 sería complicado y ciertamente más lento que el código anterior.

EDIT: si en lugar de -1 y 1 se puede hacer frente a cualquier número negativo o positivo, entonces se puede eliminar una rama

return y ? ((x^y) | 1) : 0; 

Answer 3

¿Qué tal:

int foo(int x,int y) 
{ 
    // As suggested by Luther Blissett below in the comments. 
    // Increased the size of the array to 16x16. 
    // This allows for simpler optimization for the compiler 
    // Also use +8 rather +6 in the hopes that compiler optimization will be easier 
    // you never know (there may be some fancy trick. 
    static int sign[16][16] = { 
       { 1, 1, 1, 1, 1, 1, 1, 1, 0, -1, -1, -1, -1, -1, -1, -1}, 
       { 1, 1, 1, 1, 1, 1, 1, 1, 0, -1, -1, -1, -1, -1, -1, -1}, 
       { 1, 1, 1, 1, 1, 1, 1, 1, 0, -1, -1, -1, -1, -1, -1, -1}, 
       { 1, 1, 1, 1, 1, 1, 1, 1, 0, -1, -1, -1, -1, -1, -1, -1}, 
       { 1, 1, 1, 1, 1, 1, 1, 1, 0, -1, -1, -1, -1, -1, -1, -1}, 
       { 1, 1, 1, 1, 1, 1, 1, 1, 0, -1, -1, -1, -1, -1, -1, -1}, 
       { 1, 1, 1, 1, 1, 1, 1, 1, 0, -1, -1, -1, -1, -1, -1, -1}, 
       { 1, 1, 1, 1, 1, 1, 1, 1, 0, -1, -1, -1, -1, -1, -1, -1}, 
       { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
       { -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 1, 1, 1, 1, 1, 1}, 
       { -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 1, 1, 1, 1, 1, 1}, 
       { -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 1, 1, 1, 1, 1, 1}, 
       { -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 1, 1, 1, 1, 1, 1}, 
       { -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 1, 1, 1, 1, 1, 1}, 
       { -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 1, 1, 1, 1, 1, 1}, 
       { -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 1, 1, 1, 1, 1, 1} 
      }; 

    return sign[x+8][y+8]; 
} 

Esto debe ser rápido ya que no hay bifurcación que parará el procesador.

Con g ++ -O3 -S:

__Z3fooii: 
    pushl %ebp 
    movl %esp, %ebp 
    movl 8(%ebp), %eax 
    movl 12(%ebp), %edx 
    popl %ebp 
    sall $4, %eax 
    addl %edx, %eax 
    movl _ZZ3fooiiE4sign+544(,%eax,4), %eax 
    ret 

Answer 4

Se podría hacer algo como esto (sólo con los nombres de variables adecuadas y hecho mucho menos feo!) Tenga en cuenta que este sólo funciona con 2s complementan números y si sus valores están limitados a -6 a 6 como en sus preguntas.

Haz un perfil para asegurarte de que es más rápido que la forma clara de hacerlo y SOLO escribe código como este una vez que hayas determinado que no puedes cumplir tus requisitos con un enfoque mucho más obvio. con la predicción de ramas, etc., las ramas no siempre son lentas en x86, por ejemplo. Nunca escribiría un código no portatil como este a menos que no tuviera opción de cumplir con los requisitos de rendimiento.

Básicamente extraiga los bits de signo y exclusivo de ellos para obtener el resultado que desee.

int foo(int x, int y) 
{ 
    int s; 

    if (x == 0 || y == 0) return 0; 

    x = x >> 4; // Bit 0 of x will be the sign bit of x 
    y = y >> 4; // Bit 0 of y will be the sign bit of y 

    s = (x^y) & 1; // sign is 0 if they have the same sign, 1 otherwise 

    return 1 - 2 * s; // Make it 1 for the same sign, -1 otherwise 
} 

esta compila en mi compilador para un par de pruebas rápidas para el cero y lo que parece ser todo un poco eficiente de maniplation poco después de eso ...

test ecx, ecx 
    je SHORT $LN1@foo 
    test edx, edx 
    je SHORT $LN1@foo 
; Line 12 
    xor ecx, edx 
    mov eax, 1 
    sar ecx, 4 
    and ecx, 1 
    add ecx, ecx 
    sub eax, ecx 
; Line 13 
    ret 0 
$LN1@foo: 
; Line 5 
    xor eax, eax 
; Line 13 
    ret 0 

Answer 5

Editar:

((x*y)>>7) | -(-(x*y)>>7) 

rendimientos por encima de 1 si ambos son mismo signo, -1 si ambos son diferentes signos.
A continuación se muestra 1 si ambos son positivos, -1 si ambos son negativos.

Asumiendo valores de 32 bits firmados. Con | x, y | < 7 se podría cambiar por 3.

((x&y)>>31) // -1 or 0 
-((-x&-y)>>31) // 1 or 0 

((x&y)>>31) | -((-x&-y)>>31) 

Suponiendo < es 1 ó 0.

-((x&y)<0)  // -1 or 0 
((-x&-y)<0) // 1 or 0 

-((x&y)<0) | ((-x&-y)<0) 

De cualquier forma se parece a 8 operaciones.

Answer 6

Expresar el signo del número x como un entero "normalizado" (es decir, -1, 0, 1) usar

inline int sign(int x) { return (x > 0) - (x < 0); } 

Derivado de lo anterior, para comparar x y y para uso igualdad signo

inline bool same_sign(int x, int y) { 
    return sign(x) == sign(y); 
} 

para resultado booleano.

O, por -1, 0, +1 resultado

inline int compare_sign(int x, int y) { 
    return sign(x) * sign(y); 
} 

¿Qué tan eficiente que el código final será depende, por supuesto, de la calidad del compilador que está utilizando.

Answer 7

Una mezcla de soluciones por AndreyT y Loki Astari: sucursales, compacto, eficiente (dos búsquedas 1D matriz, con una multiplicación): enfoque más eficiente

static int S[13]= { -1, -1, -1, -1, -1, -1, 0, +1, +1, +1, +1, +1, +1 }, * Sign= &S[6]; 

return Sign[x] * Sign[y]; 

Alternativamente, una menos compacta (una multiplican, uno 1D matriz de búsqueda):!

static int S[73]= { 
-1, -1, -1, -1, -1, -1, 
-1, -1, -1, -1, -1, -1, 
-1, -1, -1, -1, -1, -1, 
-1, -1, -1, -1, -1, -1, 
-1, -1, -1, -1, -1, -1, 
-1, -1, -1, -1, -1, -1, 
0, 
+1, +1, +1, +1, +1, +1, 
+1, +1, +1, +1, +1, +1, 
+1, +1, +1, +1, +1, +1, 
+1, +1, +1, +1, +1, +1, 
+1, +1, +1, +1, +1, +1, 
+1, +1, +1, +1, +1, +1 }, * Sign= &S[36]; 

return Sign[x * y]; 

Answer 8

Si el [-6 .. + 6] restricción no se sostiene (ni x = 0), una solución sin sucursales está dado por (5 ops):

x*= y; 
return (x >> 31) - (-x >> 31); // Sign(x * y) 

y una solución que funcione para la gama completa es número entero (9): ops

return ((x >> 31) - (-x >> 31)) * ((y >> 31) - (-y >> 31)); // Sign(x) * Sign(y)