Desbordamiento de desplazamiento a la izquierda de GCC

8 minutos de lectura

avatar de usuario
Lucas

El siguiente pequeño programa es muy incómodo al usar GCC versión 4.2.1 (Apple Inc. compilación 5664) en una Mac.

#include <stdio.h>

int main(){
        int x = 1 << 32;
        int y = 32;
        int z = 1 << y;
        printf("x:%d, z: %d\n", x, z);
}

El resultado es x:0, z: 1.

¿Alguna idea de por qué los valores de x y z son diferentes?

Muchas gracias.

  • ¿Estás compilando con -Wall?

    – Skurmedel

    6 de octubre de 2010 a las 10:47

  • gcc da: “advertencia: recuento de desplazamiento a la izquierda> = ancho de tipo” para el desplazamiento x

    – slashmais

    6 de octubre de 2010 a las 10:48

  • Supongo que el compilador calcula previamente el (1 << 32) expresión porque es una constante.

    – PP.

    6 oct 2010 a las 11:05

  • Finalmente encontré la respuesta. Esto se debe a que el procesador Intel enmascara el recuento de desplazamientos a 5 bits (es decir, toma la cantidad de desplazamiento y la OR bit a bit por 31).

    – PP.

    6 de octubre de 2010 a las 11:13

  • La causa más común de esto que veo es ((x << (32-S)) | (x >> S)), cuando S termina siendo 0. Tenga en cuenta que cualquier comportamiento produce los resultados deseados para este cálculo .

    – usuario3535668

    23 oct 2017 a las 15:53


avatar de usuario
PÁGINAS.

Respuesta corta: el procesador Intel enmascara el recuento de desplazamientos a 5 bits (máximo 31). En otras palabras, el cambio realmente realizado es 32 y 31, que es 0 (sin cambios).

El mismo resultado aparece usando gcc en una PC con Linux de 32 bits.

Reuní una versión más corta de este programa porque estaba desconcertado por qué un desplazamiento a la izquierda de 32 bits debería dar como resultado un valor distinto de cero:

int main(){
    int y = 32;
    unsigned int z = 1 << y;
    unsigned int k = 1;
    k <<= y;
    printf("z: %u, k: %u\n", z, k);
}

..usando el comando gcc -Wall -o a.s -S deleteme.c (los comentarios son míos)

main:
leal    4(%esp), %ecx
andl    $-16, %esp
pushl   -4(%ecx)
pushl   %ebp
movl    %esp, %ebp
pushl   %ecx
subl    $36, %esp
movl    $32, -16(%ebp)  ; y = 32
movl    -16(%ebp), %ecx ; 32 in CX register
movl    $1, %eax        ; AX = 1
sall    %cl, %eax       ; AX <<= 32(32)
movl    %eax, -12(%ebp) ; z = AX
movl    $1, -8(%ebp)    ; k = 1
movl    -16(%ebp), %ecx ; CX = y = 32
sall    %cl, -8(%ebp)   ; k <<= CX(32)
movl    -8(%ebp), %eax  ; AX = k
movl    %eax, 8(%esp)
movl    -12(%ebp), %eax
movl    %eax, 4(%esp)
movl    $.LC0, (%esp)
call    printf
addl    $36, %esp
popl    %ecx
popl    %ebp
leal    -4(%ecx), %esp
ret

Bien, ¿qué significa esto? Es esta instrucción la que me desconcierta:

sall    %cl, -8(%ebp)   ; k <<= CX(32)

Claramente k es siendo desplazado a la izquierda por 32 bits.

Me tienes – está usando el sall instrucción que es una cambio aritmético. No sé por qué girar esto 32 hace que el bit vuelva a aparecer en la posición inicial. Mi conjetura inicial sería que el procesador está optimizado para realizar esta instrucción en un ciclo de reloj, lo que significa que cualquier cambio de más de 31 se consideraría como indiferencia. Pero tengo curiosidad por encontrar la respuesta a esto porque esperaría que la rotación provoque que todos los bits caigan del extremo izquierdo del tipo de datos.

Encontré un enlace a http://faydoc.tripod.com/cpu/sal.htm lo que explica que el conteo de desplazamiento (en el registro CL) esté enmascarado a 5 bits. Esto significa que si intentara cambiar 32 bits, el cambio real realizado sería de cero bits (es decir, sin cambios). ¡Ahí está la respuesta!

  • Tiene razón en que se está utilizando la instrucción SALL; también lo noté y al consultar la Referencia del conjunto de instrucciones de Intel se revela esto: “Sin embargo, todos los demás procesadores IA-32 (comenzando con el procesador Intel 286) enmascaran el recuento de desplazamiento a 5 bits , lo que da como resultado un recuento máximo de 31”. Entonces, el valor de 32 se ignora: 1 es el argumento sin cambios, no rotado por 32.

    – andrewmu

    6 de octubre de 2010 a las 11:13


  • Debería ser (32 y 31) para enmascarar.

    – Tanveer Badar

    23 de junio de 2019 a las 12:52

  • El enlace faydoc está roto.

    – Federico

    14 de abril de 2020 a las 19:46

avatar de usuario
pmg

Si tu ints son de 32 bits o menos, el comportamiento no está definido… y comportamiento indefinido no puede ser explicado.

La Norma dice:

6.5.7/3 […] Si el valor del operando derecho es negativo o es mayor o igual que el ancho del operando izquierdo promocionado, el comportamiento no está definido.


Puedes comprobar tu int ancho tamaño de bit, por ejemplo con:

#include <limits.h>
#include <stdio.h>
int main(void) {
    printf("bits in an int: %d\n", CHAR_BIT * (int)sizeof (int));
    return 0;
}

Y puedes consultar tu int ancho (puede haber bits de relleno), por ejemplo con:

#include <limits.h>
#include <stdio.h>
int main(void) {
    int width = 0;
    int tmp = INT_MAX;
    while (tmp) {
        tmp >>= 1;
        width++;
    }
    printf("width of an int: %d\n", width + 1 /* for the sign bit */);
    return 0;
}

Estándar 6.2.6.2/2: Para los tipos enteros con signo, los bits de la representación del objeto se dividirán en tres grupos: bits de valor, bits de relleno y el bit de signo. No es necesario que haya partes de relleno; habrá exactamente un bit de signo

  • Sin ofender, pero eso realmente no responde la pregunta.

    – Simon Toth

    6 de octubre de 2010 a las 10:56

  • “La Norma sólo permite x << y Cuándo (y < sizeof x)“. Esta declaración es incorrecta de dos maneras: el estándar permite el cambio pero dice que el resultado no está definido. Para un compilador particular en una arquitectura particular, mayo dar resultados predecibles, pero no tiene que hacerlo. También la segunda parte debería ser y < widthInBitsOf(x)

    – JeremyP

    6 oct 2010 a las 11:00

  • @pmg Espero que no hables en serio. Comportamiento indefinido significa que el compilador puede hacer lo que quiera. Pero ciertamente no significa que no se pueda explicar o que no sea consistente.

    – Simon Toth

    6 oct 2010 a las 11:00

  • @Let_Me_Be: Su suposición no está definida.

    – leppie

    6 de octubre de 2010 a las 11:09

  • El comportamiento indefinido no se puede explicar. del estándar. No está más allá del ingenio humano investigar el comportamiento de un compilador y hardware en particular.

    –Steve Jessop

    6 oct 2010 a las 14:37

avatar de usuario
jeremyp

El estándar C99 dice que el resultado de cambiar un número por el ancho en bits (o más) del operando no está definido. ¿Por qué?

Bueno, esto permite a los compiladores crear el código más eficiente para una arquitectura en particular. Por ejemplo, la instrucción de desplazamiento i386 utiliza un campo de cinco bits de ancho para el número de bits por los que desplazar un operando de 32 bits. El estándar C99 permite que el compilador simplemente tome los cinco bits inferiores del conteo de turnos y los coloque en el campo. Claramente, esto significa que un desplazamiento de 32 bits (= 100000 en binario) es, por lo tanto, idéntico a un desplazamiento de 0 y, por lo tanto, el resultado será el operando izquierdo sin cambios.

Una arquitectura de CPU diferente podría usar un campo de bits más amplio, digamos 32 bits. El compilador aún puede colocar el recuento de desplazamientos directamente en el campo, pero esta vez el resultado será 0 porque un desplazamiento de 32 bits desplazará todos los bits del operando izquierdo.

Si el C99 definió uno u otro de estos comportamientos como correctos, el compilador de Intel tiene que hacer un control especial para los conteos de turnos que son demasiado grandes o el compilador para no i386 tiene que enmascarar el conteo de turnos.

La razón por la cual

   int x = 1 << 32;

y

   int z = 1 << y;

dan resultados diferentes es porque el primer cálculo es una expresión constante y el compilador puede realizarlo completamente. El compilador debe estar calculando expresiones constantes usando aritmética de 64 bits. La segunda expresión es calculada por el código generado por el compilador. Dado que el tipo de y y z es int el código genera un cálculo utilizando enteros de 32 bits de ancho (int es de 32 bits tanto en i386 como en x86_64 con gcc en Apple).

  • @DonHatch cuando dije “debe”, estaba especulando sobre el comportamiento exacto del compilador en este caso, no estaba diciendo “el estándar C exige aritmética de 64 bits”. El hecho de que (int)(1 << 32) es cero significa que la versión Intel de gcc definitivamente no está usando la versión de 32 bits del cambio para calcular el cambio, o si lo está, está haciendo una verificación para ver si el cambio es mayor que 31.

    – JeremyP

    26/09/2014 a las 13:30

  • Hola @JeremyP, gracias, eso tiene sentido, gracias por explicarlo. Hice una edición sugerida para cambiar “debe calcular” a “debe estar calculando”, lo que habría evitado mi malentendido. Eliminé mi comentario anterior y mi voto negativo. (en realidad, el voto negativo está bloqueado en este momento, pero creo que se desbloqueará si se acepta la edición)

    – Don Escotilla

    24/10/2014 a las 19:28


  • ¿Lo especuló usando aritmética de 64 bits para el cálculo constante porque el bit nunca se desbordó y, en cambio, probablemente siguió moviéndose más hacia abajo en un espacio de bits más grande (64 por ejemplo)? Supongo que podríamos probarlo con: int x = 1 << 64

    – Domingo Farolino

    4 de enero de 2018 a las 7:27

  • Realmente x = 1 << 64 y x = 0; x |= (1 << 64) no nos dirá nada porque empujaríamos el 1 fuera del extremo izquierdo de todos modos y no necesariamente se envolvería / se desbordaría a los bits inferiores

    – Domingo Farolino

    04/01/2018 a las 15:55

En mi mente “int x = y << 32;" no tiene sentido si sizeof(int)==4.

Pero tuve un problema similar con:

largo y = … largo x = y << 32;

Donde recibí una advertencia “advertencia: recuento de desplazamiento a la izquierda> = ancho de tipo” aunque el tamaño de (largo) era 8 en el objetivo en cuestión. Me deshice de la advertencia haciendo esto en su lugar:

largo x = (y << 16) << 16;

Y eso pareció funcionar.

En una arquitectura de 64 bits no hubo advertencia. En una arquitectura de 32 bits lo había.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad