Clase 14: Bitmask

Bitmask

Representacion de Enteros

Los 3 principales lenguajes de programación competitiva (C++, Java y Python) presentan las clases int (entero de 32-bits) y long (entero de 64-bits), los cuales la computadora maneja en base binaria.

La representación de estos números se da usando el bit máximo para signo y el resto de 31 o 63 bits para la representacion del valor del número. La técnica usada es llamada Complemento a dos, la cual no tiene problemas para representar los enteros positivos usando el bit de signo en 0 y el valor de manera natural, pero para los números negativos usa la siguiente forma:

\[ Valor(-x) = Inv(Valor(x-1)) \]

Esto en la parte del valor y el signo en 1. Ademas $Inv$ es el número que resulta de invertir cada bit de su argumento.

Debido a esta manera de representación, se da el hecho de que para los numeros no negativos se puede representar del $0$ al $2^{bits-1}-1$, mientras que los negativos serian todos los valores que toman aumentandoles 1 (usando la parte de la derecha de la ecuacion de arriba):

\[ Valor(-1) = Inv(Valor(1-1)) = Inv(Valor(0)) \] \[ Valor(-2) = Inv(Valor(2-1)) = Inv(Valor(1)) \]

Y asi seguimos hasta llegar a:

\[ Valor(-2^{bits-1}) = Inv(Valor(2^{bits-1}-1)) \]

Todos estos valores a la derecha estan correctamente definidos, por lo que el rango efectivo para los bits es:

\[ Rango = [-2^{bits-1},2^{bits-1}-1] \]

Manejo de bits

Los lenguajes de programación manejan operaciones (en general mas rápidas) para manipular los bits de los números enteros, entre ellas estan:

Desplazamiento de bits y negación: Permite usar un número entero y desplazar sus bits hacia la derecha o izquierda una cantidad de pasos o tomar los bits de un número e invertirlos.
Operaciones BITWISE: Operaciones logicas AND, OR y XOR.

Desplazamiento de bits y negación

El desplazamiento de bits se puede ver más como una multiplicación o división por una potencia de 2, su implementación es la siguiente:

int x = 10; //    000000000000000000000000000001010 Representacion de todos sus 32 bits
x = (x << 10); // 000000000000000000010100000000000 Desplazamiento de bits hacia la izquierda
int y = 20; //    000000000000000000000000000010100 Representacion de todos sus 32 bits
y = (y >> 10); // 000000000000000000000000000000000 Desplazamiento de bits hacia la derecha

Ahora, veamos lo que significa cada uno:

(n << y): Toma el numero $n$ y lo multiplica por $2^{y}$.
(n >> y): Toma el numero $n$ y lo vuelve el cociente de la division entera de $n$ por $2^{y}$, o tambien $floor\left(\frac{n}{2^{y}}\right)$

NOTA: La jerarquía del desplazamiento de bits es menor que la suma, por lo que $(1<<2+3)$ será interpretado como $(1<<5)$.

NOTA: Para variables long se debe usar $(1LL<<8)$ para que sea interpretada como long y no como int y asi no genere overflow.

Además, se pueden invertir los bits de un número entero usando lo siguiente:

int x = 1000; // 000000000000000000000001111101000 Representacion de todos sus 32 bits
x = ~x; //       111111111111111111111110000010111 Se invierten los bits del número

Operaciones BITWISE

BITWISE AND

Esta operación toma dos argumentos $a$ y $b$ para realizar en cada par de bits en la misma posición la función lógica Y:

&	1	0
1	1	0
0	0	0

Su implementacion es:

int x = 3;  // 011 Representación binaria
int y = 4;  // 100 Representación binaria
int z = x & y // 000 Resultado de BITWISE AND

BITWISE OR

Esta operación toma dos argumentos $a$ y $b$ para realizar en cada par de bits en la misma posición la función lógica O:

$\mid$	1	0
1	1	1
0	1	0

Su implementación es:

int x = 7;  // 111 Representación binaria
int y = 4;  // 100 Representación binaria
int z = x | y // 111 Resultado de BITWISE OR

BITWISE XOR

Esta operación toma dos argumentos $a$ y $b$ para realizar en cada par de bits en la misma posición la función logica O EXCLUSIVO:

^	1	0
1	0	1
0	1	0

Su implementación es:

int x = 10; // 1010 Representación binaria
int y = 4;  // 0100 Representación binaria
int z = x ^ y // 1110 Resultado de BITWISE XOR

Todos estos operadores también se pueden usar de manera acortada:

int x = 10;
x = (x&10); // Es equivalente a x &= 10;
x = (x|20); // Es equivalente a x |= 20;
x = (x^18); // Es equivalente a x ^= 18

Verificar si el bit de orden j esta prendido

Para determinar si un bit de orden $j$ esta prendido tenemos 2 posibles opciones, y las dos usan desplazamiento de bits:

Comprobar si $n$ & $2^{j}> 0$.

int x = 2018; // 000000000000000000000011111100010 Representación de todos sus 32 bits
bool ans = (x&(1<<3))>0; // Verificamos si el bit de orden 3 esta prendido, respuesta esperada: 0.

Comprobar si $floor\left(\frac{n}{2^{j}}\right)$ es impar (termina en 1 en su representacion binaria).

int x = 2018;        // 000000000000000000000011111100010 Representación de todos sus 32 bits
bool ans = (x>>3)&1; // 000000000000000000000000011111100 Luego de desplazarle 3 bits a la derecha
                     // el último bit es 0

Prender un bit

Para prender el bit de orden $j$ nos basta usar la funcion BITWISE OR de la siguiente manera:

int x = 1092; // 000000000000000000000010001000100 Representación de todos sus 32 bits
x |= (1<<16); // 000000000000000010000010001000100 Luego de prender el bit de orden j

Apagar un bit prendido o apagado

Para apagar un bit tenemos dos opciones, la primera (y más usada) es con el BITWISE XOR:

int x = 1092; // 000000000000000000000010001000100 Representación de todos sus 32 bits
x ^= 1<<2;    // 000000000000000000000010001000000 Apagamos el bit de orden 2

Esta técnica sirve solo si el bit esta prendido.

La segunda opcion es mas general, pues este prendido o apagado, vuelve el bit a 0.

int x = 1092;  // 000000000000000000000010001000100 Representación de todos sus 32 bits
x = x&~(1<<2); // 000000000000000000000010001000000 Apagamos el bit de orden 2

Usando Bitmask para Busqueda Completa

El principal uso de los bitmask para búsqueda completa es para representar subconjuntos.

Problema de la Mochila (0-1 Knapsack)

El clásico problema de la Mochila tiene el siguiente enunciado:

\[ \begin{array}{c}\text{Dada una mochila con capacidad }C\text{, considerando tener n objetos con sus respectivos pesos }w_{i}\text{ y valores }v_{i}\text{,} \\\text{determine el maximo valor posible de llevar en ella sin que la suma de los pesos de los objetos no sobrepase la capacidad.}\end{array} \]

Para los casos en que $n\leq 20$ se puede usar bitmask para hacer la representación de todos los objetos y cuales vamos a tomar, para procesar la máscara y maximizar como corresponda. La implementacion sería algo así:

for(int mask=0; mask<int(1<<n); mask++){
    int peso_actual = 0;
    int valor_actual = 0;
    for(int i=0; i<n; i++){
        if((mask>>i)&1){
            peso_actual += w[i];
            valor_actual += v[i];
        }
    }
    if(peso_actual <= C){
        ans = max(ans,valor_actual);
    }
}

Considerando que los limites de ambos for son constantes, entonces el algoritmo tendra una complejidad de O$(n\cdot2^{n})$.

Hallando el Least Significant One

A veces hacer la iteración completa de los $n$ elementos de un bitmask puede tomar un extra de tiempo que podríamos evitar si es que tuvieramos un método para solamente atravesar todos los 1 de la máscara sin pasar por los 0s. Por suerte, consideremos lo siguiente:

Tenemos un número $x$ con representacion binaria $b1a$, donde $a$ es el sufijo de la representacion binaria que esta compuesta por solamente 0s, mientras que b es el prefijo antes del 1 de menor orden en la máscara. Entonces, consideremos la representacion de $-x$:

\[ Valor(-x) = Inv(Valor(x-1)) = Inv(b0a^{C}) = b^{C}1 a \]

Donde $b^{C}$ es el complemento de $b$. Ahora, notemos que si realizamos un BITWISE AND entre ambos valores, se da que en el prefijo tendríamos $b$ & $b^{C} = 0$, en la posicion del 1 de menor orden tendríamos $1$ & $1 = 1$ y en el sufijo sería $a$ & $a=a$, pero al ser solamente 0s no hay problema con mantenerlo. Recordando el bit de signo, el cual diferirá entre ambos si fueran de diferente signo y considerando que el $0$ no tiene LSO:

$ x$ & $(-x) = 2^{} $

Esta tecnica nos ayudara a iterar a traves de todos los elementos validos de nuestra máscara y también al momento de analizar todos los subconjuntos posibles, lo último se verá más adelante.

Ahora, una vez que tengamos el LSO, podríamos quitarlo para que al obtener el LSO de la siguiente iteración ya no tengamos la misma respuesta. En realidad la manera más sencilla sería realizar algo como i -= i&(-i), pero las operaciones de bit son mas rápidas que las aritméticas, por lo que consideremos de nuevo la representación de $x$:

\[ x = b1a \]

Si le restamos 1 a $x$, entonces el LSO se vuelve 0 y todo el sufijo que le sigue se vuelve 1, entonces

\[ x-1 = b0a^{C} \]

Si realizamos un BITWISE AND entre ambos, claramente obtendremos el mismo valor original pero sin su LSO:

$ x$ & $(x-1) = b0a $

Para iterar por todos los elementos válidos, es útil mantener un arreglo extra (o un mapa) tal que pos[1<<i] = i, con el fin de obtener el orden del valor que tenga el LSO. Recordemos que el LSO nos da como resultado la máscara de 1 bit prendido y no el orden del bit mismo.

for(int mask = 0; mask < int(1<<n); mask++){
    int peso_actual = 0;
    int valor_actual = 0;
    for(int i=mask; i>0; i = i&(i-1)){ // Nuestra variacion quita el LSO cada vez y se detiene cuando llegamos a 0
        peso_actual += w[pos[i&(-i)]]; // Agregamos el peso del elemento del orden del LSO
        valor_actual += v[pos[i&(-i)]]; // Agregamos el valor del elemento del orden del LSO
    }
    if(peso_actual <= C){
        ans = max(ans,valor_actual);
    }
}

Ejercicios de calentamiento

Recorriendo todos los subconjuntos

Ahora que ya sabemos como analizar cada subconjunto, ¿Qué sucede si deseamos tomar valores asociados a cada posible subconjunto de cada máscara posible?. Por ejemplo, el conjunto $S = \{1,2,3,4,5,6\}$ tiene como subconjunto a $A = \{1,3,5\}$, y A posee los subconjuntos:

\[ Subsets(A) = \{\{1,3,5\},\{1,3\},\{1,5\},\{3,5\},\{1\},\{3\},\{5\},\phi\} \]

Ahora supongamos el siguiente problema:

\[ \begin{array}{c}\text{Hay }n\text{ alumnos en una clase, el profesor les va a pedir que formen grupos como deseen.} \\ \text{Cada alumno tiene un indice de capacidad no negativo, el cual depende de sus habilidades para realizar trabajos.}\\\text{El indice de comodidad de un grupo es igual a la funcion BITWISE AND de los indices de capacidad de sus integrantes.} \\\text{El potencial de un grupo es igual a la suma de los indices de comodidad de todos los posibles subgrupos que se puedan formar con sus integrantes,}\\\text{determine el potencial mas alto posible y con que integrantes se obtiene.}\end{array} \]

Con $1 \leq n \leq 13$ y $1 \leq Capacidad_{i} \leq 10^{9}$.

Realizar este problema con Fuerza Bruta tendría una implementación similar a esta:

for(int mask=0; mask<int(1<<n); mask++){
    for(int i=0; i<int(1<<n); i++){
        if((mask&i)==i) Potencial[mask] += Comodidad[i]; // Verificamos que sea subconjunto y agregamos
    }
}

Esto tendría complejidad de $O(4^{n})$.

Sin embargo, hay una manera que optimiza la búsqueda anterior:

for(int mask=0; mask<int(1<<n); mask++){
    Potencial[mask] += Comodidad[0]; // Agregamos la comodidad del conjunto vacío (inútil para este problema pero necesario)
    for(int i=mask; i>0; i=(i-1)&mask){
        Potencial[mask] += Comodidad[i]; // Agregamos la comodidad del subconjunto i
    }
}

Primero determinamos la complejidad, este algoritmo pasa por cada bit prendido en cada máscara y considera tomarlo o no tomarlo, por lo que si la máscara tiene $k$ bits prendidos, entonces habrán $2^{k}$ posibilidades, y por ende, iteraciones. Además, la cantidad de formas que se pueden distribuir $k$ bits en $n$ posiciones de manera indistinguida son $\binom{n}{k}$, por lo que se formaría una sumatoria del siguiente tipo:

$ = _{i=0}^{n}2{i} $

¿Es dificil de saber el resultado? Hagamos esto:

$ = _{i=0}^{n}2{i}1^{n-i} = (2+1)^{n} = 3^{n} $

Por lo que esta técnica tiene complejidad O($3^{n}$).

Ahora, ¿Por qué la iteracion interna recorre todos los subconjuntos de $mask$? Analicemos y probemos por inducción:

Proposición P(n): Dada una máscara $M$, el algoritmo itera en orden estrictamente decreciente sobre los valores $x$ tales que $x\in M$ y además $x$ difiere de $M$ solo hasta el bit de orden $n$. La veracidad de la proposición implicaría que el algoritmo si itera sobre todos los subconjuntos de la máscara $M$ tales que difieren de $M$ solo en los bits hasta el orden $n$ de manera estrictamente decreciente, estos los denotaremos como $S(M,n)$.

NOTA Usaremos $\oplus$ para la funcion BITWISE XOR.

Caso base P(0):

Si $M$ es par $\Longrightarrow$ En la primera iteración $i=M$ y recorre correctamente $S(M,0) = \{M\}$.
Si $M$ es impar $\Longrightarrow$ En la primera iteración $i=M$ y en la segunda iteración $i=M$ & $(M-1)$, por lo que apaga el bit de orden 0 y pasa por $M\oplus 1$. Entonces pasa por los elementos $S(M,0) = \{M,M\oplus1\}$ de manera decreciente.

Por lo que P(0) es verdadero.

Hipotesis inductiva: P(n) es verdadero, por lo que itera sobre los elementos de $S(M,n)$ de manera estrictamente decreciente.

Paso de inducción: Para probar si P(n+1) es verdadero, consideramos 2 casos:

El bit de orden $n+1$ de $M$ esta apagado: Trivialmente se cumple, pues $S(M,n+1) = S(M,n)$.
El bit de orden $n+1$ de $M$ esta prendido: Como $S(M,n)$ es atravesado de manera decreciente, entonces el último elemento tendrá apagados sus bits hasta el de orden $n$. Considerando que $M = b1a$ donde el 1 es el bit de orden $n+1$, entonces el último elemento tendría la forma $b1O$ donde $O$ es una secuencia de 0s de misma longitud que $a$. La siguiente iteración de $b1O$ sería $b0O^{C}\&M = b0a$, por lo que visitamos $S(M\oplus2^{n+1},n)$ inmediatamente después de visitar $S(M,n)$. Sin embargo, notemos que

\[ S(M,n+1) = S(M,n)\cup S(M\oplus2^{n+1},n) \]

Por lo que P(n+1) es verdadero y la proposición se cumple para todo entero.

Problemas por si alcanza el tiempo en clase

Hasta la proxima