Bitmasks
Prerequisiti
- Rappresentazione in base 2
- Algebra booleana
Introduzione
Immagino che tutti sappiamo che all’interno del calcolatore le variabili siano formate da bit (0 e 1), quello che magari non tutti ci siamo chiesti è come sfruttare questa informazione a nostro vantaggio. In questo post cercherò di aiutarvi, per quanto mi è possibile, nella scrittura ed ottimizzazione di codici che sarebbero risultati ostici senza questa tecnica, tramite l’utilizzo dei bitwise operators.
Bitwise operator
Pensate ad un operatore logico booleano, esso è generalmente usato per operare su variabili booleane (c’è anche scritto in effetti), i bitwise operators invece lavorano su qualunque tipo di intero, eseguono le stesse operazioni degli operatori logici, ma le fanno in ordine bit per bit. Facciamo un esempio: supponiamo di avere due unsigned char x = 85 e y = 204 (ho scelto i char per comodità di scrittura, essendo composti solo da 8 bit, funzionano anche gli int e i long long, sia signed che unsigned).
Allora (bitwise AND):
x&y = 68, infatti
01010101 AND
11001100 =
--------
01000100 = 68
Dunque quando andremo a trattare con le bitmask dobbiamo ragionare solo con la natura binaria del numero, infatti la base 10 ci aiuta ben poco nel comprendere quello che sta succedendo.
I bitwise operator sono &(AND), |(OR), ^(XOR), ~(NOT). Inoltre abbiamo anche <<(left shift) e >>(right shift), che, come suggerisce il nome, servono a spostare i bit di un numero verso sinistra o verso destra (i bit che “escono dai bordi” vengono persi), tradotto: servono a moltiplicare o a dividere il numero per una potenza di 2, x<<a = x\cdot2^a, x>>a = \frac{x}{2^a} (ovviamente divisione intera).
Operazioni base
Settare l’i_esimo bit a 1
Con i_esimo bit si intende il bit della potenza 2^i, per settare ad 1 l’i_esimo bit di x basta scrivere x |= 1<<i, vediamo perché:
Fare 00000001 << i equivale ad ottenere un numero con 1 nell’i_esimo bit e 0 in tutti gli altri, dato che lo 0 è elemento neutro per l’OR tutti i bit di x diversi dall’i_esimo non cambieranno, l’i_esimo diventerà 1.
Settare l’i_esimo bit a 0
Stesso concetto di prima ma l’operazione è x &= ~(1<<i), infatti ~(1<<i) è 1<<i con tutti i bit invertiti e 1 è elemento neutro dell’&.
Cambiare lo stato dell’i_esimo bit
x ^= 1<<i
Controllare se l’i_esimo bit è 1
Basta scrivere if(x&(1<<i)), infatti se l’& vale 0 l’if sarà falso e l’& vale 0 quando l’i_esimo bit di x vale 0.
Operazioni precedenti su più bit consecutivi
Supponiamo di voler settare ad 1 tutti i bit tra i e j (con i<=j), ci basterà fare x |= (1<<(j+1)) - (1<<i) (mi raccomando con gli shift riempite tutto di parentesi 
), se infatti facendo la sottrazione (1<<(j+1)) - (1<<i) in base 2 ci si accorge che il risultato ha tutti i bit tra i e j (compresi) ad 1, mentre il resto sono a 0.
Analogamente è applicabile per le altre operazioni.
Utilità
Una grande applicazione delle bitmasks è quella di poter rappresentare comodamente i sottoinsiemi di un insieme di pochi elementi. Prendiamo S=\{1,2,3,4,5,6,7,8\} e A\subseteq S, cerchiamo adesso di rappresentare A come un intero a che ha l’i_esimo bit a 1 se l’i_esimo elemento di S appartiene ad A, a 0 altrimenti (con i_esimo elemento di S si inende nell’ordine in cui sono stati scritti, partendo da 0). Quindi se A=\{1,3,7\} abbiamo a=01000101.
Questa scrittura ci permette di assegnare ad ogni sottoinsieme un numero che lo rappresenta, dunque possiamo salvarci molto semplicemente in un vettore le informazioni di tutti i sottoinsiemi di S, utilissimo in certi tipi di dp. Inoltre così facendo abbiamo ben definite le operazioni tra insiemi:
- Aggiungere l’i_esimo elemento ad A:
a |= 1<<i. - Più in generale, unione degli insiemi A e B:
a|b. - Intersezione degli insiemi A e B:
a&b - Togliere l’i_esimo elemento di A:
a &= ~(1<<i) - Sapere se B è sottoinsieme di A:
if(a&b == b)
Iterare su tutti i sottoinsiemi di A: questa è una domanda un po’ più tricky, il primo approccio sarebbe quello di iterare su tutti i sottoinsiemi B di S per poi chiedersi se B\subseteq A in qusesto modo
for(int b = 0; b <= s; b++){//s è il numero corrispondente all'insieme S
if(a&b == b){
...
}
}
Tuttavia la complessità di questo ciclo è O(2^{|S|}) (dove |S| è il numero di elementi di S), si può fare di meglio, in O(2^{|A|}), complessità ottimale dato che 2^{|A|} è proprio il numero di sottoisiemi di A. Basta questo for:
for(int b = a; b >= 0; b = (b - 1)&a){
...
}
Ma perché funziona? Vedetelo come un modo di eliminare i bit inutili, senza però saltare nessun sottoinsieme di A, infatti il for è dall’alto verso il basso e per saltare un sottoinsieme qualsiasi l’&a dovrebbe mettere dei bit a 0, tuttavia l’&a mette a 0 solo i bit che non appartengono ad a, quindi vengono saltati tutti e i soli sottoinsiemi che non sono contenuti in A, lasciando quelli contenuti.
Conclusioni
Mi rendo conto della disorganizzazione del post, che non si capisce bene dove vada a parare, tuttavia le bitmasks non sono un argomento specifico come un algoritmo particolare o una data structure impressionante, è molto più legato alla logica e alla discrezione del programmatore il come e quando usarle, l’argomento voleva essere quindi una serie di spunti ed esempi sui quali fondare le basi.
N.B. Sebbene abbia usato gli insiemi per definire le applicazioni delle bitmasks esse non vanno usate solo in quel caso, in generale, se pensate che un algoritmo possa avere una complessità di 2^n o se nel problema vengono fatte operazioni in base 2 su numeri non troppo grandi (che entrano in un long long), potrebbe essere sensato usare le bitmasks.
Ovviamente per qualsiasi cosa non esitate a chiedere 
(anche se nessuno risponde ai nostri post mi sento triste vi prego fate qualcosa)
Problemi
CMS - Crazy Lights Hotel
Codeforces - F. Two Pizzas
Codeforces - E. Team Building