Todos los números en la computadora son almacenados internamente como un número en 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 Tipos de Datos en la wiki.

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.

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.

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.

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.

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 aquí).

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)

[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$)

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.

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¹⁾ 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 Competitive Programmer's Handbook de Antii Laaksonen (está en inglés).