Operación a nivel de bits

Desplazamiento aritmético derecho

En un desplazamiento aritmético, los bits que se desplazan fuera de cualquier extremo se descartan. En un desplazamiento aritmético a la izquierda, los ceros se desplazan a la derecha; en un desplazamiento aritmético a la derecha, el bit de signo (el MSB en complemento a dos) se desplaza a la izquierda, preservando así el signo del operando.

Este ejemplo utiliza un registro de 8 bits, interpretado como complemento a dos:

 00010111 (decimal +23) LEFT-SHIFT= 00101110 (decimal +46)

 10010111 (decimal −105) RIGHT-SHIFT= 11001011 (decimal −53)

En el primer caso, el dígito más a la izquierda se desplazó más allá del final del registro, y un nuevo 0 se desplazó a la posición más a la derecha. En el segundo caso, el 1 más a la derecha se desplazó hacia fuera (tal vez en la bandera de acarreo), y un nuevo 1 se copió en la posición más a la izquierda, preservando el signo del número. Los desplazamientos múltiples a veces se acortan a un solo desplazamiento por algún número de dígitos. Por ejemplo:

 00010111 (decimal +23) LEFT-SHIFT-BY-TWO= 01011100 (decimal +92)

Un desplazamiento aritmético a la izquierda por n es equivalente a multiplicar por 2n (siempre que el valor no se desborde), mientras que un desplazamiento aritmético a la derecha por n de un valor de complemento a dos es equivalente a dividir por 2n y redondear hacia el infinito negativo. Si el número binario se trata como complemento a unos, entonces la misma operación de desplazamiento a la derecha resulta en la división por 2n y el redondeo hacia cero.

Desplazamiento lógicoEditar

Cambio lógico a la izquierda

Desplazamiento lógico a la derecha

En un desplazamiento lógico, los ceros se desplazan para reemplazar los bits descartados. Por lo tanto, los desplazamientos lógicos y aritméticos a la izquierda son exactamente iguales.

Sin embargo, como el desplazamiento lógico a la derecha inserta bits de valor 0 en el bit más significativo, en lugar de copiar el bit de signo, es ideal para números binarios sin signo, mientras que el desplazamiento aritmético a la derecha es ideal para números binarios de complemento a dos con signo.

Desplazamiento circularEditar

Otra forma de desplazamiento es el desplazamiento circular, rotación a nivel de bits o rotación de bits.

RotateEdit

Desplazamiento o giro circular a la izquierda

Desplazamiento circular a la derecha o rotar

En esta operación, a veces llamada rotar sin llevar, los bits se «rotan» como si los extremos izquierdo y derecho del registro estuvieran unidos. El valor que se desplaza a la derecha durante un desplazamiento a la izquierda es cualquier valor que se desplazó a la izquierda, y viceversa para una operación de desplazamiento a la derecha. Esto es útil si es necesario conservar todos los bits existentes, y se utiliza con frecuencia en la criptografía digital.

Girar a través de carryEdit

Girar a la izquierda a través del carry

Giro a la derecha a través de carry

La rotación mediante acarreo es una variante de la operación de rotación, en la que el bit que se desplaza hacia dentro (en cualquier extremo) es el valor antiguo de la bandera de acarreo, y el bit que se desplaza hacia fuera (en el otro extremo) se convierte en el nuevo valor de la bandera de acarreo.

Una sola rotación a través del carry puede simular un desplazamiento lógico o aritmético de una posición configurando la bandera de carry de antemano. Por ejemplo, si la bandera de carry contiene 0, entonces x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE es un desplazamiento lógico a la derecha, y si la bandera de carry contiene una copia del bit de signo, entonces x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE es un desplazamiento aritmético a la derecha. Por esta razón, algunos microcontroladores como los PICs de gama baja sólo tienen rotate y rotate through carry, y no se molestan con las instrucciones de desplazamiento aritmético o lógico.

Rotate through carry es especialmente útil cuando se realizan desplazamientos en números más grandes que el tamaño nativo de la palabra del procesador, porque si un número grande se almacena en dos registros, el bit que se desplaza de un extremo del primer registro debe entrar en el otro extremo del segundo. Con el desplazamiento circular, ese bit se «guarda» en el indicador de acarreo durante el primer desplazamiento, listo para entrar durante el segundo desplazamiento sin ninguna preparación adicional.

En lenguajes de alto nivelEditar

Familia CEdit

En los lenguajes de la familia C, los operadores lógicos de desplazamiento son «<<» para el desplazamiento a la izquierda y «>>» para el desplazamiento a la derecha. El número de posiciones a desplazar se da como segundo argumento al operador. Por ejemplo,

x = y << 2;

Asigna x el resultado de desplazar y a la izquierda en dos bits, lo que equivale a una multiplicación por cuatro.

Los desplazamientos pueden dar lugar a un comportamiento definido por la implementación o a un comportamiento indefinido, por lo que hay que tener cuidado al utilizarlos. El resultado de desplazar por una cuenta de bits mayor o igual al tamaño de la palabra es un comportamiento indefinido en C y C++. El desplazamiento a la derecha de un valor negativo está definido por la implementación y no es recomendado por las buenas prácticas de codificación; el resultado del desplazamiento a la izquierda de un valor con signo es indefinido si el resultado no puede ser representado en el tipo de resultado.

En C#, el desplazamiento a la derecha es un desplazamiento aritmético cuando el primer operando es un int o long. Si el primer operando es de tipo uint o ulong, el desplazamiento a la derecha es un desplazamiento lógico.

Desplazamientos circularesEditar

La familia de lenguajes C carece de un operador de rotación, pero se puede sintetizar uno a partir de los operadores de desplazamiento. Hay que tener cuidado de que la sentencia esté bien formada para evitar comportamientos indefinidos y ataques de sincronización en software con requisitos de seguridad. Por ejemplo, una implementación ingenua que rota a la izquierda un valor sin signo de 32 bits x en n posiciones es simplemente:

uint32_t x = ..., n = ...;uint32_t y = (x << n) | (x >> (32 - n));

Sin embargo, un desplazamiento de 0 bits resulta en un comportamiento indefinido en la expresión de la derecha (x >> (32 - n)) porque 32 - 0 es 32, y 32 está fuera del rango inclusive. Un segundo intento podría dar como resultado:

uint32_t x = ..., n = ...;uint32_t y = n ? (x << n) | (x >> (32 - n)) : x;

donde se prueba la cantidad de desplazamiento para asegurar que no introduce un comportamiento indefinido. Sin embargo, la bifurcación agrega una ruta de código adicional y presenta una oportunidad para el análisis de tiempo y el ataque, que a menudo no es aceptable en el software de alta integridad. Además, el código compila a múltiples instrucciones de máquina, lo que suele ser menos eficiente que la instrucción nativa del procesador.

Para evitar el comportamiento indefinido y las ramas bajo GCC y Clang, se recomienda lo siguiente. El patrón es reconocido por muchos compiladores, y el compilador emitirá una única instrucción rotate:

uint32_t x = ..., n = ...;uint32_t y = (x << n) | (x >> (-n & 31));

También hay intrínsecos específicos del compilador que implementan desplazamientos circulares, como _rotl8, _rotl16, _rotr8, _rotr16 en Microsoft Visual C++. Clang proporciona algunos intrínsecos de rotación para la compatibilidad con Microsoft que sufren los problemas anteriores. GCC no ofrece intrínsecos de rotación. Intel también proporciona x86 Intrinsics.

JavaEdit

En Java, todos los tipos enteros tienen signo, por lo que los operadores «<<» y «>>» realizan desplazamientos aritméticos. Java añade el operador «>>>» para realizar desplazamientos lógicos a la derecha, pero como las operaciones de desplazamiento lógico y aritmético a la izquierda son idénticas para los enteros con signo, no existe el operador «<<<» en Java.

Más detalles de los operadores de desplazamiento en Java:

• Los operadores << (desplazamiento a la izquierda), >> (desplazamiento a la derecha con signo), y >>> (desplazamiento a la derecha sin signo) se llaman operadores de desplazamiento.
• El tipo de la expresión de desplazamiento es el tipo promovido del operando de la izquierda. Por ejemplo, aByte >>> 2 es equivalente a ((int) aByte) >>> 2.
• Si el tipo promocionado del operando de la izquierda es int, sólo se utilizan los cinco bits de orden inferior del operando de la derecha como distancia de desplazamiento. Es como si el operando de la derecha se sometiera a un operador lógico AND a nivel de bits & con el valor de máscara 0x1f (0b11111). Por lo tanto, la distancia de desplazamiento realmente utilizada está siempre en el rango de 0 a 31, ambos inclusive.
• Si el tipo promocionado del operando de la izquierda es largo, entonces sólo se utilizan los seis bits de orden inferior del operando de la derecha como distancia de desplazamiento. Es como si el operando de la derecha se sometiera a un operador lógico AND a nivel de bits & con el valor de máscara 0x3f (0b111111). Por tanto, la distancia de desplazamiento realmente utilizada está siempre en el rango de 0 a 63, ambos inclusive.
• El valor de n >>> s es n posiciones de bit desplazadas a la derecha s con extensión cero.
• En las operaciones de bit y desplazamiento, el tipo byte se convierte implícitamente en int. Si el valor del byte es negativo, el bit más alto es uno, entonces se usan unos para rellenar los bytes extra en el int. Así que byte b1 = -5; int = b1 | 0x0200; resultará en i == -5.

JavaScriptEdit

JavaScript utiliza operaciones bitwise para evaluar cada uno de los lugares de dos o más unidades a 1 o 0.

PascalEdit

En Pascal, así como en todos sus dialectos (como Object Pascal y Standard Pascal), los operadores lógicos de desplazamiento a la izquierda y a la derecha son «shl» y «shr«, respectivamente. Incluso para los enteros con signo, shr se comporta como un desplazamiento lógico, y no copia el bit de signo. El número de posiciones a desplazar se da como segundo argumento. Por ejemplo, lo siguiente asigna a x el resultado de desplazar a y hacia la izquierda dos bits:

x := y shl 2;