Counting Bits

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 contiene un 1, quindi 12 ne contiene due.

Q: Posso usare una funzione popcount integrata?

Chiamarne una per ogni numero, come Integer.bitCount in Java o __builtin_popcount in C e C++, dà una risposta corretta. Di solito gli intervistatori chiedono la versione senza, perché il punto del problema è riutilizzare le risposte che hai già calcolato.

FacileManipolazione dei bit Programmazione dinamica

+10

Dato un numero intero non negativo n, restituisci un array di n+1 elementi, dove l’elemento i è il numero di 1 nella rappresentazione binaria di i, per ogni i da 0 a n.

Funzione

countBits(n: integer) → integer-array

ninteger: l'ultimo numero da contare, 0 o più
Restituisceinteger-array: un array di n+1 conteggi, dove l’elemento 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: zero 1, poi uno, poi uno.

Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Spiegazione: 3 è 11 e 5 è 101, due 1 ciascuno; 4 è 100, con uno. Con 0, 1 e 2 del primo esempio, i conteggi sono 0, 1, 1, 2, 1, 2.

Per approfondire

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

Suggerimenti

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

0 di 3 aperti

Soluzione

Contare ogni numero da zero ripete il lavoro: 13 è 1101, i bit di 6 (110) con una cifra in più alla fine. Completa le risposte in ordine crescente e ogni voce riutilizza una più piccola con un'addizione.

Conta i bit di ogni numero

Intuizione

Conta direttamente i bit 1 di ciascun numero: aggiungi x & 1 a un contatore, sposta x a destra di un bit e fermati a 0. Per 13 (1101) i bit risultano 1, 0, 1, 1, quindi il conteggio è 3.

Un numero fino a n ha circa log2 n cifre binarie, quindi l'esecuzione è O(n log n): circa 20.000 × 15 = 300.000 passaggi per n = 2 × 10^4.

Algoritmo

Inizia una lista dei risultati vuota.
Per ogni i da 0 a n, imposta count a 0 e x a i.
Mentre x è maggiore di 0, aggiungi x & 1 a count e sposta x a destra di un bit.
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 sulla metà del numero

Intuizione

Spostando i a destra di una posizione si elimina la sua ultima cifra binaria, e i & 1 è quella cifra. Quindi i ha i bit a 1 di i >> 1 più la sua ultima cifra: bits[i] = bits[i >> 1] + (i & 1).

Per ogni i maggiore o uguale a 1, i >> 1 è minore di i, quindi riempire l'array da sinistra a destra, iniziando da bits[0] = 0, significa che la voce che leggi è sempre pronta. Per n = 5: bits[3] = bits[1] + 1 = 2, bits[4] = bits[2] + 0 = 1, bits[5] = bits[2] + 1 = 2.

Ogni voce richiede uno spostamento, un AND e un'addizione: tempo O(n) e nessuna 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] su 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

Restituire n elementi invece di n+1. Per n = 0 la risposta è [0].
Precedenza degli operatori. In Python, C, Java e JavaScript, + ha una precedenza maggiore di &, quindi bits[i >> 1] + i & 1 significa (bits[i >> 1] + i) & 1. Mantieni le parentesi intorno a (i & 1).
Accedere a bits[i-1] invece di bits[i >> 1]. I numeri vicini non condividono una regola semplice: 7 è 111 con tre 1, mentre 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 l’accesso per i >> 1 a floor(i/2) + 1. Lua 5.1 non ha un operatore di shift, quindi dimezza con math.floor(i / 2).

Domande frequenti3

Qual è la complessità temporale di Counting Bits?

La soluzione migliore viene eseguita in tempo O(n): ciascuna delle n+1 voci deriva da una voce precedente con un’addizione. Contare i bit di ogni numero singolarmente richiede O(n log n). Entrambe usano O(1) memoria oltre all’array di output.

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 contiene un 1, quindi 12 ne contiene due.

Posso usare una funzione popcount integrata?

Chiamarne una per ogni numero, come Integer.bitCount in Java o __builtin_popcount in C e C++, dà una risposta corretta. Di solito gli intervistatori chiedono la versione senza, perché il punto del problema è riutilizzare le risposte che hai già calcolato.

def countBits(n):
    # Scrivi il codice qui

Test #1

Test #2

Argomento

n = 2

Output atteso

[0, 1, 1]