En programación informática , una operación bit a bit opera sobre una cadena de bits , una matriz de bits o un número binario (considerado como una cadena de bits) al nivel de sus bits individuales . Es una acción rápida y sencilla, básica para las operaciones aritméticas de nivel superior y soportada directamente por el procesador . La mayoría de las operaciones bit a bit se presentan como instrucciones de dos operandos donde el resultado reemplaza uno de los operandos de entrada.
En procesadores simples de bajo costo, normalmente, las operaciones bit a bit son sustancialmente más rápidas que la división, varias veces más rápidas que la multiplicación y, a veces, significativamente más rápidas que la suma. Si bien los procesadores modernos generalmente realizan sumas y multiplicaciones tan rápido como las operaciones bit a bit debido a sus canales de instrucciones más largos y otras opciones de diseño arquitectónico , las operaciones bit a bit comúnmente usan menos energía debido al uso reducido de recursos. [1]
En las explicaciones siguientes, cualquier indicación de la posición de un bit se cuenta desde el lado derecho (menos significativo), avanzando hacia la izquierda. Por ejemplo, el valor binario 0001 (1 decimal) tiene ceros en todas las posiciones excepto en la primera (es decir, la más a la derecha).
El NOT bit a bit , o complemento bit a bit , es una operación unaria que realiza una negación lógica en cada bit, formando el complemento a unos del valor binario dado. Los bits que son 0 se convierten en 1 y los que son 1 se convierten en 0. Por ejemplo:
NO 0 111 (7 decimal) = 1 000 (8 decimales)
NO 10101011 (decimal 171) = 01010100 (84 decimales)
El resultado es igual al complemento a dos del valor menos uno. Si se utiliza la aritmética en complemento a dos, entonces NOT x = -x − 1.
Para los enteros sin signo , el complemento bit a bit de un número es el "reflejo en espejo" del número en el punto medio del rango del entero sin signo. Por ejemplo, para enteros sin signo de 8 bits, NOT x = 255 - xque se pueden visualizar en un gráfico como una línea descendente que efectivamente "invierte" un rango creciente de 0 a 255 a un rango decreciente de 255 a 0. Un ejemplo simple pero ilustrativo utiliza es invertir una imagen en escala de grises donde cada píxel se almacena como un entero sin signo.
Un AND bit a bit es una operación binaria que toma dos representaciones binarias de igual longitud y realiza la operación AND lógica en cada par de bits correspondientes. Por tanto, si ambos bits en la posición comparada son 1, el bit en la representación binaria resultante es 1 (1 × 1 = 1); en caso contrario, el resultado es 0 (1 × 0 = 0 y 0 × 0 = 0). Por ejemplo:
010 1 (5 decimales)Y 001 1 (3 decimal) = 000 1 (1 decimal)
La operación se puede utilizar para determinar si un bit en particular se establece (1) o se borra (0). Por ejemplo, dado un patrón de bits 0011 (3 decimal), para determinar si el segundo bit está establecido usamos un AND bit a bit con un patrón de bits que contiene 1 solo en el segundo bit:
00 1 1 (3 decimales)Y 00 1 0 (decimal 2) = 00 1 0 (decimal 2)
Debido a que el resultado 0010 no es cero, sabemos que se estableció el segundo bit en el patrón original. A esto se le suele denominar enmascaramiento de bits . (Por analogía, el uso de cinta adhesiva cubre, o máscaras , partes que no deben modificarse o partes que no son de interés. En este caso, los valores 0 enmascaran los bits que no son de interés).
El AND bit a bit se puede utilizar para borrar bits seleccionados (o banderas ) de un registro en el que cada bit representa un estado booleano individual . Esta técnica es una forma eficaz de almacenar varios valores booleanos utilizando la menor cantidad de memoria posible.
Por ejemplo, 0110 (6 decimal) se puede considerar un conjunto de cuatro indicadores, donde el primero y el cuarto indicadores están limpios (0) y el segundo y tercer indicadores están establecidos (1). La tercera bandera se puede borrar usando un AND bit a bit con el patrón que tiene un cero solo en el tercer bit:
0 1 10 (6 decimales)Y 1 0 11 (11 decimal) = 0 0 10 (2 decimales)
Debido a esta propiedad, resulta fácil verificar la paridad de un número binario verificando el valor del bit de menor valor. Usando el ejemplo anterior:
0110 (6 decimales)Y 0001 (1 decimal) = 0000 (0 decimal)
Como 6 Y 1 son cero, 6 es divisible por dos y, por lo tanto, par.
Un OR bit a bit es una operación binaria que toma dos patrones de bits de igual longitud y realiza la operación OR lógica inclusiva en cada par de bits correspondientes. El resultado en cada posición es 0 si ambos bits son 0, mientras que en caso contrario el resultado es 1. Por ejemplo:
0 101 (5 decimales)O 0 011 (3 decimal) = 0 111 (7 decimales)
El OR bit a bit se puede utilizar para establecer en 1 los bits seleccionados del registro descrito anteriormente. Por ejemplo, el cuarto bit de 0010 (decimal 2) se puede configurar realizando un OR bit a bit con el patrón con solo el cuarto bit establecido:
0 0 1 0 (2 decimales)O 1 0 0 0 (8 decimales) = 1 0 1 0 (10 decimales)
Un XOR bit a bit es una operación binaria que toma dos patrones de bits de igual longitud y realiza la operación OR lógica exclusiva en cada par de bits correspondientes. El resultado en cada posición es 1 si solo uno de los bits es 1, pero será 0 si ambos son 0 o ambos son 1. En este realizamos la comparación de dos bits, siendo 1 si los dos bits son diferentes, y 0 si son iguales. Por ejemplo:
0 10 1 (5 decimales)XOR 0 01 1 (3 decimales) = 0 11 0 (6 decimales)
El XOR bit a bit se puede utilizar para invertir bits seleccionados en un registro (también llamado alternar o invertir). Cualquier bit se puede alternar mediante XOR con 1. Por ejemplo, dado el patrón de bits 0010 (2 decimal), el segundo y cuarto bits se pueden alternar mediante un XOR bit a bit con un patrón de bits que contiene 1 en las posiciones segunda y cuarta:
0 0 1 0 (2 decimales)XOR 1 0 1 0 (decimal 10) = 1 0 0 0 (8 decimales)
Esta técnica se puede utilizar para manipular patrones de bits que representan conjuntos de estados booleanos.
Los programadores de lenguaje ensamblador y los compiladores de optimización a veces usan XOR como un atajo para establecer el valor de un registro en cero. Realizar XOR en un valor contra sí mismo siempre produce cero, y en muchas arquitecturas esta operación requiere menos ciclos de reloj y menos memoria que cargar un valor cero y guardarlo en el registro.
Si el conjunto de cadenas de bits de longitud fija n (es decir, palabras de máquina ) se considera como un espacio vectorial de n dimensiones sobre el campo , entonces la suma de vectores corresponde al XOR bit a bit.
Suponiendo que , para los enteros no negativos, las operaciones bit a bit se pueden escribir de la siguiente manera:
Hay 16 posibles funciones de verdad de dos variables binarias ; esto define una tabla de verdad .
Aquí están las operaciones equivalentes bit a bit de dos bits P y Q:
Los desplazamientos de bits a veces se consideran operaciones bit a bit porque tratan un valor como una serie de bits en lugar de una cantidad numérica. En estas operaciones, los dígitos se mueven o desplazan hacia la izquierda o hacia la derecha. Los registros en el procesador de una computadora tienen un ancho fijo, por lo que algunos bits se "desplazarán hacia afuera" del registro en un extremo, mientras que el mismo número de bits se "desplazarán hacia adentro" desde el otro extremo; Las diferencias entre los operadores de desplazamiento de bits radican en cómo determinan los valores de los bits desplazados.
Si el ancho del registro (frecuentemente 32 o incluso 64) es mayor que el número de bits (generalmente 8) de la unidad direccionable más pequeña, frecuentemente llamada byte, las operaciones de desplazamiento inducen un esquema de direccionamiento de bytes a bits. De este modo, las orientaciones "izquierda" y "derecha" se toman de la escritura estándar de números en notación de valor posicional , de modo que un desplazamiento hacia la izquierda aumenta y un desplazamiento hacia la derecha disminuye el valor del número; si los dígitos de la izquierda se leen primero, esto constituye una orientación big-endian . Sin tener en cuenta los efectos de los límites en ambos extremos del registro, las operaciones de desplazamiento aritmético y lógico se comportan de la misma manera, y un desplazamiento de 8 posiciones de bits transporta el patrón de bits en una posición de 1 byte de la siguiente manera:
En un desplazamiento aritmético , los bits que se desplazan fuera de cualquiera de los extremos se descartan. En un desplazamiento aritmético hacia la izquierda, los ceros se desplazan hacia la derecha; en un desplazamiento aritmético a la derecha, el bit de signo (el MSB en complemento a dos) se desplaza hacia la izquierda, preservando así el signo del operando.
Este ejemplo utiliza un registro de 8 bits, interpretado como complemento a dos:
00010111 (decimal +23) SHIFT IZQUIERDA= 0010111 0 (decimal +46)
10010111 (decimal −105) DESPLAZAMIENTO A LA DERECHA= 1 1001011 (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 afuera (quizás hacia la bandera de acarreo ) y se copió un nuevo 1 en la posición más a la izquierda, conservando el signo del número. A veces, los turnos múltiples se reducen a un solo turno en una cierta cantidad de dígitos. Por ejemplo:
00010111 (decimal +23) DESPLAZAMIENTO A LA IZQUIERDA POR DOS= 010111 00 (decimal +92)
Un desplazamiento aritmético a la izquierda de n equivale a multiplicar por 2 n (siempre que el valor no se desborde ), mientras que un desplazamiento aritmético a la derecha de n de un valor en complemento a dos equivale a tomar el suelo de la división por 2 n . Si el número binario se trata como complemento a uno , entonces la misma operación de desplazamiento a la derecha da como resultado la división por 2 n y el redondeo hacia cero .
En un desplazamiento lógico , se desplazan ceros para reemplazar los bits descartados. Por lo tanto, los desplazamientos a la izquierda lógicos y aritméticos 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 en complemento a dos con signo.
Otra forma de desplazamiento es el desplazamiento circular , rotación bit a bit o rotación de bits .
En esta operación, a veces llamada rotar sin acarreo , los bits se "rotan" como si los extremos izquierdo y derecho del registro estuvieran unidos. El valor que se desplaza hacia la derecha durante un desplazamiento hacia la izquierda es cualquier valor que se desplaza hacia la izquierda, y viceversa para una operación de desplazamiento hacia la derecha. Esto es útil si es necesario conservar todos los bits existentes y se utiliza con frecuencia en criptografía digital . [ se necesita aclaración ]
Rotar mediante acarreo es una variante de la operación de rotación, donde el bit que se desplaza hacia adentro (en cualquier extremo) es el valor anterior de la bandera de acarreo, y el bit que se desplaza hacia afuera (en el otro extremo) se convierte en el nuevo valor de la bandera de acarreo.
Una sola rotación a través del acarreo puede simular un cambio lógico o aritmético de una posición configurando la bandera de acarreo de antemano. Por ejemplo, si el indicador de acarreo contiene 0, entonces x RIGHT-ROTATE-THROUGH-CARRY-BY-ONEes un desplazamiento lógico a la derecha, y si el indicador de acarreo contiene una copia del bit de signo, entonces x RIGHT-ROTATE-THROUGH-CARRY-BY-ONEes un desplazamiento aritmético a la derecha. Por esta razón, algunos microcontroladores, como los PIC de gama baja, simplemente rotan y rotan mediante carry y no se molestan con instrucciones de cambio aritméticas o lógicas.
La rotación mediante acarreo es especialmente útil cuando se realizan desplazamientos en números mayores que el tamaño de palabra nativo del procesador , porque si se almacena un número grande en dos registros, el bit que se desplaza de un extremo del primer registro debe entrar en el otro extremo del el segundo. Con la rotación mediante acarreo, esa broca se "guarda" en la bandera de acarreo durante el primer turno, lista para cambiar durante el segundo turno sin ninguna preparación adicional.
En los lenguajes C y C++, los operadores de desplazamiento lógicos son " <<" para desplazamiento a la izquierda y " >>" para desplazamiento a la derecha. El número de lugares a cambiar se proporciona como segundo argumento al operador. Por ejemplo,
![{\displaystyle {\begin{aligned}\operatorname {NOT} x&=\sum _{n=0}^{\lfloor \log _{2}(x)\rfloor }2^{n}\left[\left (\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}+1\right){\bmod {2}}\right]=2^{\ left\lfloor \log _{2}(x)\right\rfloor +1}-1-x\\x\operatorname {AND} y&=\sum _{n=0}^{\lfloor \log _{2 }(x)\rfloor }2^{n}\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)\left( \left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)\\x\operatorname {O} y&=\sum _{n=0} ^{\lfloor \log _{2}(x)\rfloor }2^{n}\left(\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor { \bmod {2}}\right)+\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)-\left(\ left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)\left(\left\lfloor {\frac {y}{2^{n} }}\right\rfloor {\bmod {2}}\right)\right)\\x\operatorname {XOR} y&=\sum _{n=0}^{\lfloor \log _{2}(x) \rfloor }2^{n}\left(\left[\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)+ \left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)\right]{\bmod {2}}\right)=\ suma _{n=0}^{\lfloor \log _{2}(x)\rfloor }2^{n}\left[\left(\left\lfloor {\frac {x}{2^{n} }}\right\rfloor +\left\lfloor {\frac {y}{2^{n}}}\right\rfloor \right){\bmod {2}}\right]\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b873908a8c81ef7d63805b77756dbcf70a03b39c)
x = y << 2 ; Asigna xel resultado de desplazarse yhacia la izquierda dos bits, lo que equivale a una multiplicación por cuatro.
Los cambios pueden dar como resultado un comportamiento definido por la implementación o un comportamiento indefinido , por lo que se debe tener cuidado al usarlos. El resultado de cambiar un número de bits mayor o igual al tamaño de la palabra es un comportamiento indefinido en C y C++. [2] [3] Desplazar un valor negativo a la derecha está definido por la implementación y no lo recomiendan las buenas prácticas de codificación; [4] el resultado de desplazar hacia la izquierda un valor con signo no está definido si el resultado no se puede representar en el tipo de resultado. [2]
En C#, el desplazamiento a la derecha es un desplazamiento aritmético cuando el primer operando es int o long. Si el primer operando es de tipo uint o ulong, el desplazamiento a la derecha es un desplazamiento lógico. [5]
La familia de lenguajes C carece de un operador de rotación (aunque C++ 20 proporciona std::rotly std::rotr), pero se puede sintetizar uno a partir de los operadores de cambio. Se debe tener cuidado para garantizar que la declaración esté bien formada para evitar comportamientos indefinidos y ataques de sincronización en software con requisitos de seguridad. [6] Por ejemplo, una implementación ingenua que rota a la izquierda un valor sin signo de 32 bits xpor nposiciones es simplemente
uint32_t x = ..., n = ...; uint32_t y = ( x << n ) | ( x >> ( 32 - norte )); Sin embargo, un desplazamiento de 0bits da como resultado un comportamiento indefinido en la expresión de la derecha (x >> (32 - n))porque 32 - 0es 32y 32está fuera del rango 0–31 inclusive. Un segundo intento podría resultar en
uint32_t x = ..., n = ...; uint32_t y = n ? ( x << norte ) | ( x >> ( 32 - n ) ) : x ; donde se prueba la cantidad de cambio para garantizar que no introduzca un comportamiento indefinido. Sin embargo, la rama agrega una ruta de código adicional y presenta una oportunidad para realizar análisis y ataques de tiempo, lo que a menudo no es aceptable en software de alta integridad. [6] Además, el código se compila en múltiples instrucciones de máquina, lo que a menudo es menos eficiente que la instrucción nativa del procesador.
Para evitar el comportamiento indefinido y las ramas en GCC y Clang , se recomienda lo siguiente. Muchos compiladores reconocen el patrón y el compilador emitirá una única instrucción de rotación: [7] [8] [9]
uint32_t x = ..., n = ...; uint32_t y = ( x << n ) | ( x >> ( - n & 31 )); También hay intrínsecos específicos del compilador que implementan cambios circulares , como _rotl8, _rotl16, _rotr8, _rotr16 en Microsoft Visual C++ . Clang proporciona algunos elementos intrínsecos de rotación para la compatibilidad con Microsoft que sufre los problemas anteriores. [9] GCC no ofrece funciones intrínsecas de rotación. Intel también proporciona elementos intrínsecos x86.
En Java , todos los tipos de enteros tienen signo, por lo que los operadores " <<" y " >>" realizan desplazamientos aritméticos. Java agrega el operador " >>>" para realizar desplazamientos lógicos a la derecha, pero dado que las operaciones lógicas y aritméticas de desplazamiento a la izquierda son idénticas para enteros con signo, no existe un <<<operador " " en Java.
Más detalles de los operadores de turnos de Java: [10]
<<(desplazamiento a la izquierda), >>(desplazamiento a la derecha con signo) y >>>(desplazamiento a la derecha sin signo) se denominan operadores de desplazamiento .aByte >>> 2equivale a .((int) aByte) >>> 2n >>> ses n posiciones de bits desplazadas a la derecha con extensión cero.bytese convierte implícitamente a int. Si el valor del byte es negativo, el bit más alto es uno, entonces los unos se usan para llenar los bytes adicionales en el int. Entonces resultará en .byte b1 = -5; int i = b1 | 0x0200;i == -5JavaScript utiliza operaciones bit a bit para evaluar cada una de dos o más unidades y colocarlas en 1 o 0. [12]
En Pascal, así como en todos sus dialectos (como Object Pascal y Standard Pascal ), los operadores lógicos de desplazamiento hacia la izquierda y hacia la derecha son " shl" y " shr", respectivamente. Incluso para enteros con signo, shrse comporta como un desplazamiento lógico y no copia el bit de signo. El número de lugares a cambiar se da como segundo argumento. Por ejemplo, lo siguiente asigna a x el resultado de desplazar y hacia la izquierda dos bits:
x := y shl 2 ; Las operaciones bit a bit son necesarias particularmente en programación de nivel inferior, como controladores de dispositivos, gráficos de bajo nivel, ensamblaje de paquetes de protocolos de comunicaciones y decodificación.
Aunque las máquinas suelen tener instrucciones integradas eficientes para realizar operaciones aritméticas y lógicas, todas estas operaciones se pueden realizar combinando operadores bit a bit y pruebas cero de varias maneras. [13] Por ejemplo, aquí hay una implementación de pseudocódigo de la multiplicación del antiguo Egipto que muestra cómo multiplicar dos números enteros arbitrarios ay b( amayor que b) usando solo cambios de bits y suma:
c ← 0 mientras b ≠ 0 si ( b y 1 ) ≠ 0 c ← c + a desplazar a la izquierda a en 1 desplazar a la derecha b en 1 regresar c Otro ejemplo es una implementación de pseudocódigo de suma, que muestra cómo calcular una suma de dos números enteros ay butiliza operadores bit a bit y pruebas de cero:
mientras que a ≠ 0 c ← b y a b ← b xor a desplazamiento a la izquierda c por 1 a ← c devolver b A veces resulta útil simplificar expresiones complejas formadas por operaciones bit a bit, por ejemplo al escribir compiladores. El objetivo de un compilador es traducir un lenguaje de programación de alto nivel al código de máquina más eficiente posible. El álgebra booleana se utiliza para simplificar expresiones bit a bit complejas.
x & y = y & xx & (y & z) = (x & y) & zx & 0xFFFF = x[14]x & 0 = 0x & x = xx | y = y | xx | (y | z) = (x | y) | zx | 0 = xx | 0xFFFF = 0xFFFFx | x = x~(~x) = xx ^ y = y ^ xx ^ (y ^ z) = (x ^ y) ^ zx ^ 0 = xx ^ y ^ y = xx ^ x = 0x ^ 0xFFFF = ~xAdemás, XOR se puede componer utilizando las 3 operaciones básicas (Y, O, NO)
a ^ b = (a | b) & (~a | ~b)a ^ b = (a & ~b) | (~a & b)x | (x & y) = xx & (x | y) = x~(x | y) = ~x & ~y~(x & y) = ~x | ~yx | (y & z) = (x | y) & (x | z)x & (y | z) = (x & y) | (x & z)x & (y ^ z) = (x & y) ^ (x & z)x + y = (x ^ y) + ((x & y) << 1)x - y = ~(~x + y)Puede resultar difícil resolver variables en álgebra booleana porque, a diferencia del álgebra regular, varias operaciones no tienen inversas. Las operaciones sin inversas pierden algunos de los bits de datos originales cuando se realizan y no es posible recuperar esta información faltante.
Las operaciones que se encuentran en la parte superior de esta lista se ejecutan primero. Consulte el artículo principal para obtener una lista más completa.
( )~ -[15]* / %+ -[dieciséis]<< >>&^|