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 normalmente usan 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
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 la 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
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
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
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.
Equivalentes matemáticos
Asumiendo , para los enteros no negativos, las operaciones bit a bit se pueden escribir de la siguiente manera:
Truth table for all binary logical operators
There are 16 possible truth functions of two binary variables; this defines a truth table.
Here is the bitwise equivalent operations of two bits P and Q:
p | q | F0 | NOR1 | Xq2 | ¬p3 | ↛4 | ¬q5 | XOR6 | NAND7 | AND8 | XNOR9 | q10 | If/then11 | p12 | Then/if13 | OR14 | T15 | ||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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 | ||
Bitwise equivalents | 0 | NOT (p OR q) | (NOT p) AND q | NOT p | p AND (NOT q) | NOT q | p XOR q | NOT (p AND q) | p AND q | NOT (p XOR q) | q | (NOT p) OR q | p | p OR (NOT q) | p OR q | 1 |
Cambios de bits
The bit shifts are sometimes considered bitwise operations, because they treat a value as a series of bits rather than as a numerical quantity. In these operations, the digits are moved, or shifted, to the left or right. Registers in a computer processor have a fixed width, so some bits will be "shifted out" of the register at one end, while the same number of bits are "shifted in" from the other end; the differences between bit shift operators lie in how they determine the values of the shifted-in bits.
Bit addressing
If the width of the register (frequently 32 or even 64) is larger than the number of bits (usually 8) of the smallest addressable unit (atomic element), frequently called byte, the shift operations induce an addressing scheme from the bytes to the bits. Thereby the orientations "left" and "right" are taken from the standard writing of numbers in a place-value notation, such that a left shift increases and a right shift decreases the value of the number ― if the left digits are read first this makes up a big-endian orientation. Disregarding the boundary effects at both ends of the register, arithmetic and logical shift operations behave the same, and a shift by 8 bit positions transports the bit pattern by 1 byte position in the following way:
| a left shift by 8 positions increases the byte address by 1 |
| a right shift by 8 positions decreases the byte address by 1 |
| a left shift by 8 positions decreases the byte address by 1 |
| a right shift by 8 positions increases the byte address by 1 |
Arithmetic shift
In an arithmetic shift, the bits that are shifted out of either end are discarded. In a left arithmetic shift, zeros are shifted in on the right; in a right arithmetic shift, the sign bit (the MSB in two's complement) is shifted in on the left, thus preserving the sign of the operand.
This example uses an 8-bit register, interpreted as two's complement:
00010111 (decimal +23) LEFT-SHIFT= 00101110 (decimal +46)
10010111 (decimal −105) RIGHT-SHIFT= 11001011 (decimal −53)
In the first case, the leftmost digit was shifted past the end of the register, and a new 0 was shifted into the rightmost position. In the second case, the rightmost 1 was shifted out (perhaps into the carry flag), and a new 1 was copied into the leftmost position, preserving the sign of the number. Multiple shifts are sometimes shortened to a single shift by some number of digits. For example:
00010111 (decimal +23) LEFT-SHIFT-BY-TWO= 01011100 (decimal +92)
A left arithmetic shift by n is equivalent to multiplying by 2n (provided the value does not overflow), while a right arithmetic shift by n of a two's complement value is equivalent to dividing by 2n and rounding toward negative infinity. If the binary number is treated as ones' complement, then the same right-shift operation results in division by 2n and rounding toward zero.
Logical shift
In a logical shift, zeros are shifted in to replace the discarded bits. Therefore, the logical and arithmetic left-shifts are exactly the same.
However, as the logical right-shift inserts value 0 bits into the most significant bit, instead of copying the sign bit, it is ideal for unsigned binary numbers, while the arithmetic right-shift is ideal for signed two's complement binary numbers.
Circular shift
Another form of shift is the circular shift, bitwise rotation or bit rotation.
Rotate
In this operation, sometimes called rotate no carry, the bits are "rotated" as if the left and right ends of the register were joined. The value that is shifted into the right during a left-shift is whatever value was shifted out on the left, and vice versa for a right-shift operation. This is useful if it is necessary to retain all the existing bits, and is frequently used in digital cryptography.[clarification needed]
Rotate through carry
Rotate through carry is a variant of the rotate operation, where the bit that is shifted in (on either end) is the old value of the carry flag, and the bit that is shifted out (on the other end) becomes the new value of the carry flag.
A single rotate through carry can simulate a logical or arithmetic shift of one position by setting up the carry flag beforehand. For example, if the carry flag contains 0, then x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE
is a logical right-shift, and if the carry flag contains a copy of the sign bit, then x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE
is an arithmetic right-shift. For this reason, some microcontrollers such as low end PICs just have rotate and rotate through carry, and don't bother with arithmetic or logical shift instructions.
Rotate through carry is especially useful when performing shifts on numbers larger than the processor's native word size, because if a large number is stored in two registers, the bit that is shifted off one end of the first register must come in at the other end of the second. With rotate-through-carry, that bit is "saved" in the carry flag during the first shift, ready to shift in during the second shift without any extra preparation.
In high-level languages
C-family
In C-family languages, the logical shift operators are "<<
" for left shift and ">>
" for right shift. The number of places to shift is given as the second argument to the operator. For example,
x = y << 2;
assigns x
the result of shifting y
to the left by two bits, which is equivalent to a multiplication by four.
Shifts can result in implementation-defined behavior or undefined behavior, so care must be taken when using them. The result of shifting by a bit count greater than or equal to the word's size is undefined behavior in C and C++.[2][3] Right-shifting a negative value is implementation-defined and not recommended by good coding practice;[4] the result of left-shifting a signed value is undefined if the result cannot be represented in the result type.[2]
In C#, the right-shift is an arithmetic shift when the first operand is an int or long. If the first operand is of type uint or ulong, the right-shift is a logical shift.[5]
Circular shifts
The C-family of languages lack a rotate operator (although C++20 provides std::rotl
and std::rotr
), but one can be synthesized from the shift operators. Care must be taken to ensure the statement is well formed to avoid undefined behavior and timing attacks in software with security requirements.[6] For example, a naive implementation that left rotates a 32-bit unsigned value x
by n
positions is simply:
uint32_t x = ..., n = ...;uint32_t y = (x << n) | (x >> (32 - n));
However, a shift by 0
bits results in undefined behavior in the right hand expression (x >> (32 - n))
because 32 - 0
is 32
, and 32
is outside the range [0 - 31]
inclusive. A second try might result in:
uint32_t x = ..., n = ...;uint32_t y = n ? (x << n) | (x >> (32 - n)) : x;
where the shift amount is tested to ensure it does not introduce undefined behavior. However, the branch adds an additional code path and presents an opportunity for timing analysis and attack, which is often not acceptable in high integrity software.[6] In addition, the code compiles to multiple machine instructions, which is often less efficient than the processor's native instruction.
To avoid the undefined behavior and branches under GCC and Clang, the following is recommended. The pattern is recognized by many compilers, and the compiler will emit a single rotate instruction:[7][8][9]
uint32_t x = ..., n = ...;uint32_t y = (x << n) | (x >> (-n & 31));
There are also compiler-specific intrinsics implementing circular shifts, like _rotl8, _rotl16, _rotr8, _rotr16 in Microsoft Visual C++. Clang provides some rotate intrinsics for Microsoft compatibility that suffers the problems above.[9] GCC does not offer rotate intrinsics. Intel also provides x86 Intrinsics.
Java
In Java, all integer types are signed, so the "<<
" and ">>
" operators perform arithmetic shifts. Java adds the operator ">>>
" to perform logical right shifts, but since the logical and arithmetic left-shift operations are identical for signed integer, there is no "<<<
" operator in Java.
More details of Java shift operators:[10]
- The operators
<<
(left shift),>>
(signed right shift), and>>>
(unsigned right shift) are called the shift operators. - The type of the shift expression is the promoted type of the left-hand operand. For example,
aByte >>> 2
is equivalent to((int) aByte) >>> 2
. - If the promoted type of the left-hand operand is int, only the five lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & with the mask value 0x1f (0b11111).[11] The shift distance actually used is therefore always in the range 0 to 31, inclusive.
- If the promoted type of the left-hand operand is long, then only the six lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & with the mask value 0x3f (0b111111).[11] The shift distance actually used is therefore always in the range 0 to 63, inclusive.
- The value of
n >>> s
is n right-shifted s bit positions with zero-extension. - In bit and shift operations, the type
byte
is implicitly converted toint
. If the byte value is negative, the highest bit is one, then ones are used to fill up the extra bytes in the int. Sobyte b1 = -5; int i = b1 | 0x0200;
will result ini == -5
.
JavaScript
JavaScript uses bitwise operations to evaluate each of two or more units place to 1 or 0.[12]
Pascal
In Pascal, as well as in all its dialects (such as Object Pascal and Standard Pascal), the logical left and right shift operators are "shl
" and "shr
", respectively. Even for signed integers, shr
behaves like a logical shift, and does not copy the sign bit. The number of places to shift is given as the second argument. For example, the following assigns x the result of shifting y to the left by two bits:
x := y shl 2;
Otro
- popcount, used in cryptography
- count leading zeros
Aplicaciones
Bitwise operations are necessary particularly in lower-level programming such as device drivers, low-level graphics, communications protocol packet assembly, and decoding.
Although machines often have efficient built-in instructions for performing arithmetic and logical operations, all these operations can be performed by combining the bitwise operators and zero-testing in various ways.[13] For example, here is a pseudocode implementation of ancient Egyptian multiplication showing how to multiply two arbitrary integers a
and b
(a
greater than b
) using only bitshifts and addition:
c ← 0while b ≠ 0 if (b and 1) ≠ 0 c ← c + a left shift a by 1 right shift b by 1return c
Another example is a pseudocode implementation of addition, showing how to calculate a sum of two integers a
and b
using bitwise operators and zero-testing:
while a ≠ 0 c ← b and a b ← b xor a left shift c by 1 a ← creturn b
álgebra de Boole
Sometimes it is useful to simplify complex expressions made up of bitwise operations. For example, when writing compilers. The goal of a compiler is to translate a high level programming language into the most efficient machine code possible. Boolean algebra is used to simplify complex bitwise expressions.
AND
x & y = y & x
x & (y & z) = (x & y) & z
x & 0xFFFF = x
[14]x & 0 = 0
x & x = x
OR
x | y = y | x
x | (y | z) = (x | y) | z
x | 0 = x
x | 0xFFFF = 0xFFFF
x | x = x
NOT
~(~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
Additionally, XOR can be composed using the 3 basic operations (AND, OR, NOT)
a ^ b = (a | b) & (~a | ~b)
a ^ b = (a & ~b) | (~a & b)
Others
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)
Inverses and solving equations
It can be hard to solve for variables in boolean algebra, because unlike regular algebra, several operations do not have inverses. Operations without inverses lose some of the original data bits when they are performed, and it is not possible to recover this missing information.
- Has Inverse
- NOT
- XOR
- Rotate Left
- Rotate Right
- No Inverse
- AND
- OR
- Shift Left
- Shift Right
Order of operations
Operations at the top of this list are executed first. See the main article for a more complete list.
( )
~ -
[15]* / %
+ -
[16]<< >>
&
^
|
Ver también
- Arithmetic logic unit
- Bit manipulation
- Bitboard
- Bitwise operations in C
- Boolean algebra (logic)
- Double dabble
- Find first set
- Karnaugh map
- Logic gate
- Logical operator
- Primitive data type
Referencias
- ^ "CMicrotek Low-power Design Blog". CMicrotek. Retrieved 2015-08-12.
- ^ a b JTC1/SC22/WG14 N843 "C programming language", section 6.5.7
- ^ "Arithmetic operators - cppreference.com". en.cppreference.com. Retrieved 2016-07-06.
- ^ "INT13-C. Use bitwise operators only on unsigned operands". CERT: Secure Coding Standards. Software Engineering Institute, Carnegie Mellon University. Retrieved 2015-09-07.
- ^ "Operator (C# Reference)". Microsoft. Retrieved 2013-07-14.
- ^ a b "Near constant time rotate that does not violate the standards?". Stack Exchange Network. Retrieved 2015-08-12.
- ^ "Poor optimization of portable rotate idiom". GNU GCC Project. Retrieved 2015-08-11.
- ^ "Circular rotate that does not violate C/C++ standard?". Intel Developer Forums. Retrieved 2015-08-12.
- ^ a b "Constant not propagated into inline assembly, results in "constraint 'I' expects an integer constant expression"". LLVM Project. Retrieved 2015-08-11.
- ^ The Java Language Specification, section 15.19. Shift Operators
- ^ a b "Chapter 15. Expressions". oracle.com.
- ^ "JavaScript Bitwise". W3Schools.com.
- ^ "Synthesizing arithmetic operations using bit-shifting tricks". Bisqwit.iki.fi. 2014-02-15. Retrieved 2014-03-08.
- ^ Throughout this article, 0xFFFF means that all the bits in your data type need to be set to 1. The exact number of bits depends on the width of the data type.
- ^ - is negation here, not subtraction
- ^ - is subtraction here, not negation
enlaces externos
- Online Bitwise Calculator supports Bitwise AND, OR and XOR
- Division using bitshifts
- "Bitwise Operations Mod N" by Enrique Zeleny, Wolfram Demonstrations Project.
- "Plots Of Compositions Of Bitwise Operations" by Enrique Zeleny, The Wolfram Demonstrations Project.