Power of Two
Ti viene dato un intero n. Restituisci true se n è una potenza di due, cioè se n = 2^k per qualche numero intero k ≥ 0, e false altrimenti. Quindi 1, 2, 4 e 8 sono validi, mentre 0, 6 e tutti i numeri negativi non lo sono.
Funzione
- ninteger
- l'intero da verificare, che può essere zero o negativo
- Restituisceboolean
- vero se n è uguale a 2^k per qualche k ≥ 0, falso altrimenti
Vincoli
-231 ≤ n ≤ 231-1
Esempi
- Input
- n = 16
- Output
- true
- Spiegazione
- 16 = 2 × 2 × 2 × 2 = 2^4. In binario è
10000, un singolo bit 1.
- Input
- n = 24
- Output
- false
- Spiegazione
- 24 = 8 × 3. Dividendo per due si ottengono 12, 6 e poi 3, che è dispari ma non è 1. In binario 24 è
11000, con due bit a 1.
- Input
- n = 1
- Output
- true
- Spiegazione
- 1 = 2^0, quindi è una potenza di due. La sua forma binaria
1ha esattamente un bit 1.
Per approfondire
Con gli stessi trucchi sui bit, riesci a verificare se n è una potenza di quattro senza usare un ciclo?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Scrivi alcune potenze di due in binario:
1,10,100,1000. Che cosa hanno tutte in comune che manca al 6 (110)?Una potenza di due ha esattamente un bit 1. Confronta
nconn-1in binario: sottrarre 1 trasforma il bit 1 più a destra in 0 e ogni 0 alla sua destra in 1.Quindi
nè una potenza di due esattamente quando è positivo e l’operazione AND conn-1dà 0. Verifica il segno prima dei bit, perché 0 e i numeri negativi non sono mai potenze di due.
Soluzione
Una potenza di due ha una forma fissa in binario: un bit 1 seguito da zeri, come 10000 per 16. Puoi confermare questa forma dimezzando n finché diventa dispari, operazione che richiede fino a 31 passaggi. Oppure puoi confermarla in un solo passaggio con n & (n-1), che azzera il bit 1 meno significativo e lascia 0 solo quando quel bit era l’unico. In entrambe le versioni il controllo del segno viene prima, perché i numeri zero e negativi compromettono il codice più ovvio.
Dividi per 2 finché il numero è pari
Intuizione
Se n = 2^k, puoi dividerlo esattamente per 2 k volte e arrivare a 1, e ogni valore lungo il percorso è pari. Se n ha un fattore dispari maggiore di 1, la divisione a metà si ferma a un numero dispari diverso da 1. Per 16: 16, 8, 4, 2, 1, quindi la risposta è true. Per 24: 24, 12, 6, 3, e 3 è dispari ma diverso da 1, quindi la risposta è false.
Restituisci false per n ≤ 0 prima del ciclo. Nessuna potenza di due è zero o negativa, e il ciclo non terminerebbe mai con 0, perché 0 è pari e la metà di 0 è ancora 0.
Ogni passaggio dimezza n, quindi un input a 32 bit richiede al massimo 31 passaggi: tempo O(log n) e spazio O(1).
Algoritmo
- Se
n ≤ 0, restituisci false. - Finché
nè pari, dividilo per 2. - Restituisci se
nora è 1.
def isPowerOfTwo(n):
if n <= 0:
return False
while n % 2 == 0:
n //= 2
return n == 1Azzeri il bit meno significativo impostato con n & (n-1)
Intuizione
Scrivi una potenza di due in binario e otterrai un solo 1 seguito da zeri: 16 è 10000. Sottraendo 1, quell'1 diventa 0 e ogni 0 alla sua destra diventa 1: 15 è 01111. I due numeri non hanno bit a 1 in comune, quindi 16 & 15 è 0.
Qualsiasi altro numero positivo ha almeno due bit a 1. Sottraendo 1, cambia solo il bit a 1 più basso e gli zeri alla sua destra, quindi ogni bit a 1 più alto compare in entrambi i numeri e l'AND non è 0. Per 24, che è 11000, si ottiene 23 = 10111, e 24 & 23 è 10000, cioè 16.
Controlla prima n > 0. 0 & -1 è 0 e, nell'aritmetica a 32 bit, -2^31 è un solo bit a 1 seguito da 31 zeri, quindi il solo AND considererebbe entrambi potenze di due. Il test completo richiede un confronto, una sottrazione e un AND: tempo e spazio O(1). Lua 5.1 non ha un operatore AND, quindi il codice Lua costruisce l'AND un bit alla volta, fino a 31 passaggi per un n a 32 bit; il test è lo stesso.
Algoritmo
- Se
n ≤ 0, restituisci false. - Calcola
n & (n-1), che èncon il bit 1 meno significativo azzerato. - Restituisci se il risultato è 0.
def isPowerOfTwo(n):
# One set bit: n - 1 flips it and every bit below, so the AND is 0.
return n > 0 and n & (n - 1) == 0
Trappole e casi limite
Il test sui bit occupa una sola riga e la maggior parte degli errori riguarda gli input per cui non è stato progettato.
- Omettere il controllo del segno.
0 & (0-1)è 0, quindi 0 supera il test AND. Con gli interi a 32 bit, anche-2^31lo supera, perché la sua rappresentazione binaria contiene un solo bit 1. Entrambi devono restituire false. - Eseguire il ciclo di dimezzamento su 0. Zero è pari e dimezzandolo si ottiene di nuovo 0, quindi il ciclo non termina mai.
- Omettere le parentesi.
==ha precedenza maggiore di&, quindi in C, C++ e JavaScriptn & n - 1 == 0viene interpretato comen & ((n - 1) == 0)e dà la risposta sbagliata senza alcun errore; Java e C# lo rifiutano con un errore di tipo. Scrivi(n & (n - 1)) == 0. - Usare i logaritmi. In doppia precisione,
log(536870912) / log(2)dà 29.000000000000004 invece di 29, quindi un controllo sui numeri interi considera2^29falso.
Domande frequenti3
Come si verifica se un numero è una potenza di due?
Restituisci true quando n > 0 e n & (n-1) è uguale a 0. Una potenza di due ha esattamente un bit 1 e sottraendo 1 lo si azzera, impostando solo i bit che lo precedono, quindi l’AND è 0. Senza operazioni sui bit, dimezza n finché è pari e verifica di arrivare a 1.
Perché n & (n-1) azzera il bit impostato meno significativo?
Sottrarre 1 prende in prestito dal bit 1 meno significativo: quel bit diventa 0 e ogni 0 sotto di esso diventa 1, mentre i bit più alti restano invariati. Eseguire un AND con il valore originale mantiene solo i bit impostati in entrambi, che sono esattamente i bit più alti. Per una potenza di due non ci sono bit più alti, quindi il risultato è 0.
Qual è la complessità temporale di Power of Two?
Il controllo n & (n-1) viene eseguito in tempo e spazio O(1): un confronto, una sottrazione e un AND. Il ciclo di dimezzamento viene eseguito in tempo O(log n), al massimo 31 passaggi per un intero a 32 bit.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def isPowerOfTwo(n):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomento
n = 16
Output atteso
true