Number of 1 Bits
Ti viene dato un intero non negativo n. Scrivi n in binario e restituisci quanti dei suoi bit sono 1. Questo conteggio è anche chiamato numero di bit impostati, conteggio della popolazione o peso di Hamming. Per esempio, 6 in binario è 110, quindi ha due bit a 1.
Funzione
- ninteger
- un numero intero non negativo che rientra in un int con segno a 32 bit
- Restituisceinteger
- il numero di cifre 1 nella forma binaria di n
Vincoli
0 ≤ n ≤ 231-1
Esempi
- Input
- n = 11
- Output
- 3
- Spiegazione
- 11 è
1011in binario, che corrisponde a 8 + 2 + 1. Tre delle sue quattro cifre binarie sono 1, quindi la risposta è 3.
- Input
- n = 128
- Output
- 1
- Spiegazione
- 128 è 2^7, scritto
10000000: un singolo 1 seguito da zeri, quindi la risposta è 1.
- Input
- n = 2147483645
- Output
- 30
- Spiegazione
- 2^31-1 = 2147483647 è formato da trentuno bit 1 consecutivi. 2147483645 è quel numero meno 2, il che spegne il bit che vale 2 e lascia 30 uno.
Per approfondire
Se questa funzione venisse eseguita milioni di volte, come potresti contare i bit di un numero a 32 bit con quattro consultazioni di una tabella di 256 conteggi precalcolati?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Guarda solo l’ultima cifra binaria di
n. Come puoi leggerla senza convertirenin una stringa e come puoi poi portare la cifra successiva all’ultimo posto?n & 1(on % 2) è l'ultimo bit, e uno spostamento a destra di una posizione (o una divisione per 2 arrotondata per difetto) lo rimuove. Somma gli ultimi bit finchénnon è 0.Per un ciclo più breve, usa
n & (n-1): èncon il suo bit 1 meno significativo disattivato. Conta quante volte puoi applicarlo prima chenraggiunga 0. Il ciclo viene quindi eseguito una volta per ogni bit 1 invece che una volta per ogni cifra binaria.
Soluzione
Esamina le cifre binarie di n senza costruire una stringa. Leggere l'ultimo bit e spostarlo via richiede un passaggio per ogni cifra binaria, fino a 31. Azzerare il bit 1 meno significativo con n & (n-1) richiede un passaggio per ogni bit 1, esattamente tanti quanti ne servono per ottenere la risposta.
Controlla l'ultimo bit e sposta a destra
Intuizione
n & 1 è l'ultima cifra binaria di n: 1 quando n è dispari, 0 quando è pari. Aggiungila al conteggio. Poi n >> 1 elimina quella cifra e sposta la successiva all'ultimo posto; per un numero non negativo equivale alla divisione per 2, arrotondata per difetto. Per 11, 1011, gli ultimi bit letti sono 1, 1, 0 e 1 man mano che n diminuisce fino a 0: tre bit 1.
Il ciclo si interrompe quando n è 0, quindi non visita mai gli zeri iniziali: circa log2(n) passaggi, 8 per 128 e al massimo 31. Memorizza solo n e il conteggio.
Algoritmo
- Avvia un contatore a 0.
- Finché
nè maggiore di 0, aggiungin & 1al contatore. - Sposta
na destra di un bit. - Quando
nraggiunge 0, restituisci il contatore.
def hammingWeight(n):
count = 0
while n > 0:
count += n & 1 # the last bit is 1 or 0
n >>= 1 # drop the last bit
return countCancella il bit meno significativo impostato con n & (n-1)
Intuizione
Sottrarre 1 trasforma il bit 1 meno significativo in 0 e ogni 0 al di sotto di esso in 1, lasciando invariati i bit superiori. Quindi n & (n-1) mantiene i bit superiori e azzera il bit 1 meno significativo: 12 è 1100, 11 è 1011 e 1100 & 1011 è 1000.
Ogni passaggio rimuove esattamente un bit 1, quindi la risposta è il numero di passaggi necessari affinché n diventi 0. Per 128 basta 1 passaggio invece di 8, anche se 2^31-1 richiede comunque 31 passaggi. Lua 5.1 non ha operatori bitwise, quindi la sua versione individua il bit 1 meno significativo dimezzando e lo sottrae; il ciclo viene comunque eseguito una volta per ogni bit 1.
Algoritmo
- Inizia un contatore da 0.
- Finché
nnon è 0, sostituiscinconn & (n-1). - Aggiungi 1 al contatore dopo ogni sostituzione.
- Restituisci il contatore.
def hammingWeight(n):
count = 0
while n != 0:
n &= n - 1 # turn off the lowest 1 bit
count += 1
return count
Trappole e casi limite
- Ripeti il ciclo mentre
n > 1. Il ciclo si ferma prima dell'ultimo bit 1 e restituisce 0 pern = 1. - Dividere ottenendo un numero in virgola mobile. In JavaScript, Lua e R,
11 / 2è 5.5 e i resti che seguono sono frazioni. Arrotonda per difetto conMath.floor,math.flooro%/%, oppure usa uno shift. - Scrivere
n & 1in Lua 5.1. Non ha operatori bitwise, quindi il codice non viene compilato; usan % 2emath.floor(n / 2).
Domande frequenti3
Qual è la complessità temporale di Number of 1 Bits?
Il ciclo di shift viene eseguito una volta per ogni cifra binaria: O(log n), al massimo 31 passaggi in questo caso. Il ciclo n & (n-1) viene eseguito una volta per ogni bit a 1: O(k), dove k è la risposta. Entrambi usano O(1) spazio aggiuntivo.
C'è una funzione integrata che conta i bit impostati?
La maggior parte dei linguaggi ne ha una, spesso supportata da una singola istruzione del processore: Integer.bitCount in Java, __builtin_popcount in GCC, bits.OnesCount in Go, count_ones in Rust e int.bit_count in Python 3.10 e versioni successive. In un colloquio, scrivi il ciclo e menziona la funzione integrata.
Qual è la differenza tra peso di Hamming e distanza di Hamming?
Il peso di Hamming di un numero è il numero delle sue cifre binarie pari a 1, ed è ciò che restituisce questo problema. La distanza di Hamming tra due numeri è il numero di posizioni dei bit in cui differiscono: conta i bit a 1 di a ^ b, poiché XOR imposta esattamente le posizioni in cui differiscono.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def hammingWeight(n):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomento
n = 11
Output atteso
3