¿Los operadores de desplazamiento (<<, >>) son aritméticos o lógicos en C?

Respuestas:

97

De acuerdo con la segunda edición de K&R, los resultados dependen de la implementación para los cambios correctos de los valores firmados.

Wikipedia dice que C / C ++ 'usualmente' implementa un cambio aritmético en valores con signo.

Básicamente necesita probar su compilador o no confiar en él. Mi ayuda VS2008 para el compilador actual de MS C ++ dice que su compilador hace un cambio aritmético.

Ronnie
fuente
141

Al desplazarse hacia la izquierda, no hay diferencia entre el cambio aritmético y el lógico. Cuando se desplaza hacia la derecha, el tipo de desplazamiento depende del tipo del valor que se está desplazando.

(Como fondo para aquellos lectores que no están familiarizados con la diferencia, un desplazamiento "lógico" a la derecha de 1 bit desplaza todos los bits a la derecha y llena el bit más a la izquierda con un 0. Un desplazamiento "aritmético" deja el valor original en el bit más a la izquierda La diferencia se vuelve importante cuando se trata de números negativos).

Al cambiar un valor sin signo, el operador >> en C es un cambio lógico. Al cambiar un valor con signo, el operador >> es un cambio aritmético.

Por ejemplo, suponiendo una máquina de 32 bits:

signed int x1 = 5;
assert((x1 >> 1) == 2);
signed int x2 = -5;
assert((x2 >> 1) == -3);
unsigned int x3 = (unsigned int)-5;
assert((x3 >> 1) == 0x7FFFFFFD);
Greg Hewgill
fuente
57
Muy cerca, Greg. Su explicación es casi perfecta, pero cambiar una expresión de tipo con signo y valor negativo está definida por la implementación. Ver ISO / IEC 9899: 1999 Sección 6.5.7.
Robᵩ
12
@Rob: En realidad, para el desplazamiento a la izquierda y el número negativo con signo, el comportamiento no está definido.
JeremyP
55
En realidad, el desplazamiento a la izquierda también da como resultado un comportamiento indefinido para valores con signo positivo si el valor matemático resultante (que no está limitado en tamaño de bits) no puede representarse como un valor positivo en ese tipo con signo. La conclusión es que debe pisar con cuidado al desplazar a la derecha un valor firmado.
Michael Burr
3
@supercat: Realmente no lo sé. Sin embargo, sé que hay casos documentados en los que el código que tiene un comportamiento indefinido hace que un compilador haga cosas muy poco intuitivas (generalmente debido a una optimización agresiva; por ejemplo, vea el viejo error de puntero nulo del controlador TUN / TAP de Linux: lwn.net / Artículos / 342330 ). A menos que necesite completar el signo en el desplazamiento a la derecha (lo que me doy cuenta es un comportamiento definido por la implementación), generalmente trato de realizar mis cambios de bit usando valores sin signo, incluso si eso significa usar conversiones para llegar allí.
Michael Burr
2
@MichaelBurr: Sé que los compiladores hipermodernos utilizan el hecho de que el comportamiento que no fue definido por el estándar C (aunque se había definido en el 99% de las implementaciones ) como una justificación para activar programas cuyo comportamiento se habría definido completamente en todos plataformas donde se podría esperar que se ejecuten, en grupos inútiles de instrucciones de máquina sin comportamiento útil. Sin embargo, lo admito (sarcasmo) Me sorprende por qué los autores del compilador han perdido la posibilidad de optimización más masiva: omita cualquier parte de un programa que, si se alcanza, daría lugar a funciones anidadas ...
supercat
51

TL; DR

Considere iy nser los operandos izquierdo y derecho respectivamente de un operador de turno; el tipo de i, después de la promoción de enteros, be T. Suponiendo nque esté en [0, sizeof(i) * CHAR_BIT)- indefinido de lo contrario - tenemos estos casos:

| Direction  |   Type   | Value (i) | Result                   |
| ---------- | -------- | --------- | ------------------------ |
| Right (>>) | unsigned |     0    | −∞  (i ÷ 2ⁿ)            |
| Right      | signed   |     0    | −∞  (i ÷ 2ⁿ)            |
| Right      | signed   |    < 0    | Implementation-defined  |
| Left  (<<) | unsigned |     0    | (i * 2ⁿ) % (T_MAX + 1)   |
| Left       | signed   |     0    | (i * 2ⁿ)                |
| Left       | signed   |    < 0    | Undefined                |

† la mayoría de los compiladores implementan esto como desplazamiento aritmético
‡ indefinido si el valor desborda el tipo de resultado T; tipo promocionado de i


Cambiando

Primero está la diferencia entre los cambios lógicos y aritméticos desde un punto de vista matemático, sin preocuparse por el tamaño del tipo de datos. Los desplazamientos lógicos siempre llenan los bits descartados con ceros, mientras que el desplazamiento aritmético lo rellena con ceros solo para el desplazamiento a la izquierda, pero para el desplazamiento a la derecha copia el MSB conservando así el signo del operando (suponiendo una codificación complementaria de dos para valores negativos).

En otras palabras, el cambio lógico considera el operando desplazado como una simple secuencia de bits y los mueve, sin preocuparse por el signo del valor resultante. El cambio aritmético lo ve como un número (con signo) y conserva el signo a medida que se realizan los cambios.

Un desplazamiento aritmético a la izquierda de un número X por n es equivalente a multiplicar X por 2 ny, por lo tanto, es equivalente al desplazamiento lógico a la izquierda; un cambio lógico también daría el mismo resultado ya que MSB de todos modos se cae al final y no hay nada que preservar.

Un desplazamiento aritmético a la derecha de un número X por n es equivalente a la división entera de X por 2 n ¡ SOLO si X no es negativo! La división entera no es más que división matemática y redondeada hacia 0 ( trunc ).

Para los números negativos, representados por la codificación del complemento a dos, desplazar a la derecha por n bits tiene el efecto de dividirlo matemáticamente por 2 n y redondear hacia −∞ ( piso ); así, el desplazamiento a la derecha es diferente para valores no negativos y negativos.

para X ≥ 0, X >> n = X / 2 n = trunc (X ÷ 2 n )

para X <0, X >> n = piso (X ÷ 2 n )

donde ÷es la división matemática, /es la división entera. Veamos un ejemplo:

37) 10 = 100101) 2

37 ÷ 2 = 18,5

37/2 = 18 (redondeando 18.5 hacia 0) = 10010) 2 [resultado del desplazamiento aritmético a la derecha]

-37) 10 = 11011011) 2 (considerando un complemento a dos, representación de 8 bits)

-37 ÷ 2 = -18,5

-37 / 2 = -18 (redondeando 18.5 hacia 0) = 11101110) 2 [NO es el resultado del desplazamiento aritmético a la derecha]

-37 >> 1 = -19 (redondeando 18.5 hacia −∞) = 11101101) 2 [resultado del desplazamiento aritmético a la derecha]

Como señaló Guy Steele , esta discrepancia ha provocado errores en más de un compilador . Aquí no negativo (matemático) puede asignarse a valores no negativos firmados y no firmados (C); ambos se tratan de la misma manera y el desplazamiento a la derecha se realiza por división entera.

Entonces, la lógica y la aritmética son equivalentes en el desplazamiento a la izquierda y para valores no negativos en el desplazamiento a la derecha; es el desplazamiento correcto de los valores negativos que difieren.

Tipos de operandos y resultados

Norma C99 §6.5.7 :

Cada uno de los operandos tendrá tipos enteros.

Las promociones enteras se realizan en cada uno de los operandos. El tipo de resultado es el del operando izquierdo promovido. Si el valor del operando derecho es negativo o es mayor o igual que el ancho del operando izquierdo promovido, el comportamiento es indefinido.

short E1 = 1, E2 = 3;
int R = E1 << E2;

En el fragmento anterior, ambos operandos se vuelven int(debido a la promoción de enteros); si E2fue negativo o E2 ≥ sizeof(int) * CHAR_BITla operación no está definida. Esto se debe a que desplazar más de los bits disponibles seguramente se desbordará. Si se Rhubiera declarado como short, el intresultado de la operación de cambio se convertiría implícitamente en short; una conversión de reducción, que puede conducir a un comportamiento definido por la implementación si el valor no es representable en el tipo de destino.

Shift izquierdo

El resultado de E1 << E2 es E1 posiciones de bit E2 desplazadas a la izquierda; los bits desocupados se llenan de ceros. Si E1 tiene un tipo sin signo, el valor del resultado es E1 × 2 E2 , módulo reducido uno más que el valor máximo representable en el tipo de resultado. Si E1 tiene un tipo con signo y un valor no negativo, y E1 × 2 E2 es representable en el tipo de resultado, entonces ese es el valor resultante; de lo contrario, el comportamiento es indefinido.

Como los desplazamientos a la izquierda son iguales para ambos, los bits vacíos simplemente se rellenan con ceros. Luego establece que tanto para los tipos sin signo como con signo es un cambio aritmético. Lo estoy interpretando como un cambio aritmético ya que los cambios lógicos no se preocupan por el valor representado por los bits, solo lo ven como una corriente de bits; pero el estándar no habla en términos de bits, sino definiéndolo en términos del valor obtenido por el producto de E1 con 2 E2 .

La advertencia aquí es que para los tipos con signo el valor no debe ser negativo y el valor resultante debe ser representable en el tipo de resultado. De lo contrario, la operación no está definida. El tipo de resultado sería el tipo de E1 después de aplicar la promoción integral y no el tipo de destino (la variable que va a contener el resultado). El valor resultante se convierte implícitamente al tipo de destino; si no es representable en ese tipo, entonces la conversión está definida por la implementación (C99 §6.3.1.3 / 3).

Si E1 es un tipo con signo con un valor negativo, el comportamiento del desplazamiento a la izquierda no está definido. Esta es una ruta fácil hacia un comportamiento indefinido que puede pasarse por alto fácilmente.

Giro a la derecha

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 / 2 E2 . Si E1 tiene un tipo con signo y un valor negativo, el valor resultante está definido por la implementación.

El desplazamiento a la derecha para valores no negativos sin signo y con signo es bastante sencillo; los bits vacantes están llenos de ceros. Para valores negativos con signo, el resultado del desplazamiento a la derecha está definido por la implementación. Dicho esto, la mayoría de las implementaciones como GCC y Visual C ++ implementan el desplazamiento a la derecha como desplazamiento aritmético conservando el bit de signo.

Conclusión

A diferencia de Java, que tiene un operador especial >>>para el desplazamiento lógico aparte del habitual >>y <<, C y C ++ solo tienen desplazamiento aritmético con algunas áreas que quedan sin definir y definidas por la implementación. La razón por la que los considero aritméticos se debe a la redacción estándar de la operación matemáticamente en lugar de tratar el operando desplazado como una corriente de bits; Esta es quizás la razón por la que deja esas áreas sin definir / implementación en lugar de simplemente definir todos los casos como cambios lógicos.

legends2k
fuente
1
Buena respuesta. Con respecto al redondeo (en la sección titulada Desplazamiento ): el desplazamiento a la derecha se redondea hacia -Inflos números negativos y positivos. El redondeo hacia 0 de un número positivo es un caso privado de redondeo hacia -Inf. Al truncar, siempre sueltas valores ponderados positivamente, por lo tanto, restas del resultado preciso.
ysap
1
@ysap Sí, buena observación. Básicamente, redondear hacia 0 para números positivos es un caso especial de la ronda más general hacia −∞; Esto se puede ver en la tabla, donde los números positivos y negativos lo noté como redondo hacia −∞.
legends2k
17

En términos del tipo de cambio que obtienes, lo importante es el tipo de valor que estás cambiando. Una fuente clásica de errores es cuando cambia un literal a, digamos, enmascarar bits. Por ejemplo, si quisieras soltar el bit más a la izquierda de un entero sin signo, entonces puedes probar esto como tu máscara:

~0 >> 1

Desafortunadamente, esto te meterá en problemas porque la máscara tendrá todos sus bits establecidos porque el valor que se está desplazando (~ 0) está firmado, por lo que se realiza un cambio aritmético. En cambio, querría forzar un cambio lógico declarando explícitamente el valor como sin signo, es decir, haciendo algo como esto:

~0U >> 1;
Mella
fuente
16

Aquí hay funciones para garantizar el desplazamiento lógico a la derecha y el desplazamiento aritmético a la derecha de un int en C:

int logicalRightShift(int x, int n) {
    return (unsigned)x >> n;
}
int arithmeticRightShift(int x, int n) {
    if (x < 0 && n > 0)
        return x >> n | ~(~0U >> n);
    else
        return x >> n;
}
John Scipione
fuente
7

Cuando lo haces - desplazamiento a la izquierda por 1 multiplicas por 2 - desplazamiento a la derecha por 1 divides por 2

 x = 5
 x >> 1
 x = 2 ( x=5/2)

 x = 5
 x << 1
 x = 10 (x=5*2)
Srikant Patnaik
fuente
En x >> a y x << a si la condición es a> 0, entonces la respuesta es x = x / 2 ^ a, x = x * 2 ^ a respectivamente, entonces ¿Cuál sería la respuesta si a <0?
JAVA
@sunny: a no debe ser menor que 0. Es un comportamiento indefinido en C.
Jeremy
4

Bueno, lo busqué en wikipedia , y tienen esto que decir:

C, sin embargo, solo tiene un operador de desplazamiento a la derecha, >>. Muchos compiladores de C eligen qué desplazamiento correcto realizar según el tipo de número entero que se está desplazando; a menudo, los enteros con signo se desplazan utilizando el desplazamiento aritmético, y los enteros sin signo se desplazan mediante el desplazamiento lógico.

Parece que depende de tu compilador. También en ese artículo, tenga en cuenta que el desplazamiento a la izquierda es lo mismo para la aritmética y la lógica. Recomendaría hacer una prueba simple con algunos números con signo y sin signo en el caso del borde (conjunto de bits altos, por supuesto) y ver cuál es el resultado en su compilador. También recomendaría evitar depender de que sea uno u otro, ya que parece que C no tiene un estándar, al menos si es razonable y posible evitar dicha dependencia.

Mike Stone
fuente
Aunque la mayoría de los compiladores de C solían tener un desplazamiento aritmético a la izquierda para los valores con signo, este comportamiento útil parece haber quedado en desuso. La filosofía actual del compilador parece suponer que el rendimiento de un desplazamiento a la izquierda en una variable le da derecho a un compilador a asumir que la variable debe ser no negativa y, por lo tanto, omitir cualquier código en otro lugar que sería necesario para un comportamiento correcto si la variable fuera negativa .
supercat
0

Shift izquierdo <<

Esto es de alguna manera fácil y cada vez que usa el operador de cambio, siempre es una operación de bits, por lo que no podemos usarlo con una operación doble y flotante. Cada vez que dejamos Shift One Zero, siempre se agrega al bit menos significativo ( LSB).

Pero en el desplazamiento a la derecha >>tenemos que seguir una regla adicional y esa regla se llama "copia de bit de signo". El significado de "copia de bit de signo" es si el bit más significativo ( MSB) se establece, luego, después de un desplazamiento a la derecha nuevamente MSB, se establecerá si se restableció y luego se restablece nuevamente, significa que si el valor anterior era cero, luego de cambiar nuevamente, el el bit es cero si el bit anterior era uno y luego del cambio vuelve a ser uno. Esta regla no es aplicable para un desplazamiento a la izquierda.

El ejemplo más importante sobre el desplazamiento a la derecha si cambia cualquier número negativo al desplazamiento a la derecha, luego, después de algunos cambios, el valor finalmente llega a cero y luego después de esto si cambia a -1 cualquier cantidad de veces el valor seguirá siendo el mismo. Por favor, compruebe.

asifaftab87
fuente
0

normalmente usará cambios lógicos en variables sin signo y para cambios a la izquierda en variables con signo. El desplazamiento aritmético a la derecha es el verdaderamente importante porque firmará extender la variable.

lo usará cuando corresponda, como es probable que hagan otros compiladores.

Cristián Romo
fuente
-1

GCC hace

  1. para -ve -> Desplazamiento aritmético

  2. Para + ve -> Cambio lógico

Alok Prasad
fuente
-7

Según muchos compiladores:

  1. << es un desplazamiento aritmético a la izquierda o desplazamiento a la izquierda bit a bit.
  2. >> es un desplazamiento aritmético a la derecha con desplazamiento a la derecha.
srinath
fuente
3
"Desplazamiento aritmético a la derecha" y "desplazamiento a la derecha en modo bit" son diferentes. Ese es el punto de la pregunta. La pregunta formulada, "¿Es >>aritmética o bit a bit (lógica)?" Respondiste " >>es aritmética o bit a bit". Eso no responde la pregunta.
wchargin
No, <<y los >>operadores son lógicos, no aritméticos
shjeff