En programación de computadoras , un desplazamiento aritmético es un operador de desplazamiento , a veces denominado desplazamiento con signo (aunque no está restringido a 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 números binarios , es una operación bit a bit que desplaza todos los bits de su operando; cada bit en el operando simplemente se mueve un número dado de posiciones de bit, y las posiciones de bit vacantes se rellenan. En lugar de rellenarse con ceros, como en el desplazamiento lógico , cuando se desplaza a la derecha, el bit más a la izquierda (normalmente el bit de signoen representaciones de enteros con signo) se replica para llenar todas las posiciones vacantes (esto es una especie de extensión de signo ).
Idioma o procesador | Izquierda | Derecha |
---|---|---|
ActionScript 3, Java , JavaScript , Python , PHP , Ruby ; C , C ++ , [1] D , C # , Go , Julia , Swift (solo tipos con signo) [nota 1] | << | >> |
Ada | Shift_Left [2] | Shift_Right_Arithmetic |
Kotlin | shl | shr |
ML estándar | << | ~>> |
Verilog | <<< | >>> [nota 2] |
Lenguaje de macros OpenVMS | @ [nota 3] | |
Esquema | arithmetic-shift [nota 4] | |
Lisp común | ash | |
OCaml | lsl | asr |
Haskell | Data.Bits.shift [nota 5] | |
Montaje, 68k | ASL | ASR |
Ensamblaje, x86 | SAL | SAR |
VHDL | sla [nota 6] | sra |
Z80 | SLA [4] | SRA |
Algunos autores prefieren los términos pegajosas desplazamiento a la derecha y relleno de cero desplazamiento a la derecha para los turnos aritméticas y lógicas, respectivamente. [5]
Los cambios aritméticos pueden ser útiles como formas eficientes de realizar la multiplicación o división de enteros con signo por potencias de dos. El desplazamiento a la izquierda n bits en un número binario con signo o sin signo tiene el efecto de multiplicarlo por 2 n . Desplazarse a la derecha n bits en un número binario con signo de complemento a dos tiene el efecto de dividirlo entre 2 n , pero siempre se redondea hacia abajo (hacia el infinito negativo). Esto es diferente de la forma en que generalmente se realiza el redondeo en la división de enteros con signo (que se redondea hacia 0). Esta discrepancia ha dado lugar a errores en varios compiladores. [6]
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. [7] 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 ser sustituida por una instrucción IDIV por el poder de dos instrucciones ni viceversa.
Definicion formal
La definición formal de un cambio aritmético, del Estándar 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 mueven los caracteres que representan la parte de punto fijo del número. Un desplazamiento aritmético generalmente equivale a multiplicar el número por una potencia integral positiva o negativa de la base, excepto por el efecto de cualquier redondeo; compare 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 "normalmente".
Equivalencia de multiplicaciones y desplazamientos aritméticos y lógicos a la izquierda
Los desplazamientos aritméticos a la izquierda son equivalentes a la multiplicación por una potencia (positiva, integral) de la base (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 desencadenar un desbordamiento aritmético, mientras que los desplazamientos lógicos no.
No equivalencia de desplazamiento y división aritmética a la derecha
Sin embargo, los desplazamientos aritméticos a la derecha son trampas importantes para los incautos, específicamente en el tratamiento del redondeo de números enteros negativos. Por ejemplo, en la representación habitual en complemento a dos de enteros negativos, −1 se representa como todos unos. Para un entero de 8 bits con signo, esto es 1111 1111. Un desplazamiento aritmético a la derecha en 1 (o 2, 3, ..., 7) da como resultado 1111 1111 nuevamente, que sigue siendo -1. Esto corresponde al redondeo 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 puede ser optimizado implementándolo como un desplazamiento aritmético a la derecha. (Un cambiador es mucho más simple que un divisor. En la mayoría de los procesadores, las instrucciones de cambio se ejecutarán más rápido que las instrucciones de división). Gran cantidad de manuales de programación, manuales y otras especificaciones de las décadas de 1960 y 1970 de compañías e instituciones como DEC , IBM , Data General , y ANSI hace declaraciones incorrectas [8] [ página necesaria ] .
Los desplazamientos lógicos a la derecha son equivalentes a la división por una potencia de la base (generalmente 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 con signo positivo. Los desplazamientos aritméticos a la derecha para números negativos en el complemento de N − 1 (generalmente en complemento a dos ) son aproximadamente equivalentes a la división por una potencia de la base (generalmente 2), donde para números impares se aplica el redondeo hacia abajo (no hacia 0 como generalmente se espera).
Los desplazamientos aritméticos a la derecha para números negativos son equivalentes a la división que usa el redondeo hacia 0 en la representación del complemento a uno de los números con signo, como lo usaban algunas computadoras históricas, pero esto ya no es de uso general.
Manejo del problema en lenguajes de programación
El estándar ISO (1999) para el lenguaje de programación C define el operador de cambio a la derecha en términos de divisiones por potencias de 2. [9] Debido a la no equivalencia antes mencionada, el estándar excluye explícitamente de esa definición los cambios a la derecha de los signos números que tienen valores negativos. No especifica el comportamiento del operador de desplazamiento derecho en tales circunstancias, sino que requiere que cada compilador de C individual defina el comportamiento de desplazamiento de los valores negativos a la derecha. [nota 7]
Aplicaciones
En aplicaciones donde se desea un redondeo hacia abajo consistente, los desplazamientos aritméticos a la derecha para valores con signo son útiles. Un ejemplo es la reducción de las coordenadas ráster en una potencia de dos, lo que mantiene un espaciado uniforme. Por ejemplo, el desplazamiento a la derecha en 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 el espaciado par como −2, −2, −1, −1, 0, 0, 1, 1, 2, 2 , ... Por el contrario, la división entera con redondeo hacia cero envía -1, 0 y 1 todos a 0 (3 puntos en lugar de 2), lo que da como resultado -2, -1, -1, 0, 0, 0, 1, 1, 2, 2, ... en cambio, que es irregular en 0.
Notas
- ^ El
>>
operador en C y C ++ no es necesariamente un cambio aritmético. Por lo general, es solo un cambio aritmético si se usa con un tipo entero con signo en su lado izquierdo. Si se usa en un tipo entero sin signo, será uncambio lógico . - ^ El operador de desplazamiento aritmético a la derecha de Verilog sólo realiza realmente un desplazamiento aritmético si el primer operando está firmado. Si el primer operando no tiene signo, el operador realmente realiza undesplazamiento lógico a la derecha.
- ^ En ellenguaje de macros de OpenVMS , si un desplazamiento aritmético es hacia la izquierda o hacia la derecha está determinado por 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, 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). [3] [ página necesaria ]
- ^ En el esquema
arithmetic-shift
puede ser a la vez desviación a la izquierda y la derecha, dependiendo del segundo operando, muy similar a los OpenVMS lenguaje de macros, aunque R6RS Esquema añade tanto-right
y-left
variantes. - ^ La
Bits
clase delData.Bits
módulode Haskelldefine tantoshift
tomar un argumento firmado comoshiftL
/shiftR
tomar argumentos sin firmar. Estos son isomorfos ; para las nuevas definiciones, el programador debe proporcionar sólo una de las dos formas y la otra forma se definirá automáticamente en términos de la proporcionada. - ^ El operador aritmético de desplazamiento a la izquierda de VHDL es inusual. En lugar de llenar el LSB del resultado con cero, copia el LSB original en el nuevo LSB. Si bien esta es una imagen especular 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 no se modificó (por compatibilidad con versiones anteriores ) para tipos de argumentos que no tienen interpretación numérica forzada (por ejemplo, BIT_VECTOR) pero 'SLA' paratipos de argumentos firmados y sin firmar 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' antes mencionado.
- ^ El estándar C tenía la intención de no restringir el lenguaje C a arquitecturas de complemento a uno o complemento a dos. En los casos en los que los comportamientos de las representaciones de complemento a uno y complemento a dos difieren, como este, el estándar requiere que los compiladores de C individuales documenten el comportamiento de sus arquitecturas objetivo. La documentación de GNU Compiler Collection (GCC), por ejemplo, documenta su comportamiento al emplear sign-extension. [10]
Referencias
Referencia cruzada
- ^ "Manipulación de bits - Dlang Tour" . tour.dlang.org . Consultado el 23 de junio de 2019 .
- ^ "Manual de referencia de Ada 2012 anotado" .
- ^ HP 2001 .
- ^ "Sintaxis del ensamblador Z80" .
- ^ Thomas R. Cain y Alan T. Sherman. "Cómo romper el cifrado de Gifford" . Sección 8.1: "Desplazamiento de bits pegajoso versus no pegajoso". Cryptologia. 1997.
- ^ Steele Jr, Guy. "Desplazamiento aritmético considerado perjudicial" (PDF) . Laboratorio de IA del MIT . Consultado el 20 de mayo de 2013 .
- ^ Hyde 1996 , § 6.6.2.2 SAR.
- ^ Steele 1977 .
- ^ ISOIEC9899 1999 , § 6.5.7 Operadores de desplazamiento bit a bit.
- ^ FSF 2008 , § 4.5 Implementación de enteros.
Fuentes utilizadas
Este artículo incorpora material de dominio público del documento de la Administración de Servicios Generales : "Norma Federal 1037C" .
- Knuth, Donald (1969). El arte de la programación informática , Volumen 2 - Algoritmos seminuméricos . Reading, Mass .: Addison-Wesley. págs. 169-170.
- Steele, Guy L. (noviembre de 1977). "Desplazamiento aritmético considerado perjudicial" . Archivo de avisos de ACM SIGPLAN . Nueva York: ACM Press. 12 (11): 61–69. doi : 10.1145 / 956641.956647 . hdl : 1721,1 / 6090 .
- "3.7.1 Operador de desplazamiento aritmético" . VAX MACRO y manual de referencia del conjunto de instrucciones . Documentación de sistemas HP OpenVMS . Compañía de desarrollo de Hewlett-Packard. Abril de 2001. Archivado desde el original el 8 de agosto de 2011.
- "Lenguajes de programación - C". ISO / IEC 9899: 1999. Organización Internacional de Normalización . 1999. Cite journal requiere
|journal=
( ayuda ) - Hyde, Randall (26 de septiembre de 1996). "CAPÍTULO SEIS: EL CONJUNTO DE INSTRUCCIONES 80x86 (Parte 3)". El arte de la PROGRAMACIÓN DEL LENGUAJE DE ASAMBLEAS . Archivado desde el original el 23 de noviembre de 2007 . Consultado el 28 de noviembre de 2007 .
- "Implementación C" . Manual de GCC . Fundación de Software Libre . 2008.