manejo - operadores de bits en c

¿Por qué(int)((unsigned int)((int) v)?

Question

El sitio web en el que encontré este código.

int v, sign;
// or, to avoid branching on CPUs with flag registers (IA32):
sign = -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));  // if v < 0 then -1, else 0. 

Esta declaración asigna un signo variable con el signo de la variable v (-1 o 0). Me pregunto por qué se usa (int)((unsigned int)((int)v) lugar de una v simple).

Answer 1

Citando el estándar C 6.5.7p5:

El resultado de E1 >> E2 es E1 posiciones de bit E2 desplazadas a la derecha. Si E1 tiene un tipo sin signo o si E1 tiene un tipo con signo y un valor no negativo, el valor del resultado es la parte integral del cociente de E1 / 2E2. Si E1 tiene un tipo firmado y un valor negativo, el valor resultante se define por la implementación.

El autor está escribiendo sobre cómo implementar un sign(int v) función sign(int v) que devuelve -1 para números negativos y 0 para 0 y números positivos de manera eficiente. Un enfoque ingenuo es este:

int sign(int v) {
    if (v < 0)
        return -1;
    else
        return 0;
}

Pero esta solución puede compilarse al código que realiza una comparación y se ramifica en los indicadores de CPU establecidos por la comparación. Esto es ineficiente. Propone una solución más sencilla y directa:

sign = -(v > 0);

Pero este cálculo aún requiere comparación y ramificación en CPU que no producen resultados de comparación directamente como valores booleanos. Las CPU con registros de indicadores suelen establecer varios indicadores en las instrucciones de comparación o incluso en la mayoría de las instrucciones aritméticas. Por lo tanto, propone otra solución basada en desplazar el bit de signo, pero como el Estándar especifica más arriba, no puede confiar en el resultado de cambiar a la derecha un valor negativo.

La conversión de v como unsigned elimina este problema porque los valores de unsigned que se desplazan a la derecha están bien especificados. Suponiendo que el bit de signo está en la posición más alta, lo cual es cierto para todos los procesadores modernos, pero no está exigido por el estándar C, el desplazamiento a la derecha (unsigned)v por uno menos que el número de bits en su tipo produce un valor de 1 para negativo valores y 0 caso contrario. Negar el resultado debe producir los valores esperados -1 para v negativo y 0 para positivo y cero v . Pero la expresión no está firmada, por lo que la negación simple producirá UINT_MAX o 0 , lo que a su vez provoca un desbordamiento aritmético cuando se almacena en un int o simplemente se convierte como un (int) . Devolver este resultado a int antes de negarlo correctamente calcula el resultado deseado, -1 para v negativo y 0 para v positivo o cero.

El desbordamiento aritmético generalmente es benigno y es ampliamente ignorado por la mayoría de los programadores, pero los compiladores modernos tienden a aprovechar su indefinición para realizar optimizaciones agresivas, por lo que no es prudente confiar en el comportamiento esperado pero no justificado y es mejor evitar el desbordamiento aritmético en todos los casos.

La expresión podría simplificarse como:

sign = -(int)((unsigned)v >> (sizeof(int) * CHAR_BIT - 1));

Tenga en cuenta que si el desplazamiento a la derecha se define como replicar el bit para su plataforma (un comportamiento casi universal con las CPU actuales), la expresión sería mucho más simple (suponiendo que int v ):

sign = v >> (sizeof(v) * CHAR_BIT - 1));   // works on x86 CPUs

La página de bithacks https://graphics.stanford.edu/~seander/bithacks.html , de hecho, muy instructiva, contiene una explicación detallada:

int v;      // we want to find the sign of v
int sign;   // the result goes here 

// CHAR_BIT is the number of bits per byte (normally 8).
sign = -(v < 0);  // if v < 0 then -1, else 0. 
// or, to avoid branching on CPUs with flag registers (IA32):
sign = -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));
// or, for one less instruction (but not portable):
sign = v >> (sizeof(int) * CHAR_BIT - 1); 

La última expresión anterior se evalúa como sign = v >> 31 para enteros de 32 bits. Esta es una operación más rápida que la forma obvia, signo = - (v <0). Este truco funciona porque cuando los enteros con signo se desplazan a la derecha, el valor del bit del extremo izquierdo se copia a los otros bits. El bit del extremo izquierdo es 1 cuando el valor es negativo y 0 en caso contrario; todos los 1 bits da -1. Desafortunadamente, este comportamiento es específico de la arquitectura.

Como epílogo, recomendaría usar la versión más legible y confiar en el compilador para producir el código más eficiente:

sign = -(v < 0);

Como se puede verificar en esta página ilustrativa: http://gcc.godbolt.org/# compilando el código anterior con gcc -O3 -std=c99 -m64 produce el código siguiente para todas las soluciones anteriores, incluso las más ingenuas if / else declaración:

sign(int):
    movl    %edi, %eax
    sarl    $31, %eax
    ret

Answer 2

Primero se lanza a int , luego a unsigned int , luego se realiza el cambio, luego se devuelve a int y finalmente se niega el resultado y se almacena en sign . La conversión no firmada es la que podría afectar el resultado, ya que forzará un cambio lógico (que llenará a cero), a diferencia de un cambio aritmético (que significará extensión).

Tenga en cuenta que en realidad quieren un cambio aritmético, pero no creo que C garantice su disponibilidad, lo que presumiblemente es la razón por la que están realizando manualmente la negación del bit de signo cambiado lógicamente.

Answer 3

Tenga en cuenta que ha extraído un fragmento de la expresión en su pregunta (usted cita (int)((unsigned int)((int)v) que tiene un corchete izquierdo más que el corchete derecho ) ). La expresión RHS de La declaración de asignación es, en su totalidad:

-(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));

Si agrega algunos espacios, encontrará:

-(int) (  (unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1)  );
       ^  ^            ^^      ^    ^                          ^  ^
       |  +------------++------+    +--------------------------+  |
       +----------------------------------------------------------+

Es decir, el elenco externo (int) aplica a todos:

((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));

El elenco interno a (int) emitido es vacuo; su resultado se convierte inmediatamente a unsigned int . La (unsigned int) garantiza que el cambio correcto esté bien definido. La expresión en su conjunto determina si el bit más significativo es un 0 o un 1. El int externo convierte el resultado nuevamente en un int , y el - luego lo niega, por lo que la expresión es -1 si v es negativo y 0 si v es cero o positivo, que es lo que dice el comentario.