Maschere di bit: impostare, azzerare, invertire e verificare

Una maschera di bit è un intero usato per selezionare, modificare o verificare bit specifici di un altro intero. La maschera contiene 1 nelle posizioni di interesse e 0 nelle altre. In combinazione con gli operatori bitwise, le maschere consentono di eseguire operazioni precise sui bit senza modificare gli altri.

Le quattro operazioni fondamentali con le maschere sono: impostare un bit (attivarlo), cancellare un bit (disattivarlo), invertire un bit (scambiarne il valore) e verificare un bit (controllare se vale 1). Ciascuna usa un operatore diverso, rispettivamente OR, AND-NOT, XOR e AND, con la maschera 1 << k.

Per impostare il bit k, cioè forzarlo a 1 indipendentemente dal suo valore corrente, si applica OR al numero con la maschera 1 << k. Poiché 0 OR 1 = 1 e 1 OR 1 = 1, il bit interessato diventa 1. A tutti gli altri bit viene applicato OR con 0, lasciandoli invariati.

Impostare un bit è un'operazione idempotente: chiamarla più volte produce lo stesso effetto di una sola chiamata. Se il bit k vale già 1, il risultato non cambia. Questa proprietà è importante nella gestione dei flag, quando si desidera abilitare una funzionalità senza preoccuparsi del suo stato corrente.

Per cancellare il bit k, cioè forzarlo a 0 indipendentemente dal suo valore corrente, si applica AND al numero con il complemento della maschera: n & ~(1 << k). Il complemento ~(1 << k) ha tutti i bit impostati a 1 tranne il bit k, che vale 0. Applicare AND con 0 forza a 0 il bit interessato; applicarlo con 1 conserva tutti gli altri bit.

Come l'impostazione, anche la cancellazione è idempotente. Cancellare un bit che vale già 0 lascia invariato il numero. In Python, ~(1 << k) funziona correttamente per qualsiasi k, perché Python gestisce automaticamente l'estensione del segno: concettualmente, il complemento ha tutti i bit più alti impostati a 1.

Per invertire il bit k, cioè passarlo da 0 a 1 o da 1 a 0, si applica XOR al numero con la maschera 1 << k. Applicare XOR con 1 inverte il bit; applicarlo con 0 lo lascia invariato. Questa è la proprietà fondamentale di XOR applicata a un singolo bit.

L'inversione è l'unica delle quattro operazioni a non essere idempotente: chiamarla due volte riporta al valore originale. Questo la rende perfetta per le funzionalità che alternano due stati, come un interruttore acceso/spento o un flag booleano in una rappresentazione compatta tramite interi.

Per verificare se il bit k è impostato, si fa uno scorrimento a destra di n di k posizioni e si applica AND con 1: (n >> k) & 1. In questo modo il bit k viene portato nella posizione 0 e tutti i bit più alti vengono mascherati, lasciando 0 (il bit k valeva 0) oppure 1 (il bit k valeva 1). In alternativa, si può usare bool(n & (1 << k)) per ottenere un risultato True/False.

La verifica di un bit non è distruttiva: non modifica n. È possibile verificare più bit facendo scorrimento e mascheramento di ciascuna posizione separatamente. Questa è la base per scorrere la rappresentazione binaria di un numero, operazione usata nell'enumerazione dei sottoinsiemi e nella programmazione dinamica con stati rappresentati da maschere di bit.

Un intero con n bit può rappresentare un sottoinsieme di un insieme di n elementi: il bit k vale 1 se l'elemento k appartiene al sottoinsieme, altrimenti vale 0. In questo modo un sottoinsieme viene compresso in un singolo intero, consentendo operazioni O(1): verifica dell'appartenenza (mask & (1 << k)), aggiunta di un elemento (mask | (1 << k)), rimozione di un elemento (mask & ~(1 << k)) e unione/intersezione di insiemi (mask1 | mask2 e mask1 & mask2).

Con n elementi esistono 2^n sottoinsiemi possibili, ciascuno rappresentato in modo univoco da un intero di n bit compreso tra 0 e 2^n - 1. Scorrere tutti gli interi da 0 a 2^n - 1 permette di enumerare tutti i sottoinsiemi.

Nella programmazione dinamica con maschere di bit, spesso è necessario scorrere tutti i sottoinsiemi di una determinata maschera. Un trucco comune consiste nel partire da sub = mask e aggiornare il valore con sub = (sub - 1) & mask finché sub non raggiunge 0. Ogni iterazione produce una sottomaschera diversa. Il costo totale su tutte le maschere è O(3^n), perché ogni elemento può appartenere solo alla maschera esterna, solo alla sottomaschera, a entrambe oppure a nessuna delle due.

Questa tecnica compare in problemi come «dividere un array in sottoinsiemi con lo stesso XOR» o «trovare l'AND massimo di un qualsiasi sottoinsieme». La capacità di enumerare in modo efficiente le sottomaschere è una caratteristica distintiva della programmazione dinamica avanzata con maschere di bit.

La DP con maschere di bit risolve problemi in cui lo stato include un sottoinsieme di elementi visitati. L'esempio classico è il problema del commesso viaggiatore (TSP): trovare il tour di costo minimo che visiti n città. Lo stato è dp[mask][city] = costo minimo per visitare le città in mask, terminando nella città city. Con n città, ci sono 2^n × n stati, con un tempo di O(n^2 × 2^n) — gestibile per n ≤ 20.

La maschera funge da insieme compresso degli elementi visitati. Impostare, cancellare e controllare i bit corrisponde rispettivamente a visitare, lasciare e interrogare le città. Questo è il principio fondamentale della DP con maschere di bit: usare i bit come insieme compatto per rappresentare lo stato.

A volte è necessario estrarre non solo un singolo bit, ma un campo multi-bit — un intervallo contiguo di bit. Per estrarre i bit dalla posizione start a start+length-1, crei una maschera composta da length bit consecutivi a 1: mask = (1 << length) - 1, quindi applichi (n >> start) & mask.

Questa tecnica viene usata per analizzare formati di interi impacchettati, come indirizzi IP, dati dei pixel o registri hardware, in cui diversi valori piccoli sono memorizzati in un unico intero. Ad esempio, un pixel RGB565 a 16 bit memorizza il rosso nei bit 15-11, il verde nei bit 10-5 e il blu nei bit 4-0.

Le maschere di bit compaiono comunemente nei seguenti tipi di problemi da colloquio:

• Enumerazione dei sottoinsiemi: iterare su tutti i 2^n sottoinsiemi usando maschere da 0 a 2^n-1
• DP con compressione dello stato: codificare un insieme di nodi o elementi visitati come maschera di bit nello stato della DP
• Sistemi di autorizzazioni: combinare i flag READ/WRITE/EXECUTE con OR e verificarli con AND
• Tracciamento delle celle visitate in una griglia: per le griglie piccole, memorizzare le celle visitate in un unico intero

Un indizio importante dell'utilità delle maschere di bit è che il problema coinvolga un insieme piccolo (n ≤ 20 elementi) e richieda di tenere traccia delle combinazioni di appartenenza. Per insiemi più grandi sono necessarie rappresentazioni diverse.

Quando si iterano i bit impostati di una maschera, si usano comunemente due tecniche. Il metodo shift-and-check: spostare a destra e controllare l'LSB. Il metodo di isolamento del bit meno significativo impostato: isolare il bit meno significativo impostato con n & -n, elaborarlo e poi cancellarlo con n &= n - 1. Il secondo metodo visita solo i bit impostati ed è più veloce quando la maschera è sparsa.

In Python, per il popcount può anche usare bin(n).count('1') o n.bit_count() (3.10+). Per ottenere la posizione di ciascun bit impostato, usi n.bit_length() - 1 per il bit impostato più significativo.

Metta alla prova la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep affrontati in questa lezione.

In questa lezione ha imparato che: le quattro operazioni fondamentali sulle maschere di bit sono impostazione (OR), cancellazione (AND-NOT), inversione (XOR) e controllo (shift-AND); gli interi possono rappresentare sottoinsiemi, in cui ogni bit codifica l'appartenenza di un elemento, permettendo di enumerare 2^n sottoinsiemi; inoltre, l'estrazione di campi multi-bit e la DP con maschere di bit usano gli stessi principi di mascheramento per codificare stati più complessi. Prossimamente esploreremo il conteggio dei bit, i numeri mancanti e l'inversione dei bit usando le tecniche di questa lezione e della precedente.