Resultado inesperado de los operadores de desplazamiento bit a bit de C/C++

7 minutos de lectura

avatar de usuario
valdo

Creo que me estoy volviendo loco con esto.

Tengo un fragmento de código que necesita crear un número entero (sin firmar) con N los bits consiguientes se establecen en 1. Para ser exactos, tengo una máscara de bits y, en algunas situaciones, me gustaría configurarla en un rango sólido.

tengo la siguiente función:

void MaskAddRange(UINT& mask, UINT first, UINT count)
{
    mask |= ((1 << count) - 1) << first;
}

En palabras simples: 1 << count en representación binaria es 100...000 (el número de ceros es count), restando 1 de tal número da 011...111y luego simplemente lo desplazamos a la izquierda first.

Lo anterior debería dar el resultado correcto, cuando se cumple la siguiente limitación obvia:

first + count <= sizeof(UINT)*8 = 32

Nota que eso deberían también funcionan correctamente para casos “extremos”.

  • si count = 0 tenemos (1 << count) = 1y por lo tanto ((1 << count) - 1) = 0.
  • si count = 32 tenemos (1 << count) = 0ya que el bit inicial se desborda y, de acuerdo con las reglas de C/C++, los operadores de desplazamiento bit a bit son no cíclico. Luego ((1 << count) - 1) = -1 (todos los bits establecidos).

Sin embargo, como resultó, por count = 32 la fórmula no funciona como se esperaba. Como se descubrió:

UINT n = 32;
UINT x = 1 << n;
// the value of x is 1

Además, estoy usando MSVC2005 IDE. Cuando evalúo la expresión anterior en el depurador, el resultado es 0. Sin embargo, cuando paso por encima de la línea anterior, x obtiene el valor de 1. Mirando a través del desensamblador, vemos lo siguiente:

mov eax,1 
mov ecx,dword ptr [ebp-0Ch] // ecx = n
shl eax,cl                  // eax <<= LOBYTE(ecx)
mov dword ptr [ebp-18h],eax // n = ecx

De hecho, no hay magia, el compilador acaba de usarse shl instrucción. Entonces parece que shl no hace lo que esperaba que debería hacer. O la CPU decide ignorar esta instrucción, o el cambio se trata como módulo 32, o no sé qué.

Mis preguntas son:

  • ¿Cuál es el comportamiento correcto de shl/shr ¿instrucciones?
  • ¿Hay un indicador de CPU que controle las instrucciones de cambio de bits?
  • ¿Es esto de acuerdo con el estándar C/C++?

Gracias por adelantado

Editar:

Gracias por las respuestas. me he dado cuenta de que (1) shl/shr de hecho, trate el módulo 32 del operando (o & 0x1F) y (2) el estándar C/C++ trata el cambio en más de 31 bits como un comportamiento indefinido.

Entonces tengo una pregunta más. ¿Cómo puedo reescribir mi expresión de “enmascaramiento” para cubrir también este caso extremo? Debe ser sin ramificación (if, ?). ¿Cuál sería la expresión más simple?

  • No existe un lenguaje como “C/C++”. Etiquetó la pregunta como C, pero uno de sus fragmentos de código usa la notación UINT& maskque solo existe en C++.

    – ruakh

    25 de marzo de 2012 a las 13:37

  • Dos cosas me vienen a la mente: cuál es el tamaño de (UINT) y asegúrese de que 1 también sea UINT cuando lo muestre.

    – Mario La Cuchara

    25 de marzo de 2012 a las 13:40

  • Por cierto, para responder a su última pregunta: “¿Es esto de acuerdo con el estándar C/C++?”: el estándar C dice: “Si el valor del operando derecho es negativo o es mayor o igual que el ancho del operando izquierdo promocionado operando, el comportamiento no está definido”, y el estándar de C++ dice: El comportamiento no está definido si el operando derecho es negativo, o mayor o igual que la longitud en bits del operando izquierdo promovido”. Entonces, en cualquier idioma, el sistema puede haga absolutamente lo que quiera cuando haga esto; puede terminar el programa o enviar correos electrónicos enojados a su jefe. cualquier cosa.

    – ruakh

    25 de marzo de 2012 a las 13:42

  • Relacionados.

    – usuario202729

    26 de marzo de 2018 a las 6:13


avatar de usuario
ouah

1U << 32 es un comportamiento indefinido en C y en C++ cuando se escribe unsigned int es de 32 bits de ancho.

(C11, 6.5.7p3) “Si el valor del operando derecho es negativo o es mayor o igual que el ancho del operando izquierdo promovido, el comportamiento es indefinido”

(C++11, 5.8p1) “El comportamiento no está definido si el operando derecho es negativo, o mayor o igual que la longitud en bits del operando izquierdo promovido”.

Cambiar tantos o más bits que en el tipo de entero que está cambiando es indefinido en C y C++. En x86 y x86_64, la cantidad de desplazamiento de las instrucciones de desplazamiento se trata de hecho como módulo 32 (o cualquiera que sea el tamaño del operando). tu sin embargo no poder confíe en que el compilador generará este comportamiento de módulo desde C o C++ >>/<< operaciones a menos que su compilador lo garantice explícitamente en su documentación.

avatar de usuario
M. Shiina

Creo que la expresión 1 << 32 es lo mismo que 1 << 0. La referencia del conjunto de instrucciones IA-32 dice que el operando de conteo de las instrucciones de cambio está enmascarado a 5 bits.

La referencia del conjunto de instrucciones de las arquitecturas IA-32 se puede encontrar aquí.

Para arreglar el caso “extremo”, solo puedo encontrar el siguiente código (quizás con errores) que puede ser un poco incómodo:

void MaskAddRange(UINT *mask, UINT first, UINT count) {
    int count2 = ((count & 0x20) >> 5);
    int count1 = count - count2;
    *mask |= (((1 << count1) << count2) - 1) << first;
}

La idea básica es dividir la operación de turno para que cada cuenta de turno no exceda 31. Aparentemente, el código anterior asume que la cuenta está en un rango de 0 a 32, por lo que no es muy robusto.

avatar de usuario
gbulmer

Si he entendido los requisitos, ¿quieres un int sin firmar, con los N bits superiores establecidos?

Hay varias formas de obtener el resultado (creo) que desea. Editar: me preocupa que esto no sea muy robusto y falle para n> 32:

uint32_t set_top_n(uint32 n)
{
    static uint32_t value[33] = { ~0xFFFFFFFF, ~0x7FFFFFFF, ~0x3FFFFFFF, ~0x1FFFFFFF,
                                  ~0x0FFFFFFF, ~0x07FFFFFF, ~0x03FFFFFF, ~0x01FFFFFF,
                                  ~0x00FFFFFF, ~0x007FFFFF, ~0x003FFFFF, ~0x001FFFFF,
                                  // you get the idea
                                  0xFFFFFFFF
                                  };
    return value[n & 0x3f];
}

Esto debería ser bastante rápido ya que solo tiene 132 bytes de datos.

Para hacerlo robusto, extendería todos los valores hasta 63 o lo haría condicional, en cuyo caso se puede hacer con una versión de su enmascaramiento de bits original + el caso 32. Es decir

avatar de usuario
Morfismo

Mis 32 centavos:

#include <limits.h>

#define INT_BIT     (CHAR_BIT * sizeof(int))

unsigned int set_bit_range(unsigned int n, int frm, int cnt)
{
        return n | ((~0u >> (INT_BIT - cnt)) << frm);
}

Lista 1.

Una versión segura con resultado falso/semicircular podría ser:

unsigned int set_bit_range(unsigned int n, int f, int c)
{
        return n | (~0u >> (c > INT_BIT ? 0 : INT_BIT - c)) << (f % INT_BIT);
}

Lista 2.

Hacer esto sin bifurcaciones o variables locales podría ser algo como;

return n | (~0u >> ((INT_BIT - c) % INT_BIT)) << (f % INT_BIT);

Lista 3.

Lista 2 y Lista 3 Esto daría un resultado “correcto” siempre que from es menos entonces INT_BIT y >= 0. Es decir:

./bs 1761 26 810
Setting bits from 26 count 810 in 1761 -- of 32 bits
Trying to set bits out of range, set bits from 26 to 836 in 32 sized range
x = ~0u       =  1111 1111 1111 1111 1111 1111 1111 1111

Unsafe version:
x = x >> -778 =  0000 0000 0000 0000 0000 0011 1111 1111
x = x <<  26  =  1111 1100 0000 0000 0000 0000 0000 0000
x v1 Result   =  1111 1100 0000 0000 0000 0110 1110 0001
Original:        0000 0000 0000 0000 0000 0110 1110 0001    

Safe version, branching:
x = x >>   0  =  1111 1111 1111 1111 1111 1111 1111 1111
x = x <<  26  =  1111 1100 0000 0000 0000 0000 0000 0000
x v2 Result   =  1111 1100 0000 0000 0000 0110 1110 0001
Original:        0000 0000 0000 0000 0000 0110 1110 0001    

Safe version, modulo:
x = x >>  22  =  0000 0000 0000 0000 0000 0011 1111 1111
x = x <<  26  =  1111 1100 0000 0000 0000 0000 0000 0000
x v3 Result   =  1111 1100 0000 0000 0000 0110 1110 0001
Original:        0000 0000 0000 0000 0000 0110 1110 0001

avatar de usuario
relojero

Puede evitar el comportamiento indefinido dividiendo la operación de cambio en dos pasos, el primero por (cuenta – 1) bits y el segundo por 1 bit más. Se necesita cuidado especial en caso de que el recuento de casos sea cero, sin embargo:

void MaskAddRange(UINT& mask, UINT first, UINT count)
{
  if (count == 0) return;
  mask |= ((1 << (count - 1) << 1) - 1) << first;
}

¿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