Operación bit a bit

La negación bit a bit , o complemento bit a bit , es una operación unaria que realiza la negación lógica en cada bit, formando el complemento a uno 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 (decimal 7) = 1 000 (8 decimales)

NO 10101011 (decimal 171) = 01010100 (decimal 84)

El resultado es igual al complemento a dos del valor menos uno. Si se utiliza la aritmética del 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 especular" 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 puede 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 sencillo pero ilustrativo de su uso es invertir una imagen en escala de grises donde cada píxel se almacena como un entero sin signo.

La operación AND bit a bit es una operación binaria que toma dos representaciones binarias de igual longitud y realiza la operación lógica AND en cada par de bits correspondientes. Así, si ambos bits en la posición comparada son 1, el bit en la representación binaria resultante es 1 (1  × 1  = 1); de lo contrario, el resultado es 0 (1  × 0  = 0 y 0  × 0  = 0). Por ejemplo:

 010 1 (decimal 5) Y 001 1 (decimal 3) = 000 1 (decimal 1)

Esta operación se puede utilizar para determinar si un bit en particular está activado (1) o desactivado (0). Por ejemplo, dado el patrón de bits 0011 (decimal 3), para determinar si el segundo bit está activado, utilizamos una operación AND bit a bit con un patrón de bits que contiene solo un 1 en el segundo bit:

 00 1 1 (decimal 3) Y 00 1 0 (decimal 2) = 00 1 0 (decimal 2)

Dado que el resultado 0010 no es cero, sabemos que el segundo bit del patrón original estaba activado. Esto se conoce comúnmente como enmascaramiento de bits . (Por analogía, el uso de cinta adhesiva cubre, o enmascara , las partes que no deben modificarse o que no son de interés. En este caso, los valores 0 enmascaran los bits que no son relevantes).

La operación AND bit a bit se puede utilizar para borrar bits (o indicadores ) seleccionados de un registro , donde cada bit representa un estado booleano individual . Esta técnica es una forma eficiente de almacenar varios valores booleanos utilizando la menor cantidad de memoria posible.

Por ejemplo, 0110 (decimal 6) puede considerarse un conjunto de cuatro indicadores numerados de derecha a izquierda, donde el primero y el cuarto están desactivados (0), y el segundo y el tercero están activados (1). El tercer indicador puede desactivarse mediante una operación AND bit a bit con el patrón que tiene un cero solo en el tercer bit:

 0 1 10 (decimal 6) Y 1 0 11 (decimal 11) = 0 0 10 (decimal 2)

Debido a esta propiedad, resulta fácil determinar si un número binario es par o impar comprobando el valor del bit de menor valor. Siguiendo el ejemplo anterior:

 011 0 (decimal 6) Y 000 1 (decimal 1) = 000 0 (decimal 0)

Como 6 Y 1 es cero, 6 es divisible por dos y por lo tanto es par.

La operación OR bit a bit es una operación binaria que toma dos patrones de bits de igual longitud y realiza la operación OR inclusiva lógica 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 (decimal 5) O 0 011 (decimal 3) = 0 111 (decimal 7)

La operación OR bit a bit se puede utilizar para establecer a 1 los bits seleccionados del registro descrito anteriormente. Por ejemplo, el cuarto bit de 0010 (decimal 2) se puede establecer realizando una operación OR bit a bit con el patrón en el que solo se establece el cuarto bit:

0 0 1 0 (decimal 2) O 1 0 0 0 (decimal 8) = 1 0 1 0 (decimal 10)

Una operación XOR bit a bit es una operación binaria que toma dos patrones de bits de igual longitud y realiza la operación lógica OR 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 esta operación, comparamos dos bits, obteniendo 1 si son diferentes y 0 si son iguales. Por ejemplo:

 0 10 1 (decimal 5) XOR 0 01 1 (decimal 3) = 0 11 0 (decimal 6)

La operación XOR bit a bit se puede utilizar para invertir bits seleccionados en un registro (también llamada inversión o volteo). Cualquier bit se puede invertir mediante una operación XOR con 1. Por ejemplo, dado el patrón de bits 0010 (decimal 2), el segundo y el cuarto bit se pueden invertir mediante una operación XOR bit a bit con un patrón de bits que contenga 1 en la segunda y cuarta posición:

0 0 1 0 (decimal 2) XOR 1 0 1 0 (decimal 10) = 1 0 0 0 (decimal 8)

Esta técnica puede utilizarse para manipular patrones de bits que representan conjuntos de estados booleanos.

Los programadores de lenguaje ensamblador y los compiladores optimizadores a veces utilizan la operación XOR como atajo para establecer el valor de un registro a cero. Realizar una operación XOR entre un valor y sí mismo siempre da como resultado 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 n -dimensional${\displaystyle {\bf {F}}_{2}^{n}}$sobre el campo${\displaystyle {\bf {F}}_{2}}$, entonces la suma de vectores corresponde a la operación XOR bit a bit.

Suponiendo​${\displaystyle x\geq y}$Para números enteros no negativos, las operaciones bit a bit se pueden escribir de la siguiente manera :

${\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)\\&=\left(2^{\lfloor \log _{2}x\rfloor +1}-1\right)-x\\[10pt]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)\\[10pt]x\operatorname {OR} y&=\sum _{n=0}^{\lfloor \log _{2}x\rfloor }2^{n}{\Bigg (}\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}+\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\\&\qquad \qquad -\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right){\Bigg )}\\[10pt]x\operatorname {XOR} y&=\sum _{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}}}$

Existen 16 posibles funciones de verdad de dos variables binarias ; esto define una tabla de verdad , denominada tabla de búsqueda LUT2 , también conocida como orden de función booleana k=2 (2 entradas). Algunos proveedores utilizan el término conectivo ^{[ 2 ]} para instrucciones con un campo de 4 bits que identifica el conectivo binario específico; otros proveedores utilizan el término operación booleana ^{[ 3 ]} para 16 códigos de operación distintos.

Aquí están las operaciones equivalentes a nivel de bits de dos bits P y Q:

El equivalente ternario es una función booleana LUT3 de orden k=3 (tres entradas), que da como resultado una tabla de 256 operaciones, y en informática se denomina instrucción lógica ternaria bit a bit .

Si el ancho del registro (frecuentemente 32 o incluso 64) es mayor que el número de bits (normalmente 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 posicional , de manera que un desplazamiento a la izquierda aumenta y un desplazamiento a la derecha disminuye el valor del número; si se leen primero los dígitos de la izquierda, esto constituye una orientación big-endian . Sin tener en cuenta los efectos de borde 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 bit transporta el patrón de bits 1  posición de byte de la siguiente manera:

En un desplazamiento aritmético (o desplazamiento fijo), los bits que se desplazan hacia afuera por cualquiera de los extremos se descartan. En un desplazamiento aritmético hacia la izquierda, se introducen ceros por la derecha; en un desplazamiento aritmético hacia la derecha, se introduce el bit de signo (el bit más significativo en complemento a dos) por la izquierda, preservando así el signo del operando.

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

 00010111 (decimal +23) DESPLAZAMIENTO A LA 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 se colocó un nuevo 0 en 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 el indicador 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 desplazamientos múltiples se reducen a un solo desplazamiento de cierta cantidad de dígitos. Por ejemplo:

 00010111 (decimal +23) DESPLAZAMIENTO A LA IZQUIERDA DE DOS = 010111 00 (decimal +92)

Un desplazamiento aritmético a la izquierda de n es equivalente a multiplicar por 2n ⁽ 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 es equivalente a calcular la parte entera de la división por ²ⁿ . Si el número binario se trata como complemento a uno , entonces la misma operación de desplazamiento a la derecha resulta en una división por 2n ^y un redondeo hacia cero .

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

Sin embargo, dado que 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 con signo en complemento a dos .

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

• x & y = y & x
• x & (y & z) = (x & y) & z
• x & 0xFFFF = x^{[ 16 ]}
• x & 0 = 0

• x & x = x

• x | y = y | x
• x | (y | z) = (x | y) | z
• x | 0 = x
• x | 0xFFFF = 0xFFFF
• x | x = x

• ~(~x) = x

• x ^ y = y ^ x
• x ^ (y ^ z) = (x ^ y) ^ z
• x ^ 0 = x
• x ^ y ^ y = x
• x ^ x = 0
• x ^ 0xFFFF = ~x

Además, la operación XOR se puede componer utilizando las 3 operaciones básicas (AND, OR, NOT).

• a ^ b = (a | b) & (~a | ~b)
• a ^ b = (a & ~b) | (~a & b)

• x | (x & y) = x
• x & (x | y) = x
• ~(x | y) = ~x & ~y
• ~(x & y) = ~x | ~y
• x | (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)

Resolver ecuaciones con variables en álgebra booleana puede ser complicado, ya que, a diferencia del álgebra convencional, varias operaciones no tienen inversas. Las operaciones sin inversa pierden parte de los bits de datos originales al ejecutarse, y no es posible recuperar esta información faltante.

• Tiene inverso
  • NO
  • XOR
  • Gire a la izquierda
  • Gire a la derecha
• No hay reverso
  • Y
  • O
  • Desplazamiento a la izquierda
  • Desplazarse a la derecha

Las operaciones que aparecen al principio de esta lista se ejecutan primero. Consulte el artículo principal para obtener una lista más completa.

• ( )
• ~ -^{[ 17 ]}
• * / %
• + -^{[ 18 ]}
• << >>
• &
• ^
• |