Conteggio dei bit, numero mancante e inversione dei bit

Il problema Counting Bits (LeetCode 338) richiede, dato n, di restituire un array ans di dimensione n+1 in cui ans[i] è il numero di bit a 1 in i. L'approccio ingenuo è O(n log n): contare i bit di ogni numero individualmente. L'approccio DP è O(n), perché sfrutta la relazione tra i e la sua metà o il suo bit meno significativo impostato.

La DP si basa su due osservazioni fondamentali: (1) i >> 1 elimina il bit meno significativo, quindi bits[i] = bits[i >> 1] + (i & 1). (2) Cancellando il bit meno significativo impostato: bits[i] = bits[i & (i-1)] + 1. Entrambi gli approcci richiedono tempo O(n) e spazio O(n) per l'array di output.

Per la ricorrenza dello shift a destra dp[i] = dp[i >> 1] + (i & 1): dividere per 2, effettuando uno shift a destra, rimuove l'ultimo bit. Se l'ultimo bit era 1, il conteggio aumenta di 1; se era 0, non cambia. Quindi bits[i] = bits[i // 2] + (i mod 2).

Per la ricorrenza basata sul bit meno significativo impostato dp[i] = dp[i & (i-1)] + 1: i & (i-1) cancella il bit a 1 più a destra, quindi ha un bit impostato in meno rispetto a i. Il conteggio è dunque quello del valore ridotto, più 1. Entrambe le ricorrenze elaborano i in ordine crescente, così i sottoproblemi più piccoli vengono sempre risolti per primi.

Il problema Missing Number (LeetCode 268) fornisce un array di n numeri distinti nell'intervallo [0, n], con esattamente un numero mancante. L'approccio XOR: applicare XOR a tutti gli indici da 0 a n e a tutti i valori dell'array. Le coppie si annullano, lasciando il numero mancante. L'approccio della somma: expected = n*(n+1)//2, quindi restituire expected - sum(nums).

Entrambi gli approcci richiedono tempo O(n) e spazio O(1). L'approccio XOR è più robusto nei linguaggi con interi a larghezza fissa, perché evita un possibile overflow. In Python, entrambi funzionano senza problemi, poiché gli interi hanno precisione arbitraria.

Il problema Reverse Bits (LeetCode 190) richiede di invertire la rappresentazione binaria di un intero senza segno a 32 bit. L'approccio iterativo consiste nell'elaborare ciascuno dei 32 bit dell'input da destra a sinistra e nel collocarli da sinistra a destra nell'output. A ogni iterazione si estrae il bit più a destra con n & 1, si sposta l'output a sinistra per fare spazio, si inserisce il bit con OR e infine si sposta n a destra.

Dopo 32 iterazioni, l'intero di output contiene tutti i 32 bit di n in ordine inverso. Si tratta di O(32) = O(1) per chiamata, oppure di O(1) ammortizzato con il caching per chiamate ripetute su blocchi da 8 bit.

Un approccio più rapido O(log 32) = O(1) inverte i bit usando uno scambio divide et impera. Prima si scambiano i bit adiacenti, poi i gruppi adiacenti di 2 bit, quindi i gruppi di 4 bit e così via. Ogni livello di scambio usa maschere per separare i gruppi alternati e shift per intercalarli. Dopo 5 scambi, tutti i 32 bit sono invertiti.

Questo approccio usa un numero fisso di operazioni O(1), indipendentemente dall'input, ed è utilizzato nelle implementazioni hardware. Le maschere sono costanti: 0x55555555 (pattern alternato 01), 0x33333333 (pattern alternato 0011), 0x0f0f0f0f (pattern alternato 00001111) e così via.

Il problema Number of 1 Bits (LeetCode 191) richiede il peso di Hamming (popcount) di un intero senza segno. Esistono tre approcci, con compromessi diversi: ciclo ingenuo (O(32)), metodo di Brian Kernighan (O(k), dove k = numero di bit impostati) e funzione integrata di Python n.bit_count() (3.10+).

Il metodo di Brian Kernighan è preferibile nei colloqui perché dimostra la comprensione del trucco n & (n-1). A ogni iterazione rimuove il bit meno significativo impostato, quindi il ciclo viene eseguito esattamente tante volte quanti sono i bit a 1: è molto più veloce di una scansione completa a 32 bit per gli interi sparsi.

A volte è necessario contare rapidamente i bit a 1 in un intervallo [l, r]. Costruisca una somma prefissa dei bit impostati per 0..n: prefix[i] = prefix[i-1] + bin(i).count('1'). Il conteggio per l'intervallo [l, r] è quindi prefix[r] - prefix[l-1]. In questo modo, dopo una preelaborazione O(n), è possibile eseguire query sugli intervalli in O(1).

Questa tecnica si generalizza a qualsiasi aggregato basato sui bit su un intervallo. Ad esempio, per contare i numeri in [l, r] con un numero pari di bit impostati si usa la stessa tecnica dei prefissi, ma con una funzione di accumulazione diversa.

In Python, gli interi sono con segno e hanno larghezza arbitraria. Quando si invertono i bit per il problema di LeetCode, è necessario trattare l'input come un intero senza segno a 32 bit. Applichi la maschera & 0xFFFFFFFF all'input prima dell'elaborazione, per assicurarsi di considerare solo 32 bit. Anche l'output deve essere un intero senza segno a 32 bit, quindi non negativo.

Se Le viene fornito un intero Python che può essere negativo, in senso complemento a due, applichi prima & 0xFFFFFFFF per ottenere la rappresentazione senza segno a 32 bit, quindi lo inverta. Il risultato è sempre un intero non negativo compreso tra 0 e 2^32 - 1.

Il problema del conteggio dei bit mostra un pattern generale per la DP sui bit: se conosce la risposta per una versione più piccola di i, può calcolarla per i usando un'operazione sui bit a tempo costante. Questo pattern si generalizza ad altri problemi di conteggio dei bit, come contare i numeri con esattamente k bit impostati nell'intervallo [0, n] usando l'enumerazione binaria, oppure trovare la potenza di due più alta che divide ciascun numero.

Un'altra osservazione utile è che il conteggio dei bit impostati di i segue un pattern ripetuto all'interno di ogni intervallo definito da una potenza di due. Il pattern per [2^k, 2^(k+1) - 1] è uguale a quello per [0, 2^k - 1], con ogni valore incrementato di 1, perché il bit k è sempre impostato in questo intervallo.

Molti problemi da colloquio combinano il conteggio dei bit, la logica dei numeri mancanti e l'inversione dei bit in un'unica domanda. Ad esempio: dato un array i cui elementi sono interi a n bit e in cui ne manca uno, trovare il valore mancante. Oppure: dato un flusso di conteggi dei bit, ricostruire l'intero mancante. Questi problemi richiedono di riconoscere quale sottotecnica applicare.

Si eserciti a costruire una mappa mentale: se un problema parla di trovare elementi mancanti, pensi a XOR o alla somma. Se chiede di «contare gli 1 in modo efficiente», pensi a Kernighan o alla DP. Se chiede di «invertire i bit», pensi all'approccio iterativo o a quello divide et impera. Questi sono i tre strumenti fondamentali della manipolazione dei bit nei colloqui.

Per chiamate ripetute all'inversione dei bit, ad esempio in una simulazione hardware, memorizzi nella cache i risultati per blocchi da 8 bit. Poiché ogni byte può assumere solo 256 valori, precalcoli il byte invertito per ogni valore da 0 a 255. Per invertire un intero a 32 bit, lo suddivida in quattro blocchi da 8 bit, inverta ciascuno di essi e li riassembli nell'ordine inverso.

In questo modo ogni chiamata si riduce a quattro accessi a una tabella e ad alcune operazioni sui bit, molto più rapide di un ciclo da 32 iterazioni per l'elaborazione in blocco. La cache viene creata una volta in O(256 × 8) e riutilizzata per tutte le chiamate successive in O(1).

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: il conteggio dei bit usa la DP con dp[i] = dp[i >> 1] + (i & 1) oppure dp[i] = dp[i & (i-1)] + 1, con tempo O(n); il numero mancante si trova in O(n)/O(1) applicando XOR a tutti gli indici e a tutti i valori oppure usando la formula della somma aritmetica; inoltre, l'inversione di 32 bit si esegue iterativamente in O(32) oppure con la tecnica delle maschere divide et impera. Prossimamente esploreremo gli stack monotoni, iniziando dall'invariante crescente rispetto a quella decrescente e dalle query del successivo elemento maggiore.