C++ dispone de unos operadores que permiten trabajar con la representación en binario de los números enteros.
Operadores de desplazamiento (SHIFT)
Se trata de los operadores << y >> . a<<b significa "desplaza la representación en binario de a b bits hacia la izquierda", es decir, añade b ceros a la derecha de a en binario. Por ejemplo, 5<<2 da como resultado 20, ya que la representación en binario de 5 es 101 y moviéndolo dos posiciones hacia la izquierda se obtiene 10100, que es 20 en binario. El operador >> es lo mismo pero desplazando hacia la derecha y desechando los bits que queden fuera. Por ejemplo, 5>>2 da como resultado 1 , ya que la representación de 5 en binario es 101 y el "01" final se quita.
Notemos que a<<b $= a \cdot 2^b$ y a>>b $=\left\lfloor \frac{a}{2^b} \right\rfloor$. Pero hay que tener cuidado con el operador <<, ya que el resultado puede salirse de el número de bits máximo que se puede almacenar en nuestra variable y en ese caso ya no nos da $a \cdot 2^b$. Si usamos una variable de tipo entero sin signo, el comportamiento es el esperable y los bits que "se salen" por la izquierda se desechan al igual que sucede con el operador >>, pero si usamos un tipo de variable con signo tenemos un caso de "comportamiento indefinido" que debemos evitar. Tampoco se pueden utilizar operadores de desplazamiento en enteros negativos: en general, se recomienda usarlos solo en enteros sin signo.
Operadores lógicos bit a bit
Se trata de los operadores &, |, ^ y ~. Estos operadores realizan las operaciones lógicas and, or, xor y not, respectivamente, que utilizamos normalmente en operadores booleanos, pero esta vez aplicándolas a cada uno de los bits de los operandos. Por ejemplo, el resultado de 21&7 es 5, porque la representación en binario de 21 es 10101, la representación en binario de 7 es 00111, y 00101 es la cadena donde están a 1 los bits que están a 1 en ambas cadenas, es decir, los bits resultantes de aplicar la operación AND a cada uno de los bits. 21|7 daría como resultado 23 (10111), por ejemplo.
Aplicaciones (MÁSCARA DE BITS)
Este tipo de operadores se usa generalmente para sustituir vectores de booleanos a los que les queremos aplicar operaciones lógicas: en lugar de iterar por el vector con un bucle, almacenamos la información en la representación en binario de un entero y podemos utilizar los operadores bit a bit para obtener un código más corto y elegante. Esta técnica a veces se refiere con el nombre de máscara de bits, ya que sobre nuestro vector de bits aplicamos una máscara que los modifica (lo de máscara se entiende mejor con el operador &: podemos imaginarnos los bits a 1 como "agujeros" y por tanto aplicar el operador & es como "tapar" ciertos bits y "dejar ver" otros). Además del beneficio en brevedad de código, estos operadores suelen ser muy eficientes.
Nótese que el tamaño de nuestro vector está limitado por el número de bits de nuestro tipo de variable ($32$ en el caso de int y $64$ en el caso de long long, usualmente, aunque no está fijado). Para vectores más grandes, C++ ofrece el tipo bitset, que es un vector de bits con tamaño definido en tiempo de compilación muy optimizado y con algunas operaciones bit a bit implementadas, pero generalmente un vector de booleanos (que también está optimizado para que cada entrada ocupe un bit) sirve igualmente.
Añadir nuevo comentario