OIA-Wiki

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
====== Operaciones con Bits ======

===== Representación de Bits =====

Todos los números en la computadora son almacenados internamente como un número en [[algoritmos-oia:enteros:cambio-de-base|binario]], usualmente de 32 o 64 bits. Por ejemplo, en C++ el tipo ''int'' guarda números de 32 bits, y si tipeamos: ''int x = 43'', la computadora representará internamente a ''x'' por:

$$
x = \underbrace{00000000000000000000000000101011}_{32}
$$

Donde la representación debe entenderse con los bits menos significativos a la derecha. Es decir:

$$
43 = 2^0 \cdot {\bf 1} + 2^1 \cdot {\bf 1} + 2^2 \cdot {\bf 0} + 2^3 \cdot {\bf 1} + 2^4 \cdot {\bf 0} + 2^5 \cdot {\bf 1} + 2^6 \cdot {\bf 0} + \dots + 2^{30} \cdot {\bf 0} + 2^{31} \cdot {\bf 0}
$$

Sin embargo, si tipeamos ''long long x = 43'', la computadora representará internamente a ''x'' por:

$$
x = \underbrace{0000000000000000000000000000000000000000000000000000000000101011}_{64}
$$

Ya que

$$
43 = 2^0 \cdot {\bf 1} + 2^1 \cdot {\bf 1} + 2^2 \cdot {\bf 0} + 2^3 \cdot {\bf 1} + 2^4 \cdot {\bf 0} + 2^5 \cdot {\bf 1} + 2^6 \cdot {\bf 0} + \dots + 2^{62} \cdot {\bf 0} + 2^{63} \cdot {\bf 0}
$$


Para más información sobre distintos tipos de enteros, pueden ingresar a [[curso-cpp:mas-tipos|Tipos de Datos]] en la wiki.

===== Operaciones lógicas bit a bit =====

==== Operación AND ====

Dados dos números $x$ e $y$, $x {\small \textbf{ AND } } y$ nos da otro número que tiene un $1$ en el desarrollo binario exactamente en las posiciones donde **tanto $x$ como $y$ tienen un $1$** en sus respectivos desarrollos binarios.

Ejemplo:

$$
\begin{matrix}
   & 10110 & (22) \\ 
\& & 11010 & (26) \\ \hline
=  & 10010 & (18)
\end{matrix}
$$

En C++, si tenemos dos enteros ''x'' e ''y'', podemos escribir $x {\small \textbf{ AND } } y$ como '' x & y''.

==== Operación OR ====

Dados dos números $x$ e $y$, $x {\small \textbf{ OR } } y$ nos da otro número que tiene un $1$ en el desarrollo binario exactamente en las posiciones donde **alguno de $x$ e $y$ tiene un $1$** en sus respectivos desarrollos binarios (posiblemente ambos).

Ejemplo:

$$
\begin{matrix}
  & 10110 & (22) \\ 
| & 11010 & (26) \\ \hline
= & 11110 & (30)
\end{matrix}
$$

En C++, si tenemos dos enteros ''x'' e ''y'', podemos escribir $x {\small \textbf{ OR } } y$ como ''x | y''.

==== Operación XOR ====

Dados dos números $x$ e $y$, $x {\small \textbf{ XOR } } y$ nos da otro número que tiene un $1$ en el desarrollo binario exactamente en las posiciones donde **solamente uno de $x$ e $y$ tiene un $1$** en su desarrollo binario.

Ejemplo:

$$
\begin{matrix}
       & 10110 & (22) \\ 
\wedge & 11010 & (26) \\ \hline
     = & 01100 & (12)
\end{matrix}
$$

En C++, si tenemos dos enteros ''x'' e ''y'', podemos escribir $x {\small \textbf{ XOR } } y$ como '' x ^ y''.

==== Operación NOT ====

Dado un número $x$,   ${\small \textbf{NOT } } x$ nos da otro número que **invierte cada bit del desarrollo binario de $x$**. Es decir, nos devuelve un número con un $1$ donde el desarrollo de $x$ tiene un $0$ y viceversa (un $0$ donde hay un $1$).

Cuidado, si usamos un tipo de enteros con signo, también da vuelta el //bit de signo//.

Ejemplo (trabajando con enteros de 32 bits con signo, o sea ''int'' en C++):

$$
\begin{matrix}
\sim & 00000000000000000000000000011101 & (29) \\ \hline
   = & 11111111111111111111111111100010 & (-30)
\end{matrix}
$$

En C++, si tenemos un entero ''x'' y queremos negarlo, es decir ${\small \textbf{NOT } } x$, podemos escribirlo como '' ~x''.

===== Desplazamiento de bits (Shift de bits) =====

Hay dos tipos de desplazamientos que podemos hacer. Un **shift a izquierda** de $k$ posiciones a un número $x$, **agrega $k$ ceros** en la representación binaria al final del número. En C++ se nota con '' x << k ''. 
De manera análoga, un **shift a derecha** de $k$ posiciones a un número $x$, **remueve los últimos $k$ bits** del desarrollo binario del número. En C++ se nota con '' x >> k ''.

Ejemplo:

$$
\begin{matrix}
14      & = & 0000000000001110 & (14) \\
14 << 2 & = & 0000000000111000 & (56) \\
14 >> 2 & = & 0000000000000011 & (3) 
\end{matrix}
$$

Una **aplicación muy común** de los shift de bits es **obtener el k-ésimo bit de un número**. Usando que ''1 << k'' nos da el número $2^k$, cuya representación tiene solamente el k-ésimo bit igual a $1$, podemos acceder al k-ésimo bit de un número $x$ en C++ haciendo '' x & (1 << k) '' (si el k-ésimo bit es 1, nos devuelve $2^k$. Entonces si quisiéramos saber solo si es 1 o no, debemos escribir algo como: '' (x & (1 << k)) != 0 '').

Si estamos **trabajando con 64 bits** hay que tener cuidado y escribir ''1LL << k'' si queremos tener al número $2^k$ con $k \geq 31$ (el motivo de esto se explica [[curso-cpp:mas-tipos#tipo_de_un_literal_entero|aquí]]). 

===== Operaciones bit a bit (más avanzadas) =====

Dado un número $x$, combinando operaciones de bits podemos generar otros números que guardan una relación con $x$ en su desarrollo binario que pueden ser de gran utilidad.

   * Escribir un $1$ en la k-ésima posición del desarrollo binario de $x \quad$ ''x | (1 << k) ''
   * Escribir un $0$ en la k-ésima posición del desarrollo binario de $x \quad$ '' x & ~(1 << k) ''
   * Invertir el bit en la k-ésima posición del desarrollo binario de $x \quad$ '' x ^ (1 << k) ''
   * Poner en $0$ el bit menos significativo de $x$ que tiene un $1 \quad$ '' x & (x-1) ''
   * Poner en $0$ todos los bits, salvo el menos significativo (más a la derecha) de $x$ que tiene un $1 \quad$ '' x & (-x) ''
   * Invertir todos los bits que vienen después del menos significativo de $x$ que tiene un $1 \quad$ '' x | (x-1) ''

FIXME [definir LSB (least significant bit) y reescribir lo anterior más prolijo en términos del LSB]

Notar que si quisiéramos ver si $x$ **es una potencia de 2**, podemos hacerlo viendo si '' (x & (x-1)) == 0 '' (Si asumimos $x > 0$)

==== Funciones Adicionales ====

En C++ tenemos las siguientes funciones que pueden resultar muy útiles al trabajar con enteros de 32 bits.


   * $\texttt{__builtin_clz(x)}$ Nos da la cantidad de ceros consecutivos **al comienzo** del desarrollo binario de $x$ 
   * $\texttt{__builtin_ctz(x)}$ Nos da la cantidad de ceros consecutivos **al final** del desarrollo binario de $x$  
   * $\texttt{__builtin_popcount(x)}$ Nos da la cantidad bits iguales a $1$ que hay en el desarrollo de $x$
   * $\texttt{__builtin_parity(x)}$ Nos da la paridad ($0$ si es par, $1$ si es impar) de la cantidad de bits igual a $1$ que hay en el desarrollo de $x$.

Si estamos **trabajando con enteros de 64 bits** y queremos usar estas funciones, podemos hacerlo agregando ''ll'' (por ''long long'') al final de la función. Por ejemplo $\texttt{__builtin_clzll(29)}$ nos devuelve $59$ como respuesta, porque $(29)_2 = 11101$, así que tiene $59$ bits en $0$ antes de esos $5$ bits finales. En cambio, $\texttt{__builtin_clz(29)}$ devuelve $27$, ya que solamente hay $32$ bits en total.

===== Representación de Conjuntos (máscaras de bits) =====

Si tenemos un conjunto de $n$ elementos dispuesto en un arreglo $A$, el conjunto $\{ 0,1,2,\dots, n-1 \}$ representa los índices de los elementos de nuestro arreglo. De esta forma, cada subconjunto de $\{ 0,1,2,\dots, n-1 \}$, representa un subconjunto de nuestro arreglo original. Si $n \leq 31$, usando un entero de 32 bits, podemos representar a cada subconjunto de $\mathcal{A} \subseteq \{ 0,1,2,\dots, n-1 \}$ con un entero: asociaremos cada subconjunto $\mathcal{A}$ con el entero no negativo cuyo desarrollo binario tenga un $1$ exactamente en las posiciones correspondientes a los elementos de $\mathcal{A}$.

Ejemplo: Si $ \mathcal{A} = \{ 1,3,4,8 \}$, entonces, $\mathcal{A}$ se corresponde con :

$$
a = 00000000000000000000\overset{\cdots}{0}0\overset{9}{0}\overset{8}{1}\overset{7}{0}\overset{6}{0}\overset{5}{0}\overset{4}{1}\overset{3}{1}\overset{2}{0}\overset{1}{1}\overset{0}{0} = 282
$$

Entonces, utilizando las operaciones de bits que vimos más arriba podemos describir las operaciones entre conjuntos de manera práctica y compacta. La siguiente tabla muestra un resumen de estas operaciones: $a$ es la //máscara de bits//((Se llama así a un entero que representa un conjunto mediante sus bits, de la forma ya explicada)) que representa al conjunto $\mathcal{A}$, y $b$ es la máscara que representa al conjunto $\mathcal{B}$.
$$
\begin{matrix}
                    & \text{conjuntos}                  & \text{bits}   \\ \hline
\text{intersección} & \mathcal{A}  \cap \mathcal{B}     & a \& b        \\ 
\text{unión}        & \mathcal{A}  \cup \mathcal{B}     & a | b         \\ 
\text{complemento}  & \mathcal{A}^{c}                   & \sim a        \\ 
\text{diferencia}   & \mathcal{A} \setminus \mathcal{B} & a \& (\sim b) 
\end{matrix}
$$


Notar que si quisiéramos **generar el subconjunto** $\mathcal{A} = \{ 1,3,4,8 \}$ en C++ y representarlo en un entero, podemos hacerlo con el siguiente código utilizando las operaciones que vimos anteriormente.

<code cpp>
int x = 0;
x |= (1 << 1); // pongo en 1 el bit correspondiente a la posición 1
x |= (1 << 3); // pongo en 1 el bit correspondiente a la posición 3
x |= (1 << 4); // pongo en 1 el bit correspondiente a la posición 4
x |= (1 << 8); // pongo en 1 el bit correspondiente a la posición 8
</code>

Si quisiéramos **iterar en los elementos de una máscara**, podríamos hacerlo de la siguiente forma. 

<code cpp>
for (int i = 0; i < n; i++)
{
   if ((x & (1 << i)) != 0 ) // Si el i-ésimo bit tiene un 1...
   {
      // Hago lo que quiero con i (o A[i] si queremos usar los valores) ...
   }
}
</code>

Una forma de **iterar todos los subconjuntos de $n$ elementos** es

<code cpp>
for (int b = 0; b < (1 << n); b++)
{
   // Hago lo que quiero con el subconjunto b
}
</code>

Si tenemos una máscara $x$ que ya representa a un conjunto $\mathcal{X}$, podemos **iterar en todos los subconjuntos de los elementos de esa máscara $x$** de la siguiente forma

<code cpp>
int b = 0;
do
{
   // Hago lo que quiero con el subconjunto b, incluido en el subconjunto que representa x
}
while (b = (b-x)&x);
</code>

La versión anterior itera las máscaras correspondientes a todos los subconjuntos, de menor a mayor. La siguiente en cambio los recorre de mayor a menor, y no incluye ni la máscara $x$ ni la máscara $0$ (correspondientes a $\mathcal{X}$ y a $\varnothing$).


<code cpp>
for (int b = (x-1)&x; b != 0 ; b=(b-1)&x)
{
    // Hago lo que quiero con el subconjunto b, incluido en el subconjunto que representa x
}
</code>





Todas las ideas explayadas en este artículo, se encuentran en el capítulo 10 del siguiente libro [[ https://cses.fi/book.pdf | Competitive Programmer's Handbook]] de Antii Laaksonen (está en inglés).
OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Herramientas de la página
