Operación bit a bit

Computer operation that operates on values at the level of their individual bits

Este artículo necesita citas adicionales para su verificación . Por favor, ayuda a mejorar este artículo mediante la adición de citas de fuentes confiables . El material no obtenido puede ser cuestionado y eliminado. Buscar fuentes:  "Operación bit a bit"  -  noticias  · periódicos  · libros  · académico  · JSTOR ( agosto de 2018 ) ( Aprenda cómo y cuándo eliminar este mensaje de plantilla )

"Desplazamiento binario" vuelve a dirigir aquí. Para el código de exceso de 3, consulte (código) binario desplazado . Para conocer el concepto general, consulte Offset binary .

En la programación de computadoras , una operación bit a bit opera en 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 a 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. ^{[ aclaración necesaria ]} Mientras que los procesadores modernos suelen realizar sumas y multiplicaciones tan rápido como las operaciones bit a bit debido a sus líneas de instrucción más largas y otras opciones de diseño arquitectónico , las operaciones bit a bit utilizan menos energía debido al uso reducido de recursos. ^[1]

Operadores bit a bit

En las explicaciones a continuación, 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 (decimal 1) tiene ceros en cada posición menos en la primera (es decir, la más a la derecha).

NO

Ver también: Complemento de uno

El NOT bit a bit , o complemento , 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 (decimal 7) = 1 000 (decimal 8)

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

El complemento bit a bit es igual al complemento a dos del valor menos uno. Si se usa aritmética en complemento a dos, entonces NOT x = -x − 1.

Para enteros sin signo , el complemento bit a bit de un número es el "reflejo de espejo" del número en el punto medio del rango del entero sin signo. Por ejemplo, para enteros de 8 bits sin signo NOT x = 255 - x, que 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 uso consiste en invertir una imagen en escala de grises donde cada píxel se almacena como un entero sin signo.

Y

AND bit a bit de enteros de 4 bits

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 los bits correspondientes, lo que equivale a multiplicarlos. 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); 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)

La operación puede usarse para determinar si un bit en particular está establecido (1) o borrado (0). Por ejemplo, dado un patrón de bits 0011 (decimal 3), 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 (decimal 3)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 del patrón original. Esto a menudo se denomina enmascaramiento de bits . (Por analogía, el uso de cinta de enmascarar cubre, o enmascara , partes que no se deben alterar 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 los 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 una serie de valores booleanos utilizando la menor cantidad de memoria posible.

Por ejemplo, 0110 (decimal 6) se puede considerar un conjunto de cuatro banderas, donde la primera y cuarta banderas son claras (0) y la segunda y tercera banderas están configuradas (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 (decimal 6)Y 1 0 11 (decimal 11) = 0 0 10 (decimal 2)

Debido a esta propiedad, resulta fácil comprobar la paridad de un número binario comprobando el valor del bit de menor valor. Usando el ejemplo anterior:

 0110 (decimal 6)Y 0001 (decimal 1) = 0000 (decimal 0)

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

O

OR bit a bit de enteros de 4 bits

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 (decimal 5)O 0011 (decimal 3) = 0111 (decimal 7)

El OR bit a bit puede usarse para poner a 1 los bits seleccionados del registro descrito anteriormente. Por ejemplo, el cuarto bit de 0010 (decimal 2) puede establecerse realizando un OR bit a bit con el patrón con solo el cuarto bit establecido:

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

XOR

XOR bit a bit de enteros de 4 bits

Un 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 exclusiva OR 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 esto 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 (decimal 5)XOR 0 01 1 (decimal 3) = 0 11 0 (decimal 6)

El XOR bit a bit puede usarse 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 (decimal 2), el segundo y cuarto bits se pueden alternar mediante un XOR bit a bit con un patrón de bits que contiene 1 en la segunda y cuarta posiciones:

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

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 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 un espacio vectorial n- dimensional sobre el campo , entonces la suma de vectores corresponde al XOR bit a bit. ${\displaystyle {\bf {F}}_{2}^{n}}$ F 2 {\displaystyle {\bf {F}}_{2}}

Equivalentes matemáticos

Suponiendo , para los enteros no negativos, las operaciones bit a bit se pueden escribir de la siguiente manera:${\displaystyle x\geq y}$

${\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 {OR} 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)+\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)\\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)=\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}}}$

Tabla de verdad para todos los operadores lógicos binarios

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:

pag	q		F 0	NOR 1	Xq 2	¬p 3	↛ 4	¬q 5	XOR 6	NAND 7		Y 8	XNOR 9	q 10	Si / entonces 11	p. 12	Entonces / si 13	O 14	T 15
1	1		0	0	0	0	0	0	0	0		1	1	1	1	1	1	1	1
1	0		0	0	0	0	1	1	1	1		0	0	0	0	1	1	1	1
0	1		0	0	1	1	0	0	1	1		0	0	1	1	0	0	1	1
0	0		0	1	0	1	0	1	0	1		0	1	0	1	0	1	0	1
Equivalentes bit a bit			0	NO (p OR q)	(NO p) Y q	NO p	py (NO q)	NO q	p XOR q	NO (py q)		py q	NO (p XOR q)	q	(NO p) O q	pag	p O (NO q)	p O q	1

Cambios de bits

Los cambios 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 se desplazan hacia la izquierda o hacia la derecha. Los registros en un procesador de computadora tienen un ancho fijo, por lo que algunos bits se "desplazarán" del registro en un extremo, mientras que el mismo número de bits se "desplazarán" desde el otro extremo; las diferencias entre los operadores de desplazamiento de bits radican en cómo determinan los valores de los bits desplazados.

Direccionamiento de bits

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 (elemento atómico), frecuentemente llamado byte, las operaciones de desplazamiento inducen un esquema de direccionamiento de los bytes al bits. Por lo tanto, las orientaciones "izquierda" y "derecha" se toman de la escritura estándar de números en una notación de valor posicional , de modo 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 los límites en ambos extremos del registro, las operaciones de desplazamiento aritméticas y lógicas 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:

Pedidos de little-endian :	un desplazamiento a la izquierda en 8 posiciones aumenta la dirección del byte en 1
Pedidos de little-endian:	un desplazamiento a la derecha en 8 posiciones disminuye la dirección del byte en 1
Pedidos de big endian :	un desplazamiento a la izquierda en 8 posiciones disminuye la dirección del byte en 1
Pedidos de big endian:	un desplazamiento a la derecha en 8 posiciones aumenta la dirección del byte en 1

Cambio aritmético

Artículo principal: Desplazamiento aritmético

Desplazamiento aritmético a la izquierda

Desplazamiento aritmético a la derecha

En un desplazamiento aritmético , los bits que se desplazan fuera de cada extremo se descartan. En un desplazamiento aritmético a 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, conservando así el signo del operando.

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

 00010111 (decimal +23) IZQUIERDA-MAYÚS= 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ó (quizás a 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. En ocasiones, los turnos múltiples se acortan a un solo turno en algunos dígitos. Por ejemplo:

 00010111 (decimal +23) CAMBIO IZQUIERDO EN DOS= 010111 00 (decimal +92)

Un desplazamiento aritmético a la izquierda por n equivale a multiplicar por 2 ⁿ (siempre que el valor no se desborde ), mientras que un desplazamiento aritmético a la derecha por n del valor del complemento a dos equivale a dividir por 2 ⁿ 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 da como resultado la división por 2 ⁿ y el redondeo hacia cero .

Cambio lógico

Artículo principal: Cambio lógico

Desplazamiento lógico a la izquierda

Cambio lógico a la derecha

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

Sin embargo, como el desplazamiento a la derecha lógico 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 a la derecha aritmético es ideal para números binarios en complemento a dos con signo .

Desplazamiento circular

Más información: Desplazamiento circular

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

Rotar

Desplazamiento circular a la izquierda o rotar

Desplazamiento circular a la derecha o rotar

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 a la izquierda es el valor que se desplazó hacia 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 usa con frecuencia en criptografía digital . ^{[ aclaración necesaria ]}

Rotar a través de acarreo

Girar a la izquierda a través del transporte

Girar a la derecha a través del transporte

Rotar a través de 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 llevar.

Una sola rotación a través de acarreo puede simular un cambio lógico o aritmético de una posición configurando la bandera de acarreo de antemano. Por ejemplo, si la bandera de acarreo contiene 0, entonces x RIGHT-ROTATE-THROUGH-CARRY-BY-ONEes un desplazamiento lógico a la derecha, y si la bandera 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, solo tienen que rotar y rotar a través del acarreo , y no se molestan con las instrucciones de cambio lógicas o aritméticas.

Rotar a través de acarreo es especialmente útil cuando se realizan cambios en números más grandes que el tamaño de la palabra nativa 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 de el segundo. Con rotación a través de acarreo, ese bit se "guarda" en la bandera de acarreo durante el primer turno, listo para cambiar durante el segundo turno sin ninguna preparación adicional.

En idiomas de alto nivel

Más información: Cambio circular § Implementación de turnos circulares

Familia C

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

x  =  y  <<  2 ;

asigna xel resultado de desplazarse yhacia la izquierda en 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 que el tamaño de la palabra es un comportamiento indefinido en C y C ++. ^{[2] [3]} Desplazar a la derecha un valor negativo está definido por la implementación y no es recomendado por las buenas prácticas de codificación; ^[4] el resultado de desplazar a 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 un int o long. Si el primer operando es de tipo uint o ulong, el desplazamiento a la derecha es un desplazamiento lógico. ^[5]

Turnos circulares

La familia C de lenguajes 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 turno. Se debe tener cuidado para garantizar que la declaración esté bien formada para evitar comportamientos indefinidos y ataques de tiempo en software con requisitos de seguridad. ^[6] Por ejemplo, una implementación ingenua que gira 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  -  n ));

Sin embargo, un cambio de 0bits da como resultado un comportamiento indefinido en la expresión de la derecha (x >> (32 - n))porque 32 - 0está 32y 32está fuera del rango [0 - 31]inclusive. Un segundo intento puede resultar en:

uint32_t  x  =  ...,  n  =  ...; uint32_t  y  =  n  ?  ( x  <<  n )  |  ( 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 el análisis de tiempo y el ataque, que a menudo no es aceptable en software de alta integridad. ^[6] Además, el código se compila en varias 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 bajo GCC y Clang, se recomienda lo siguiente. Muchos compiladores reconocen el patrón y el compilador emitirá una sola instrucción de rotación: ^{[7] [8] [9]}

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

También hay elementos 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 de Microsoft que sufre los problemas anteriores. ^[9] GCC no ofrece elementos intrínsecos de rotación. Intel también proporciona intrínsecos x86 .

Java

En Java , todos los tipos de enteros están firmados, por lo que los operadores " <<" y " >>" realizan cambios 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 el entero con signo, no hay " <<<" operador en Java.

Más detalles de los operadores de turno de Java: ^[10]

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

JavaScript

JavaScript utiliza operaciones bit a bit para evaluar cada una de dos o más unidades colocadas en 1 o 0. ^[12]

Pascal

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

x  : =  y  shl  2 ;

Otro

• popcount , utilizado en criptografía
• contar ceros iniciales

Aplicaciones

Las operaciones bit a bit son necesarias particularmente en la programación de bajo nivel, como controladores de dispositivos, gráficos de bajo nivel, ensamblaje de paquetes de protocolo de comunicaciones y decodificación.

Aunque las máquinas a menudo tienen instrucciones incorporadas eficientes para realizar operaciones aritméticas y lógicas, todas estas operaciones se pueden realizar combinando los operadores bit a bit y la prueba cero de varias formas. ^[13] Por ejemplo, aquí hay una implementación de pseudocódigo de la multiplicación del antiguo Egipto que muestra cómo multiplicar dos enteros arbitrarios ay b( amayor que b) usando solo cambios de bits y suma:

c  ←  0 mientras que  b  ≠  0  si  ( b  y  1 )  ≠  0  c  ←  c  +  un  izquierda  cambio  una  por  1  derecho  desplazamiento  b  por  1 retorno  c

Otro ejemplo es una implementación de pseudocódigo de suma, que muestra cómo calcular una suma de dos enteros ay busando operadores bit a bit y prueba de cero:

mientras que  un  ≠  0  c  ←  b  y  un  b  ←  b  xor  una  izquierda  cambio  c  por  1  un  ←  c retorno  b

Álgebra booleana

Artículo principal: álgebra de Boole

A veces es útil simplificar expresiones complejas compuestas 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 usa para simplificar expresiones complejas bit a bit.

Y

• x & y = y & x
• x & (y & z) = (x & y) & z
• x & 0xFFFF = x^[14]
• x & 0 = 0

• x & x = x

O

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

NO

• ~(~x) = x

XOR

• 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, XOR se puede componer usando las 3 operaciones básicas (Y, O, NO)

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

Otros

• 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)

Inversiones y resolución de ecuaciones

Puede ser 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.

• Tiene inversa
  • NO
  • XOR
  • Girar a la izquierda
  • Gira a la derecha
• No inverso
  • Y
  • O
  • Desplazar a la izquierda
  • Desplazar a la derecha

Orden de operaciones

Artículo principal: Operadores en C y C ++ § Operator_precedence

Las operaciones 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]
• << >>
• &
• ^
• |

Ver también

• Unidad aritmética lógica
• Manipulación de bits
• Bitboard
• Operaciones bit a bit en C
• Álgebra booleana (lógica)
• Doble incursión
• Encuentra el primer conjunto
• Mapa de Karnaugh
• Puerta lógica
• Operador lógico
• Tipo de datos primitivo

Referencias

1. "Blog de diseño de bajo consumo de CMicrotek" . CMicrotek . Consultado el 12 de agosto de 2015 .
2. JTC1 / SC22 / WG14 N843 "Lenguaje de programación C" , sección 6.5.7
3. "Operadores aritméticos - cppreference.com" . en.cppreference.com . Consultado el 6 de julio de 2016 .
4. "INT13-C. Utilice operadores bit a bit solo en operandos sin signo" . CERT: Estándares de codificación segura . Instituto de Ingeniería de Software, Universidad Carnegie Mellon . Consultado el 7 de septiembre de 2015 .
5. "Operador (Referencia de C #)" . Microsoft . Consultado el 14 de julio de 2013 .
6. "¿Rotación de tiempo casi constante que no viola los estándares?" . Stack Exchange Network . Consultado el 12 de agosto de 2015 .
7. "Optimización deficiente del idioma de rotación portátil" . Proyecto GNU GCC . Consultado el 11 de agosto de 2015 .
8. "¿Rotación circular que no viola el estándar C / C ++?" . Foros de desarrolladores de Intel . Consultado el 12 de agosto de 2015 .
9. "La constante no se propaga al ensamblaje en línea, da como resultado" la restricción 'I' espera una expresión constante entera "" . Proyecto LLVM . Consultado el 11 de agosto de 2015 .
10. La especificación del lenguaje Java, sección 15.19. Operadores de turno
11. "Capítulo 15. Expresiones" . oracle.com .
12. "JavaScript bit a bit" . W3Schools.com .
13. "Sintetizar operaciones aritméticas usando trucos de cambio de bits" . Bisqwit.iki.fi. 2014-02-15 . Consultado el 8 de marzo de 2014 .
14. A lo largo de este artículo, 0xFFFF significa que todos los bits de su tipo de datos deben establecerse en 1. El número exacto de bits depende del ancho del tipo de datos.
15. - es la negación aquí, no la resta
16. - aquí es resta, no negación

Enlaces externos

• La calculadora bit a bit en línea es compatible con AND, OR y XOR bit a bit
• División usando cambios de bits
• " Bitwise Operations Mod N " de Enrique Zeleny, Wolfram Demonstrations Project .
• " Tramas de composiciones de operaciones bit a bit " de Enrique Zeleny, The Wolfram Demonstrations Project.