stringtranslate.com

Desplazamiento aritmético

Un desplazamiento aritmético hacia la derecha de un número binario en 1. La posición vacía en el bit más significativo se rellena con una copia del MSB original.
Un desplazamiento aritmético hacia la izquierda de un número binario en 1. La posición vacía en el bit menos significativo se rellena con un cero.

En programación informática , un desplazamiento aritmético es un operador de desplazamiento , a veces denominado desplazamiento con signo (aunque no está restringido a los operandos con signo). Los dos tipos básicos son el desplazamiento aritmético a la izquierda y el desplazamiento aritmético a la derecha . Para los números binarios, es una operación bit a bit que desplaza todos los bits de su operando; cada bit del operando simplemente se mueve un número determinado de posiciones de bit y las posiciones de bit vacantes se rellenan. En lugar de rellenarse con todos los 0, como en el desplazamiento lógico , al desplazarse hacia la derecha, el bit más a la izquierda (normalmente el bit de signo en las representaciones de números enteros con signo) se replica para rellenar todas las posiciones vacantes (esto es un tipo de extensión de signo ).

Algunos autores prefieren los términos desplazamiento a la derecha fijo y desplazamiento a la derecha con relleno de ceros para desplazamientos aritméticos y lógicos respectivamente. [7]

Los desplazamientos aritméticos pueden ser útiles como formas eficientes de realizar la multiplicación o división de números enteros con signo por potencias de dos. Desplazar n bits hacia la izquierda en un número binario con signo o sin signo tiene el efecto de multiplicarlo por 2 n . Desplazar n bits hacia la derecha en un número binario con signo en complemento a dos tiene el efecto de dividirlo por 2 n , pero siempre se redondea hacia abajo (hacia el infinito negativo). Esto es diferente de la forma en que se suele realizar el redondeo en la división de números enteros con signo (que se redondea hacia 0). Esta discrepancia ha provocado errores en varios compiladores. [8]

Por ejemplo, en el conjunto de instrucciones x86 , la instrucción SAR (desplazamiento aritmético a la derecha) divide un número con signo por una potencia de dos, redondeando hacia el infinito negativo. [9] Sin embargo, la instrucción IDIV (división con signo) divide un número con signo, redondeando hacia cero. Por lo tanto, una instrucción SAR no puede sustituirse por una instrucción IDIV por potencia de dos ni viceversa.

Definición formal

La definición formal de un desplazamiento aritmético, según la Norma Federal 1037C , es que es:

Un desplazamiento, aplicado a la representación de un número en un sistema de numeración de base fija y en un sistema de representación de punto fijo , y en el que solo se desplazan los caracteres que representan la parte de punto fijo del número. Un desplazamiento aritmético suele ser equivalente a multiplicar el número por una potencia integral positiva o negativa de la base, excepto por el efecto de cualquier redondeo; compárese el desplazamiento lógico con el desplazamiento aritmético, especialmente en el caso de la representación de punto flotante .

Una palabra importante en la definición de FS 1073C es "generalmente".

Equivalencia de desplazamientos aritméticos y lógicos a la izquierda y multiplicación

Los desplazamientos aritméticos a la izquierda son equivalentes a la multiplicación por una potencia (positiva, integral) del radio (por ejemplo, una multiplicación por una potencia de 2 para números binarios). Los desplazamientos lógicos a la izquierda también son equivalentes, excepto que la multiplicación y los desplazamientos aritméticos pueden provocar un desbordamiento aritmético, mientras que los desplazamientos lógicos no [ cita requerida ] .

No equivalencia entre el desplazamiento aritmético a la derecha y la división

Sin embargo, los desplazamientos aritméticos a la derecha son trampas importantes para los incautos, especialmente en el tratamiento del redondeo de números enteros negativos. Por ejemplo, en la representación habitual de complemento a dos de números enteros negativos, −1 se representa como todos los 1. Para un entero con signo de 8 bits, esto es 1111 1111. Un desplazamiento aritmético a la derecha de 1 (o 2, 3, ..., 7) da como resultado 1111 1111 nuevamente, que sigue siendo −1. Esto corresponde a redondear hacia abajo (hacia el infinito negativo), pero no es la convención habitual para la división.

Con frecuencia se afirma que los desplazamientos aritméticos a la derecha son equivalentes a la división por una potencia (positiva, integral) de la base (por ejemplo, una división por una potencia de 2 para números binarios), y por lo tanto, esa división por una potencia de la base se puede optimizar implementándola como un desplazamiento aritmético a la derecha. (Un desplazador es mucho más simple que un divisor. En la mayoría de los procesadores, las instrucciones de desplazamiento se ejecutarán más rápido que las instrucciones de división). Una gran cantidad de manuales de programación, manuales y otras especificaciones de las décadas de 1960 y 1970 de empresas e instituciones como DEC , IBM , Data General y ANSI hacen afirmaciones incorrectas [10] [ página necesaria ] .

Los desplazamientos lógicos a la derecha son equivalentes a la división por una potencia de la base (normalmente 2) solo para números positivos o sin signo. Los desplazamientos aritméticos a la derecha son equivalentes a los desplazamientos lógicos a la derecha para números positivos con signo. Los desplazamientos aritméticos a la derecha para números negativos en complemento de N (normalmente complemento a dos ) son aproximadamente equivalentes a la división por una potencia de la base (normalmente 2), donde para los números impares se aplica el redondeo hacia abajo (no hacia 0 como se espera habitualmente).

Los desplazamientos aritméticos a la derecha para números negativos son equivalentes a la división que utiliza redondeo hacia 0 en la representación del complemento a uno de números con signo, como lo usaban algunas computadoras históricas, pero esto ya no se usa de manera general.

Manejo del problema en lenguajes de programación

La norma ISO (1999) para el lenguaje de programación C define el operador de desplazamiento a la derecha en términos de divisiones por potencias de 2. [11] Debido a la falta de equivalencia mencionada anteriormente, la norma excluye explícitamente de esa definición los desplazamientos a la derecha de números con signo que tienen valores negativos. No especifica el comportamiento del operador de desplazamiento a la derecha en tales circunstancias, sino que requiere que cada compilador de C individual defina el comportamiento del desplazamiento de valores negativos a la derecha. [nota 8]

Al igual que C, C++ tenía un desplazamiento a la derecha definido por la implementación para números enteros con signo hasta C++20. A partir del estándar C++20, el desplazamiento a la derecha de un número entero con signo se define como un desplazamiento aritmético. [13]

Aplicaciones

En aplicaciones en las que se desea un redondeo hacia abajo uniforme, los desplazamientos aritméticos a la derecha para valores con signo son útiles. Un ejemplo es la reducción de escala de las coordenadas ráster por una potencia de dos, lo que mantiene un espaciado uniforme. Por ejemplo, un desplazamiento a la derecha de 1 envía 0, 1, 2, 3, 4, 5, ... a 0, 0, 1, 1, 2, 2, ..., y −1, −2, −3, −4, ... a −1, −1, −2, −2, ..., manteniendo un espaciado uniforme como −2, −2, −1, −1, 0, 0, 1, 1, 2, 2, ... Por el contrario, la división de enteros con redondeo hacia cero envía −1, 0 y 1 a 0 (3 puntos en lugar de 2), lo que produce −2, −1, −1, 0, 0, 0, 1, 1, 2, 2, ... en su lugar, que es irregular en 0.

Notas

  1. ^ El >> operador en C y C++ no es necesariamente un desplazamiento aritmético. Por lo general, solo es un desplazamiento aritmético si se utiliza con un tipo entero con signo en su lado izquierdo. Si, en cambio, se utiliza con un tipo entero sin signo, será un desplazamiento lógico .
  2. ^ Fortran 2008.
  3. ^ El operador de desplazamiento aritmético a la derecha de Verilog solo realiza un desplazamiento aritmético si el primer operando tiene signo. Si el primer operando no tiene signo, el operador realiza un desplazamiento lógico a la derecha.
  4. ^ En el lenguaje de macros OpenVMS , si un desplazamiento aritmético es hacia la izquierda o hacia la derecha se determina en función de si el segundo operando es positivo o negativo. Esto es inusual. En la mayoría de los lenguajes de programación, las dos direcciones tienen operadores distintos, en los que el operador especifica la dirección y el segundo operando es implícitamente positivo. (Algunos lenguajes, como Verilog, requieren que los valores negativos se conviertan en valores positivos sin signo. Algunos lenguajes, como C y C++, no tienen un comportamiento definido si se utilizan valores negativos). [4] [ página necesaria ]
  5. ^ En Scheme arithmetic-shiftse puede hacer tanto desplazamiento a la izquierda como a la derecha, dependiendo del segundo operando, muy similar al lenguaje de macros OpenVMS, aunque Scheme R6RS añade ambos -righty -leftvariantes.
  6. ^ La Bitsclase del módulo de Haskell Data.Bitsdefine tanto shiftla posibilidad de tomar un argumento con signo como shiftLla shiftRde tomar argumentos sin signo. Estas son isomorfas ; para las nuevas definiciones, el programador necesita proporcionar solo una de las dos formas y la otra forma se definirá automáticamente en términos de la proporcionada.
  7. ^ El operador de desplazamiento aritmético a la izquierda de VHDL es inusual. En lugar de llenar el LSB del resultado con ceros, copia el LSB original en el nuevo LSB. Si bien esta es una imagen reflejada exacta del desplazamiento aritmético a la derecha, no es la definición convencional del operador y no es equivalente a la multiplicación por una potencia de 2. En el estándar VHDL 2008, este comportamiento extraño se dejó sin cambios (para compatibilidad con versiones anteriores) para los tipos de argumentos que no tienen una interpretación numérica forzada (por ejemplo, BIT_VECTOR), pero 'SLA' para los tipos de argumentos con y sin signo se comporta de la manera esperada (es decir, las posiciones más a la derecha se llenan con ceros). La función de desplazamiento lógico a la izquierda (SLL) de VHDL implementa el desplazamiento aritmético 'estándar' mencionado anteriormente.
  8. ^ El estándar C fue pensado para no restringir el lenguaje C a arquitecturas de complemento a uno o complemento a dos. En casos donde el comportamiento de las representaciones de complemento a uno y complemento a dos difiere, como en este caso, el estándar requiere que los compiladores C individuales documenten el comportamiento de sus arquitecturas de destino. La documentación para GNU Compiler Collection (GCC), por ejemplo, documenta su comportamiento como si empleara extensión de signos. [12]

Referencias

Referencia cruzada

  1. ^ "Manipulación de bits - Dlang Tour". tour.dlang.org . Consultado el 23 de junio de 2019 .
  2. ^ "Expresiones de operador: operadores binarios aritméticos y lógicos". doc.rust-lang.org . Consultado el 13 de noviembre de 2022 .
  3. ^ "Manual de referencia anotado de Ada 2012".
  4. ^ Hogar de los Indios 2001.
  5. ^ "Sintaxis del ensamblador Z80".
  6. ^ "El manual del conjunto de instrucciones RISC-V, volumen I: ISA sin privilegios" (PDF) . GitHub . 2019-12-13. págs. 18–20. Archivado (PDF) desde el original el 2022-10-09 . Consultado el 2021-08-07 .
  7. ^ Thomas R. Cain y Alan T. Sherman. "Cómo descifrar el código de Gifford". Sección 8.1: "Desplazamiento de bits persistente frente a no persistente". Criptología. 1997.
  8. ^ Steele Jr, Guy. "Arithmetic Shifting Considered Harmful" (PDF) . MIT AI Lab. Archivado (PDF) del original el 2022-10-09 . Consultado el 20 de mayo de 2013 .
  9. ^ Hyde 1996, § 6.6.2.2 SAR.
  10. ^ Steele 1977.
  11. ^ ISOIEC9899 1999, § 6.5.7 Operadores de desplazamiento bit a bit.
  12. ^ FSF 2008, § 4.5 Implementación de números enteros.
  13. ^ ISOCPP20 2020, § 7.6.7 Operadores de turno.

Fuentes utilizadas

Dominio público Este artículo incorpora material de dominio público de la Norma Federal 1037C. Administración de Servicios Generales . Archivado desde el original el 22 de enero de 2022.