====== 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. 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 Si quisiéramos **iterar en los elementos de una máscara**, podríamos hacerlo de la siguiente forma. 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) ... } } Una forma de **iterar todos los subconjuntos de $n$ elementos** es for (int b = 0; b < (1 << n); b++) { // Hago lo que quiero con el subconjunto b } 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 int b = 0; do { // Hago lo que quiero con el subconjunto b, incluido en el subconjunto que representa x } while (b = (b-x)&x); 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$). 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 } 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).