Contare i bit e il bit impostato meno significativo
Usare popcount e il trucco n & -n
Contare i bit e il bit impostato meno significativo è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Contare gli uni
Molti problemi chiedono quanti bit sono impostati in un numero, un valore chiamato popcount. Compare nel calcolo delle dimensioni dei sottoinsiemi, nei controlli di parità e nei punteggi. 🔢
Il conteggio integrato di Python
Il modo più rapido per contare i bit impostati è usare il metodo degli interi bit_count(). Nessun ciclo, nessuna complicazione: si ottiene direttamente il numero di uni.
print((13).bit_count()) # 0b1101 has 3 onesContare con bin e count
Se si dimentica bit_count, si può convertire il numero in testo binario e contare gli uni. È più lento, ma chiaro e facile da ricordare.
print(bin(13).count('1')) # 3Il bit impostato meno significativo
Il bit impostato meno significativo è l’1 più a destra in un numero. Isolarlo è una tecnica fondamentale per gli alberi di Fenwick e per i trucchi con i sottoinsiemi.
Isolarlo con n e -n
Il famoso trucco n & -n mantiene solo il bit impostato meno significativo. I numeri negativi in complemento a due fanno funzionare il trucco quasi per magia.
n = 12 # 0b1100
print(n & -n) # 4 = 0b100Perché n e -n funzionano
La negazione inverte tutti i bit e aggiunge 1, quindi tutto ciò che si trova sotto l’1 meno significativo viene invertito. L’AND lascia in piedi solo quel singolo bit.
Rimuovere il bit impostato meno significativo
Sottrarre 1 propaga il prestito attraverso gli zeri finali, quindi n & (n - 1) cancella il bit impostato meno significativo. Ripetendo l’operazione, si possono rimuovere gli uni uno alla volta.
n = 12 # 0b1100
print(n & (n - 1)) # 8 = 0b1000Il conteggio di Brian Kernighan
Si esegue un ciclo finché il numero è diverso da zero, azzerando ogni volta il bit meno significativo. Il ciclo viene eseguito una volta per ogni bit impostato, quindi è veloce per un popcount sparso.
c = 0
while n:
n &= n - 1
c += 1Verificare se è una potenza di due
Una potenza di due positiva ha esattamente un bit impostato, quindi n & (n - 1) è uguale a 0. Un solo AND permette di verificarlo immediatamente.
def is_pow2(n):
return n > 0 and (n & (n - 1)) == 0La parità dal conteggio dei bit
La parità di un numero è semplicemente il suo popcount modulo 2. Permette di stabilire in un solo passaggio se il numero di uni è dispari o pari.
parity = (13).bit_count() & 1 # 1Scegliere lo strumento più veloce
Per la massima velocità si utilizza bit_count; per scorrere i bit impostati si usa il ciclo con n & (n-1). Scegliere lo strumento giusto aiuta a rispettare i limiti di tempo stringenti. ⚡
Verifica rapida
Verifichi il trucco del bit impostato meno significativo.
Riepilogo: contare i bit
È possibile contare gli uni con bit_count, isolare il bit meno significativo con n & -n e rimuoverlo con n & (n-1). Sono espressioni brevi e potenti. 🎉
Domande Frequenti
La lezione «Contare i bit e il bit impostato meno significativo» è gratuita?
Sì — il testo completo di «Contare i bit e il bit impostato meno significativo» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Contare i bit e il bit impostato meno significativo»?
Usare popcount e il trucco n & -n Eserciti Competitive Programming Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Contare i bit e il bit impostato meno significativo»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- AND, OR, XOR e shift
- Impostare, azzerare e invertire un bit
- Contare i bit e il bit impostato meno significativo
- Le bitmask come piccoli set