Counting Bits

Q: Perché bits[i] = bits[i >> 1] + (i & 1) funziona?

i >> 1 è i con la sua ultima cifra binaria rimossa, e i & 1 è quella cifra rimossa. Gli 1 di i sono gli 1 del numero più corto più l’ultima cifra. Per 11, che è 1011 , il numero più corto è 5 ( 101 , due 1) e l’ultima cifra è 1, quindi 11 ne ha tre.

Q: Esiste un'altra ricorrenza O(n) per il conteggio dei bit?

Sì. i & (i-1) azzera il bit 1 meno significativo di i , quindi bits[i] = bits[i & (i-1)] + 1 per ogni i maggiore o uguale a 1. Per 12 ( 1100 ), 12 & 11 è 8 ( 1000 ), che ha un 1, quindi 12 ne ha due. È veloce quanto la regola dello shift e usa lo stesso riempimento da sinistra a destra.

Q: Posso usare una funzione popcount integrata?

La maggior parte dei linguaggi ne ha una, come Integer.bitCount in Java o __builtin_popcount in C e C++, e chiamarla per ogni numero dà una risposta corretta. Di solito gli intervistatori chiedono la versione senza, perché il punto del problema è riutilizzare le risposte che hai già calcolato. La ricorrenza funziona anche nei linguaggi che non hanno una funzione del genere.

FacileManipolazione dei bit Programmazione dinamica

+10

Ricevi un numero intero n maggiore o uguale a 0. Per ogni numero i da 0 a n, conta quanti 1 compaiono quando i è scritto in binario. Restituisci i conteggi come un array di n+1 elementi, dove l’elemento i è il conteggio per il numero i.

Funzione

countBits(n: integer) → integer-array

ninteger: l'ultimo numero da contare, 0 o più
Restituisceinteger-array: un array di n+1 conteggi, dove la voce i è il numero di bit 1 in i

Vincoli

0 ≤ n ≤ 2 × 10⁴

Esempi

Input: n = 2
Output: [0, 1, 1]
Spiegazione: In binario, 0 è 0, 1 è 1 e 2 è 10. Ovvero nessun 1, poi uno, poi uno.

Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Spiegazione: 3 è 11 e 5 è 101, entrambi con due 1, mentre 4 è 100 con un solo 1. Con 0, 1 e 2 del primo esempio, i conteggi da 0 a 5 sono 0, 1, 1, 2, 1, 2.

+15 test nascosti all’invio

Per approfondire

Riesci a riempire l'intero array in tempo O(n), senza una funzione integrata che conta i bit e senza contare da zero ogni numero?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Contare gli 1 di ogni numero singolarmente funziona, ma ripete del lavoro. 13 è 1101 e 6 è 110: i bit di 13 sono i bit di 6 con una cifra in più alla fine. Se inserisci le risposte in ordine crescente, il conteggio che ti serve per i è già nell’array e ogni voce richiede una sola addizione.

Conta i bit di ogni numero

Intuizione

Prendi ogni numero da 0 a n e conta direttamente i suoi bit a 1. Il bit meno significativo di x è x & 1. Aggiungilo a un contatore, poi sposta x a destra con x >> 1, così il bit successivo diventa quello meno significativo. Fermati quando x raggiunge 0.

Per 13, che in binario è 1101, i bit letti da destra sono 1, 0, 1, 1, quindi il conteggio è 3. Ogni numero richiede un passaggio per ogni cifra binaria e un numero fino a n ha circa log2 n cifre.

Questo rende l’esecuzione complessiva O(n log n). Per n = 2 × 10^4 sono circa 20.000 × 15 = 300.000 passaggi, un numero di passaggi gestibile in tempo. Rimane però del lavoro sprecato: contare 13 ripete ogni passaggio già eseguito per 6. Lo spazio è O(1), a parte l’array di output.

Algoritmo

Inizia una lista di risultati vuota.
Per ogni i da 0 a n, imposta count su 0 e x su i.
Mentre x è maggiore di 0, aggiungi x & 1 a count e sposta x a destra di una posizione.
Aggiungi count al risultato.
Restituisci il risultato.

def countBits(n):
    bits = []
    for i in range(n + 1):
        count = 0
        x = i
        while x > 0:
            count += x & 1  # the lowest bit
            x >>= 1         # shift it out
        bits.append(count)
    return bits

Costruisci su metà del numero

Intuizione

Spostare i a destra di una posizione elimina la sua ultima cifra binaria. Quindi i ha esattamente gli stessi bit a 1 di i >> 1, più uno se la sua ultima cifra è 1. Quest’ultima cifra è i & 1, da cui deriva la regola bits[i] = bits[i >> 1] + (i & 1).

Per ogni i maggiore o uguale a 1, i >> 1 è minore di i. Se riempi l’array da sinistra a destra, iniziando con bits[0] = 0, la voce che cerchi è sempre già stata riempita. Questa è la programmazione dinamica: ogni risposta viene costruita a partire da una più piccola.

Per n = 5: bits[1] = bits[0] + 1 = 1, bits[2] = bits[1] + 0 = 1, bits[3] = bits[1] + 1 = 2, bits[4] = bits[2] + 0 = 1, bits[5] = bits[2] + 1 = 2. Ogni voce richiede uno shift, un AND e un’addizione, quindi il tempo è O(n) e non serve altra memoria oltre a quella necessaria per l’output.

Algoritmo

Crea un array bits di n+1 zeri. bits[0] rimane 0.
Per i da 1 a n, imposta bits[i] a bits[i >> 1] + (i & 1).
Restituisci bits.

def countBits(n):
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        # i >> 1 is i without its last bit, and i & 1 is that last bit
        bits[i] = bits[i >> 1] + (i & 1)
    return bits

Trappole e casi limite

La regola sta su una riga, quindi i bug si nascondono nei dettagli.

L’array ha n+1 elementi, non n. Per n = 0 la risposta è [0]: un elemento, per il numero 0.
Precedenza degli operatori. In Python, C, Java e JavaScript, + ha la precedenza su &, quindi bits[i >> 1] + i & 1 viene letto come (bits[i >> 1] + i) & 1. Mantieni le parentesi intorno a (i & 1).
Usare bits[i-1] invece di bits[i >> 1]. I numeri vicini non seguono una regola semplice: 7 è 111 con tre 1, e 8 è 1000 con uno.
In Lua e R gli array iniziano da 1, quindi il conteggio per i si trova all’indice i+1 e il riferimento a i >> 1 si trova all’indice floor(i/2) + 1. Lua del runner non ha un operatore di shift, quindi dimezza con math.floor(i / 2).
Convertire ogni numero in una stringa binaria e contare i caratteri 1 dà la risposta giusta, ma crea una nuova stringa per ogni numero.

Domande frequenti4

Qual è la complessità temporale di Counting Bits?

La soluzione migliore richiede un tempo O(n): ciascuna delle n+1 voci deriva da una voce precedente con un’addizione. Contare i bit di ogni numero uno alla volta richiede O(n log n), perché un numero fino a n ha circa log2 n cifre binarie. Entrambi gli approcci usano O(1) memoria oltre all’array di output.

Perché bits[i] = bits[i >> 1] + (i & 1) funziona?

i >> 1 è i con la sua ultima cifra binaria rimossa, e i & 1 è quella cifra rimossa. Gli 1 di i sono gli 1 del numero più corto più l’ultima cifra. Per 11, che è 1011, il numero più corto è 5 (101, due 1) e l’ultima cifra è 1, quindi 11 ne ha tre.

Esiste un'altra ricorrenza O(n) per il conteggio dei bit?

Sì. i & (i-1) azzera il bit 1 meno significativo di i, quindi bits[i] = bits[i & (i-1)] + 1 per ogni i maggiore o uguale a 1. Per 12 (1100), 12 & 11 è 8 (1000), che ha un 1, quindi 12 ne ha due. È veloce quanto la regola dello shift e usa lo stesso riempimento da sinistra a destra.

Posso usare una funzione popcount integrata?

La maggior parte dei linguaggi ne ha una, come Integer.bitCount in Java o __builtin_popcount in C e C++, e chiamarla per ogni numero dà una risposta corretta. Di solito gli intervistatori chiedono la versione senza, perché il punto del problema è riutilizzare le risposte che hai già calcolato. La ricorrenza funziona anche nei linguaggi che non hanno una funzione del genere.

Python

def countBits(n):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Input

n = 2

Atteso

[0, 1, 1]