c++ - usuario - leer 10 números y determinar cuántos son positivos y cuántos son negativos dfd
n es negativo, positivo o cero? devuelve 1, 2 o 4 (8)
Estoy construyendo un intérprete de PowerPC, y funciona bastante bien. En la arquitectura Power, el registro de condición CR0 (EFLAGS en x86) se actualiza en casi cualquier instrucción. Se establece así. El valor de CR0 es 1, si el último resultado fue negativo, 2 si el último resultado fue positivo, 4 en caso contrario.
Mi primer método ingenuo para interpretar esto es:
if (n < 0)
cr0 = 1
else if (n > 0)
cr0 = 2;
else
cr0 = 4;
Sin embargo, entiendo que todas esas ramas no serán óptimas, ya que se ejecutan millones de veces por segundo. He visto algo de piratería en SO, pero ninguno parecía adeguado. Por ejemplo, encontré muchos ejemplos para convertir un número a -1, 0 o 1 según el signo o 0. ¿Pero cómo hacer -1 = 1, 1 = 2, 0 = 4? Estoy pidiendo la ayuda de los Bit Hackers ...
Gracias por adelantado
Actualización: Antes que nada: gracias chicos, han sido geniales. Probaré todos los códigos cuidadosamente para saber la velocidad y serás el primero en saber quién es el ganador.
@jalf: sobre su primer consejo, en realidad no estaba calculando CR0 en cada instrucción. Prefiero mantener una variable LastResult, y cuando (y si) una instrucción siguiente solicita una marca, haga la comparación. Tres motivaciones principales me llevaron de nuevo a la actualización "everytime":
- En PPC no está obligado a actualizar CR0 como en x86 (donde ADD siempre cambia EFLAGS, incluso si no es necesario), tiene dos sabores de ADD, una actualización. Si el compilador elige utilizar la actualización, significa que va a utilizar CR0 en algún momento, por lo que no tiene sentido retrasar ...
- Hay una instrucción particularmente dolorosa llamada mtcrf, que le permite cambiar el CR0 arbitrariamente. Incluso puede establecerlo en 7, sin significado aritmético ... Esto simplemente destruye la posibilidad de mantener una variable "lastResult".
El siguiente es mi intento.
int cro = 4 >> (((n > 0) - (n < 0)) % 3 + (n < 0)*3);
Estaba trabajando en esto cuando mi computadora se colgó.
int cr0 = (-(n | n-1) >> 31) & 6;
cr0 |= (n >> 31) & 5;
cr0 ^= 4;
Aquí está el ensamblaje resultante (para Intel x86):
PUBLIC ?tricky@@YAHH@Z ; tricky
; Function compile flags: /Ogtpy
_TEXT SEGMENT
_n$ = 8 ; size = 4
?tricky@@YAHH@Z PROC ; tricky
; Line 18
mov ecx, DWORD PTR _n$[esp-4]
lea eax, DWORD PTR [ecx-1]
or eax, ecx
neg eax
sar eax, 31 ; 0000001fH
; Line 19
sar ecx, 31 ; 0000001fH
and eax, 6
and ecx, 5
or eax, ecx
; Line 20
xor eax, 4
; Line 22
ret 0
?tricky@@YAHH@Z ENDP ; tricky
Y una prueba exhaustiva completa que también es razonablemente adecuada para la evaluación comparativa:
#include <limits.h>
int direct(int n)
{
int cr0;
if (n < 0)
cr0 = 1;
else if (n > 0)
cr0 = 2;
else
cr0 = 4;
return cr0;
}
const int shift_count = sizeof(int) * CHAR_BIT - 1;
int tricky(int n)
{
int cr0 = (-(n | n-1) >> shift_count) & 6;
cr0 |= (n >> shift_count) & 5;
cr0 ^= 4;
return cr0;
}
#include <iostream>
#include <iomanip>
int main(void)
{
int i = 0;
do {
if (direct(i) != tricky(i)) {
std::cerr << std::hex << i << std::endl;
return i;
}
} while (++i);
return 0;
}
La siguiente expresión es un poco críptica, pero no excesivamente, y parece ser algo que el compilador puede optimizar bastante fácilmente:
cr0 = 4 >> ((2 * (n < 0)) + (n > 0));
Esto es lo que GCC 4.6.1 para un objetivo x86 compila con -O2 :
xor ecx, ecx
mov eax, edx
sar eax, 31
and eax, 2
test edx, edx
setg cl
add ecx, eax
mov eax, 4
sar eax, cl
Y VC 2010 con /Ox parece bastante similar:
xor ecx, ecx
test eax, eax
sets cl
xor edx, edx
test eax, eax
setg dl
mov eax, 4
lea ecx, DWORD PTR [edx+ecx*2]
sar eax, cl
La versión que usa pruebas if se compila para el ensamblaje que usa saltos con cualquiera de estos compiladores. Por supuesto, nunca estarás realmente seguro de qué hará un compilador en particular con cualquier bit de código que elijas a menos que realmente examines el resultado. Mi expresión es lo suficientemente críptica como para decir que a menos que sea realmente un código de código crítico para el rendimiento, aún podría seguir con la versión de declaración if . Dado que necesita establecer el registro CR0 con frecuencia, creo que valdría la pena medir si esta expresión ayuda en absoluto.
Muchas respuestas que son aproximadamente "no hacer" ya, como de costumbre :) ¿Quieres el truco de bits? Lo conseguiras. Entonces siéntete libre de usarlo o no como mejor te parezca.
Puede usar esa asignación en -1, 0 y 1 ( sign ), y luego hacer esto:
return 7 & (0x241 >> ((sign(x) + 1) * 4));
Que es esencialmente usar una pequeña tabla de búsqueda.
O el "bithack ingenuo":
int y = ((x >> 31) & 1) | ((-x >> 31) & 2)
return (~(-y >> 31) & 4) | y;
La primera línea mapea x < 0 a 1, x > 0 a 2 x == 0 a 0. La segunda línea entonces mapea y == 0 a 4 e y != 0 a y.
Y, por supuesto, tiene un caso astuto para x = 0x80000000 que está mapeado a 3. Vaya. Bueno, arreglemos eso:
int y = ((x >> 31) & 1) | ((-x >> 31) & 2)
y &= 1 | ~(y << 1); // remove the 2 if odd
return (~(-y >> 31) & 4) | y;
Para un enfoque completamente no portátil, me pregunto si esto podría tener algún beneficio de velocidad:
void func(signed n, signed& cr0) {
cr0 = 1 << (!(unsigned(n)>>31)+(n==0));
}
mov ecx,eax ;with MSVC10, all optimizations except inlining on.
shr ecx,1Fh
not ecx
and ecx,1
xor edx,edx
test eax,eax
sete dl
mov eax,1
add ecx,edx
shl eax,cl
mov ecx,dword ptr [cr0]
mov dword ptr [ecx],eax
comparado con tu código en mi máquina:
test eax,eax ; if (n < 0)
jns func+0Bh (401B1Bh)
mov dword ptr [ecx],1 ; cr0 = 1;
ret ; cr0 = 2; else cr0 = 4; }
xor edx,edx ; else if (n > 0)
test eax,eax
setle dl
lea edx,[edx+edx+2]
mov dword ptr [ecx],edx ; cr0 = 2; else cr0 = 4; }
ret
No sé mucho sobre ensamblaje, así que no puedo decir con certeza si esto tendría algún beneficio (o incluso si el mío tiene saltos. De todos modos, no veo instrucciones que comiencen con j). Como siempre, (y como todos dijeron un millón de veces) PERFIL.
Dudo que esto sea más rápido que decir que Jalf o Ben, pero no vi ninguno que aprovechara el hecho de que en x86 todos los números negativos tienen un cierto bit establecido, y pensé que lanzaría uno.
[EDITAR] BenVoigt sugiere cr0 = 4 >> ((n != 0) + (unsigned(n) >> 31)); para eliminar la negación lógica, y mis pruebas muestran que es una gran mejora.
Primero, si esta variable debe actualizarse después de (casi) cada instrucción, el consejo obvio es este:
no lo hagas
Solo actualícelo cuando las instrucciones subsiguientes necesiten su valor. En cualquier otro momento, no tiene sentido actualizarlo.
Pero de todos modos, cuando lo actualizamos, lo que queremos es este comportamiento:
R < 0 => CR0 == 0b001
R > 0 => CR0 == 0b010
R == 0 => CR0 == 0b100
Idealmente, no necesitaremos ramificarnos en absoluto. Aquí hay un posible enfoque:
- Establezca CR0 en el valor
1. (si realmente desea velocidad, investigue si esto puede hacerse sin recuperar la constante de la memoria. Incluso si tiene que pasar un par de instrucciones, puede valer la pena) - Si R> = 0, el desplazamiento a la izquierda en un bit.
- Si R == 0, el desplazamiento a la izquierda en un bit
Donde los pasos 2 y 3 se pueden transformar para eliminar la parte "si"
CR0 <<= (R >= 0);
CR0 <<= (R == 0);
¿Es esto más rápido? No lo sé. Como siempre, cuando le preocupa el rendimiento, necesita medir, medir, medir.
Sin embargo, puedo ver un par de ventajas de este enfoque:
- evitamos ramas completamente
- evitamos cargas de memoria / tiendas.
- las instrucciones en las que confiamos (cambio de bits y comparación) deben tener una baja latencia, que no siempre es el caso para la multiplicación, por ejemplo.
La desventaja es que tenemos una cadena de dependencia entre las tres líneas: cada una modifica CR0, que luego se utiliza en la siguiente línea. Esto limita un poco el paralelismo a nivel de instrucción.
Para minimizar esta cadena de dependencia, podríamos hacer algo como esto en su lugar:
CR0 <<= ((R >= 0) + (R == 0));
entonces solo tenemos que modificar CR0 una vez, después de su inicialización.
O, haciendo todo en una sola línea:
CR0 = 1 << ((R >= 0) + (R == 0));
Por supuesto, hay muchas variaciones posibles de este tema, así que adelante y experimenta.
Si hay un método más rápido, el compilador probablemente ya lo está usando.
Mantenga su código corto y simple; eso hace que el optimizador sea más efectivo.
La solución simple y simple sorprende sorprendentemente a la velocidad:
cr0 = n? (n < 0)? 1: 2: 4;
Conjunto x86 (producido por VC ++ 2010, flags /Ox ):
PUBLIC ?tricky@@YAHH@Z ; tricky
; Function compile flags: /Ogtpy
_TEXT SEGMENT
_n$ = 8 ; size = 4
?tricky@@YAHH@Z PROC ; tricky
; Line 26
mov eax, DWORD PTR _n$[esp-4]
test eax, eax
je SHORT $LN3@tricky
xor ecx, ecx
test eax, eax
setns cl
lea eax, DWORD PTR [ecx+1]
; Line 31
ret 0
$LN3@tricky:
; Line 26
mov eax, 4
; Line 31
ret 0
?tricky@@YAHH@Z ENDP ; tricky
gcc sin optimización
movl %eax, 24(%esp) ; eax has result of reading n
cmpl $0, 24(%esp)
jns .L2
movl $1, 28(%esp)
jmp .L3
.L2:
cmpl $0, 24(%esp)
jle .L4
movl $2, 28(%esp)
jmp .L3
.L4:
movl $4, 28(%esp)
.L3:
Con -O2:
movl $1, %edx ; edx = 1
cmpl $0, %eax
jl .L2 ; n < 0
cmpl $1, %eax ; n < 1
sbbl %edx, %edx ; edx = 0 or -1
andl $2, %edx ; now 0 or 2
addl $2, %edx ; now 2 or 4
.L2:
movl %edx, 4(%esp)
No creo que sea probable que lo haga mucho mejor