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

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

Según 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 ++ ‘generalmente’ implementa un cambio aritmético en los valores firmados.

Básicamente, necesitas probar tu comstackdor o no confiar en él. Mi ayuda VS2008 para el comstackdor MS C ++ actual dice que su comstackdor realiza un cambio aritmético.

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

(Como fondo para los lectores que no están familiarizados con la diferencia, un desplazamiento “lógico” a la derecha en 1 bit desplaza todos los bits a la derecha y rellena el bit más a la izquierda con 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 firmado, el operador >> es un desplazamiento 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); 

TL; DR

Considere que i y n son los operandos izquierdo y derecho, respectivamente, de un operador de turno; el tipo de i , después de la promoción entera, sea T Suponiendo que n está en [0, sizeof(i) * CHAR_BIT) – no definido de otra manera – 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 comstackdores implementan esto como un cambio aritmético
‡ indefinido si el valor rebasa 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 llena de ceros solo para el desplazamiento a la izquierda, pero para el desplazamiento a la derecha copia el MSB preservando así el signo del operando (suponiendo una encoding complementaria de dos para valores negativos).

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

Un desplazamiento aritmético izquierdo de un número X por n es equivalente a multiplicar X por 2 n y, por lo tanto, equivale al desplazamiento lógico a la izquierda; un cambio lógico también daría el mismo resultado ya que MSB cae de todos modos 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 SÓLO si X no es negativo. La división entera no es más que división matemática y redonda hacia 0 ( trunc ).

Para los números negativos, representados por la encoding del complemento de dos, el desplazamiento por n bits tiene el efecto de dividir matemáticamente por 2 n y redondear hacia -∞ ( piso ); por lo tanto, el desplazamiento a la derecha es diferente para los 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 división matemática, / es 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 de 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 cambio de aritmética 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 dado lugar a errores en más de un comstackdor . Aquí, no negativas (matemáticas) se pueden asignar a valores no negativos firmados y no firmados (C); ambos son tratados de la misma manera y su 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 los valores no negativos en el desplazamiento a la derecha; está en el desplazamiento correcto de los valores negativos que difieren.

Operando y Tipos de resultados

Estándar C99 §6.5.7 :

Cada uno de los operandos debe tener 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 no está definido.

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

En el fragmento de arriba, ambos operandos se convierten en int (debido a la promoción entera); si E2 fue negativo o E2 ≥ sizeof(int) * CHAR_BIT , la operación no está definida. Esto se debe a que el desplazamiento de más de los bits disponibles seguramente se desbordará. Si R hubiera declarado short , el resultado int de la operación de cambio se convertiría implícitamente en short ; una conversión de estrechamiento, 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 vacíos se rellenan con 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 firmado 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 no está definido.

Como los cambios a la izquierda son los mismos para ambos, los bits vacíos simplemente se rellenan con ceros. A continuación, indica que, para los tipos sin signo y firmado, es un cambio aritmético. Lo interpreto como un desplazamiento aritmético, ya que los cambios lógicos no se preocupan por el valor representado por los bits, simplemente lo ve como una secuencia de bits; pero el estándar no habla en términos de bits, sino que lo define 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 debe ser no 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 firmado con un valor negativo, entonces el comportamiento del desplazamiento a la izquierda no está definido. Esta es una ruta fácil hacia un comportamiento indefinido que fácilmente puede pasarse por alto.

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 firmado y un valor no negativo, el valor del resultado es la parte integral del cociente de E1 / 2 E2 . Si E1 tiene un tipo firmado y un valor negativo, el valor resultante está definido por la implementación.

El desplazamiento a la derecha para valores no negativos firmados y no firmados es bastante directo; los bits vacantes están llenos de ceros. Para los valores negativos firmados, 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 al preservar el bit de signo.

Conclusión

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

En términos del tipo de cambio que obtienes, lo importante es el tipo del valor que estás cambiando. Una fuente clásica de errores es cuando cambias un literal a, por ejemplo, máscara de bits. Por ejemplo, si quieres soltar el bit más a la izquierda de un entero sin signo, 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 tanto se realiza un cambio aritmético. En su lugar, querría forzar un cambio lógico declarando explícitamente el valor como no firmado, es decir, haciendo algo como esto:

 ~0U >> 1; 

Aquí hay funciones para garantizar el desplazamiento lógico a la derecha y el desplazamiento a la derecha aritmético 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; } 

Cuando lo haces: el desplazamiento a la izquierda en 1 multiplicas por 2, el desplazamiento a la derecha en 1 lo divides por 2

  x = 5 x >> 1 x = 2 ( x=5/2) x = 5 x << 1 x = 10 (x=5*2) 

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

C, sin embargo, tiene solo un operador de desplazamiento a la derecha, >>. Muchos comstackdores de C eligen el cambio a la derecha para realizar dependiendo del tipo de entero que se está desplazando; los enteros a menudo firmados se desplazan usando el desplazamiento aritmético, y los enteros sin signo se desplazan usando el desplazamiento lógico.

Entonces parece que depende de tu comstackdor. También en ese artículo, tenga en cuenta que el desplazamiento a la izquierda es el mismo para la aritmética y lógica. Recomendaría hacer una prueba simple con algunos números firmados y sin firmar en el caso de borde (por ejemplo, alto bit) y ver cuál es el resultado en tu comstackdor. También recomendaría evitar dependiendo de si es uno u otro, ya que parece que C no tiene un estándar, al menos si es razonable y posible evitar tal dependencia.

Cambio a la izquierda <<

Esto es de alguna manera fácil y cada vez que utiliza el operador de desplazamiento, siempre es una operación poco inteligente, por lo que no podemos usarlo con una operación doble y flotante. Cada vez que salimos, cambie un cero, 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 "signo de copia de bit" es si el bit más significativo ( MSB ) se establece y después de un cambio a la derecha nuevamente el MSB se configurará si se reinició y luego se reinicia, significa que el valor anterior era cero y después de cambiar de nuevo , el bit es cero si el bit anterior fue uno y después del cambio vuelve a ser uno. Esta regla no es aplicable para un turno de la izquierda.

El ejemplo más importante del desplazamiento a la derecha si cambias un número negativo al desplazamiento a la derecha, luego, después de algún cambio del valor, finalmente llega a cero y después de esto si cambias esto -1 cualquier cantidad de veces, el valor permanecerá igual. Por favor, compruebe.

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

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

GCC sí

  1. for -ve -> Cambio aritmético

  2. Para + ve -> Cambio lógico

De acuerdo con muchos comstackdores c :

  1. << es un desplazamiento aritmético a la izquierda o un desplazamiento a la izquierda bit a bit.
  2. >> es un desplazamiento aritmético a la derecha en el desplazamiento a la derecha en modo bit.