DSA Interview Prep · Lezione

Operatori bitwise: AND, OR, XOR, NOT e shift

Ripassi tutti e sei gli operatori bitwise con tabelle di verità ed esempi Python e comprenda come gli shift a sinistra e a destra siano collegati alla moltiplicazione e alla divisione per due.

Lezione 1 di 413 passaggi

Operatori bitwise: AND, OR, XOR, NOT e shift è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 1 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 DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.

Perché la manipolazione dei bit è importante

La manipolazione dei bit consente di operare direttamente sulla rappresentazione binaria degli interi. Molti problemi che sembrano complessi diventano banali con il giusto trucco bitwise: trovare un numero mancante in O(n) tempo e O(1) spazio, scambiare variabili senza una variabile temporanea o codificare i sottoinsiemi in modo compatto. I selezionatori usano questi problemi per verificare la comprensione dei concetti di basso livello e la capacità di ragionamento creativo.

Gli interi Python hanno precisione arbitraria: possono essere grandi quanto consente la memoria disponibile; tuttavia, le operazioni sui bit seguono sempre la semantica standard del complemento a due a livello hardware. Tutti e sei gli operatori agiscono bit per bit sulle rappresentazioni binarie degli interi.

# All six bitwise operators in Python
a, b = 0b1010, 0b1100  # 10 and 12 in decimal
print(f'a = {bin(a)} = {a}')
print(f'b = {bin(b)} = {b}')
print(f'a & b  (AND) = {bin(a & b)} = {a & b}')   # 1000 = 8
print(f'a | b  (OR)  = {bin(a | b)} = {a | b}')   # 1110 = 14
print(f'a ^ b  (XOR) = {bin(a ^ b)} = {a ^ b}')   # 0110 = 6
print(f'~a     (NOT) = {~a}')                       # -11 (two's complement)
print(f'a << 1 (LSH) = {bin(a << 1)} = {a << 1}') # 10100 = 20
print(f'a >> 1 (RSH) = {bin(a >> 1)} = {a >> 1}') # 101 = 5

Operatore AND: mascheramento dei bit

L'operatore AND (&) restituisce 1 solo quando entrambi i bit di input sono 1. Il suo uso principale è il mascheramento: selezionare bit specifici di un numero azzerando tutti gli altri. Per verificare se il bit k è impostato nel numero n, valuti n & (1 << k): se il risultato è diverso da zero, il bit k vale 1.

AND serve anche ad azzerare il bit impostato meno significativo: n & (n - 1) rimuove il bit 1 più a destra. Questa tecnica viene usata per contare in modo efficiente i bit impostati e per verificare se un numero è una potenza di due (una potenza di due ha esattamente un bit impostato, quindi n & (n-1) == 0).

n = 0b10110100  # 180

# Check if bit 5 is set (0-indexed from right)
bit_5 = (n >> 5) & 1
print(f'Bit 5 of {n}: {bit_5}')  # 1

# Clear lowest set bit
print(f'n = {bin(n)}')
print(f'n & (n-1) = {bin(n & (n-1))}')  # 10110000, removed the '100'

# Check power of two
for x in [16, 15, 8, 6, 1, 0]:
    is_pow2 = x > 0 and (x & (x - 1)) == 0
    print(f'{x}: power of 2 = {is_pow2}')

Operatore OR: impostazione dei bit

L'operatore OR (|) restituisce 1 se almeno uno dei bit di input è 1. Il suo uso principale è impostare un bit specifico a 1 senza modificare gli altri. Per impostare il bit k nel numero n, utilizzi n | (1 << k). L'1 spostato nella posizione k attiva quel bit; tutti gli altri bit restano invariati, perché qualsiasi valore sottoposto a OR con 0 rimane uguale.

OR viene usato anche per combinare i flag: se i flag delle funzionalità sono rappresentati come singoli bit, è possibile abilitare più flag con OR. Ad esempio, READ | WRITE | EXECUTE combina tre bit di autorizzazione in un unico intero.

# Set bit k in n
def set_bit(n, k):
    return n | (1 << k)

n = 0b1000  # 8
print(f'Original: {bin(n)}')
print(f'Set bit 1: {bin(set_bit(n, 1))}')  # 1010
print(f'Set bit 0: {bin(set_bit(n, 0))}')  # 1001

# Flag combination example
READ    = 0b001  # 1
WRITE   = 0b010  # 2
EXECUTE = 0b100  # 4

perms = READ | EXECUTE
print(f'READ|EXECUTE permissions: {bin(perms)} = {perms}')
print(f'Has READ:    {bool(perms & READ)}')
print(f'Has WRITE:   {bool(perms & WRITE)}')
print(f'Has EXECUTE: {bool(perms & EXECUTE)}')

Operatore XOR: commutazione e differenza

L'operatore XOR (^) restituisce 1 quando i bit di input sono diversi. XOR ha tre importanti proprietà algebriche: a ^ a = 0 (gli input uguali si annullano), a ^ 0 = a (zero è l'elemento neutro) e XOR è sia commutativo sia associativo. Queste proprietà rendono XOR lo strumento principale per trovare gli elementi unici.

XOR serve anche a commutare un bit specifico: n ^ (1 << k) inverte il bit k lasciando invariati gli altri. Se il bit k era 0, diventa 1; se era 1, diventa 0.

# XOR properties
print(5 ^ 5)    # 0 — same values cancel
print(5 ^ 0)    # 5 — zero is identity
print(5 ^ 3 ^ 3)  # 5 — 3 cancels itself

# Toggle bit k
def toggle_bit(n, k):
    return n ^ (1 << k)

n = 0b1010
print(f'Toggle bit 3: {bin(toggle_bit(n, 3))}')  # 0010 (was 1)
print(f'Toggle bit 0: {bin(toggle_bit(n, 0))}')  # 1011 (was 0)

# XOR swap without temp variable
a, b = 7, 13
a = a ^ b
b = a ^ b   # b now gets original a
a = a ^ b   # a now gets original b
print(f'After XOR swap: a={a}, b={b}')  # a=13, b=7

Operatore NOT e complemento a due

L'operatore NOT (~) inverte tutti i bit. In Python, ~n equivale a -(n+1) a causa della rappresentazione in complemento a due. Questo sorprende molte persone: ~5 = -6, non il risultato che ci si aspetterebbe ingenuamente, 0b11111010. Gli interi Python hanno precisione infinita, quindi l'inversione di tutti i bit di un numero positivo produce un risultato negativo in complemento a due.

In pratica, in Python si usa raramente ~ da solo per la manipolazione dei bit. Lo si usa invece insieme ad AND per azzerare bit specifici, oppure si calcola ~n & mask, dove mask limita la larghezza a un numero specifico di bit (ad esempio, & 0xFFFFFFFF per 32 bit).

# NOT in Python: ~n = -(n+1)
for n in [0, 1, 5, 127]:
    print(f'~{n} = {~n}')   # all give -(n+1)

# Clear bit k using NOT
def clear_bit(n, k):
    return n & ~(1 << k)

n = 0b1111
print(f'Clear bit 2: {bin(clear_bit(n, 2))}')  # 1011
print(f'Clear bit 0: {bin(clear_bit(n, 0))}')  # 1110

# Limiting to 32-bit with mask
def bitwise_not_32(n):
    return ~n & 0xFFFFFFFF

print(f'32-bit NOT of 5: {bin(bitwise_not_32(5))}')  # 32 zeros then ones

Spostamento a sinistra: moltiplicazione per potenze di due

L'operatore di spostamento a sinistra (<<) sposta tutti i bit a sinistra di k posizioni, riempiendo con zeri le posizioni libere a destra. È equivalente a moltiplicare per 2^k. Uno spostamento a sinistra di 1 raddoppia il valore; uno spostamento a sinistra di k lo moltiplica per 2^k.

Nei problemi da colloquio, gli spostamenti a sinistra vengono usati soprattutto per creare maschere di bit: 1 << k crea un numero con il solo bit k impostato. Questa è la base di tutte le operazioni di manipolazione dei bit: impostare, azzerare, commutare e verificare singoli bit sono operazioni che iniziano tutte con 1 << k.

# Left shift = multiply by 2^k
n = 1
for k in range(8):
    print(f'1 << {k} = {1 << k}')   # 1,2,4,8,16,32,64,128

# Practical use: creating bitmasks
def bit_mask(k):
    return 1 << k

print(f'\nBitmask for bit 0: {bin(bit_mask(0))}')  # 1
print(f'Bitmask for bit 3: {bin(bit_mask(3))}')  # 1000
print(f'Bitmask for bit 7: {bin(bit_mask(7))}')  # 10000000

# Fast exponentiation: 2^10 = 1024
print(f'2^10 = {1 << 10}')  # 1024

Spostamento a destra: divisione per potenze di due

L'operatore di spostamento a destra (>>) sposta tutti i bit a destra di k posizioni, scartando i k bit più a destra. È equivalente alla divisione intera per 2^k. Lo spostamento a destra di Python è sempre aritmetico: i bit più a sinistra vengono riempiti con il bit di segno (0 per i numeri positivi, 1 per quelli negativi).

Un trucco comune nei colloqui: per estrarre il bit k dal numero n, utilizzi (n >> k) & 1. In questo modo il bit k viene spostato nella posizione 0 e tutti gli altri bit vengono mascherati. È il modo più pulito per verificare un bit specifico senza dover calcolare e confrontare una maschera completa.

# Right shift = integer division by 2^k
n = 64
for k in range(7):
    print(f'{n} >> {k} = {n >> k}')   # 64,32,16,8,4,2,1

# Extract bit k from n
def get_bit(n, k):
    return (n >> k) & 1

n = 0b10110101  # 181
print(f'\nBits of {n} ({bin(n)}):')
for k in range(8):
    print(f'  Bit {k}: {get_bit(n, k)}')

# Negative number right shift (arithmetic)
print(f'-8 >> 1 = {-8 >> 1}')   # -4 (fills with sign bit 1)

Scheda riassuntiva dei trucchi pratici sui bit

Questa è una raccolta delle espressioni più comuni per la manipolazione dei bit che incontrerà nei colloqui. Memorizzi questi schemi: ricorrono continuamente in decine di problemi:

n & 1 — verificare se n è dispari
n & (n-1) — azzerare il bit impostato meno significativo
n & -n — isolare il bit impostato meno significativo
n | (1 << k) — impostare il bit k
n & ~(1 << k) — azzerare il bit k
n ^ (1 << k) — commutare il bit k
(n >> k) & 1 — verificare il bit k

# Bit trick cheatsheet — all at once
n = 0b10110100  # 180

print(f'n = {bin(n)} = {n}')
print(f'n & 1       (odd check)         = {n & 1}')          # 0: even
print(f'n & (n-1)   (clear lowest bit)  = {bin(n & (n-1))}')
print(f'n & -n      (isolate lowest bit) = {bin(n & -n)}')
print(f'n | (1<<1)  (set bit 1)          = {bin(n | (1<<1))}')
print(f'n & ~(1<<2) (clear bit 2)        = {bin(n & ~(1<<2))}')
print(f'n ^ (1<<5)  (toggle bit 5)       = {bin(n ^ (1<<5))}')
print(f'(n>>4) & 1  (check bit 4)        = {(n>>4) & 1}')

Conteggio dei bit impostati (popcount)

Il conteggio del numero di bit 1 in un intero si chiama population count (popcount). L'approccio ingenuo scorre tutti i bit. Il trucco di Brian Kernighan è più veloce: azzera ripetutamente il bit impostato meno significativo con n &= n - 1, contando le iterazioni finché n diventa 0. Ogni iterazione rimuove esattamente un bit 1, quindi il ciclo viene eseguito esattamente tante volte quanti sono i bit 1.

Python 3.10+ fornisce int.bit_count(), che restituisce direttamente il conteggio. Per le versioni precedenti, il trucco di Kernighan è l'approccio manuale standard. Questa tecnica risolve anche il problema «Hamming Weight» su LeetCode.

# Method 1: naive O(log n)
def count_bits_naive(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

# Method 2: Brian Kernighan O(k) where k = number of set bits
def count_bits_fast(n):
    count = 0
    while n:
        n &= n - 1   # clear lowest set bit
        count += 1
    return count

# Method 3: Python built-in (3.10+)
# n.bit_count()

for x in [0, 1, 7, 255, 180, 1024]:
    naive = count_bits_naive(x)
    fast  = count_bits_fast(x)
    print(f'{x:4d} ({bin(x):10s}): naive={naive}, fast={fast}')

Manipolazione dei bit in Python: aspetti importanti

A differenza di C/Java, gli interi Python hanno dimensioni arbitrarie: non esiste overflow a 32 o 64 bit. Questo significa che, quando si risolvono problemi che richiedono un comportamento a 32 bit, è necessario applicare manualmente una maschera ai risultati: utilizzi & 0xFFFFFFFF per conservare solo i 32 bit meno significativi.

L'operatore NOT ~n in Python restituisce -(n+1), non la versione con i bit invertiti che ci si potrebbe aspettare da C. Per i problemi a 32 bit, utilizzi ~n & 0xFFFFFFFF oppure calcoli 0xFFFFFFFF ^ n per ottenere il complemento a 32 bit previsto. Queste differenze traggono in inganno molti candidati abituati alla manipolazione dei bit in stile C.

# Python vs C gotchas
# In C: unsigned 32-bit NOT of 5 = 4294967290
# In Python: ~5 = -6
print(f'Python ~5 = {~5}')              # -6
print(f'32-bit ~5 = {~5 & 0xFFFFFFFF}') # 4294967290

# No integer overflow in Python
big = 1 << 100   # 2^100: huge number, no overflow
print(f'2^100 = {big}')  # works fine

# Right shift on negatives: arithmetic (sign-extending)
print(f'-1 >> 3 = {-1 >> 3}')   # -1 (all ones shifted in)

# Safe 32-bit mask for problems expecting C/Java semantics
MASK32 = 0xFFFFFFFF
result = (5 + 0xFFFFFFFE) & MASK32  # simulates 32-bit overflow
print(f'5 + (-2) in 32-bit = {result}')  # 3

Operatori di shift e moltiplicazione

Gli spostamenti a sinistra e a destra offrono un modo estremamente veloce per moltiplicare o dividere per potenze di due. A livello hardware, gli spostamenti dei bit sono operazioni eseguite con una singola istruzione, mentre moltiplicazione e divisione richiedono più cicli. In Python, la moltiplicazione tra interi è già efficiente, ma comprendere questa relazione aiuta a visualizzare più chiaramente i pattern dei bit.

Un'identità utile: per verificare se n è un multiplo di 2^k, utilizzi (n & (2^k - 1)) == 0. La maschera 2^k - 1 ha tutti i k bit inferiori impostati a 1; applicare AND a questa maschera restituisce il resto della divisione per 2^k. È equivalente a n % (2^k), ma più veloce nei linguaggi basati su C.

# Shift vs arithmetic equivalence
for k in range(1, 5):
    n = 48
    print(f'{n} * 2^{k} = {n * (2**k)} = {n << k} (left shift)')
    print(f'{n} // 2^{k} = {n // (2**k)} = {n >> k} (right shift)')
    print()

# Check divisibility by power of 2
def divisible_by_power_of_2(n, k):
    mask = (1 << k) - 1   # 2^k - 1: lower k bits all 1
    return (n & mask) == 0

for n in [16, 24, 32, 15, 100]:
    print(f'{n} divisible by 4? {divisible_by_power_of_2(n, 2)}')

Verifica rapida

Verifichi la sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.

Rispondi nella lezione interattiva

Riepilogo della lezione

In questa lezione ha appreso che: AND maschera i bit, OR li imposta, XOR li commuta e rileva le differenze, NOT li inverte (restituendo -(n+1) in Python) e gli shift moltiplicano o dividono per potenze di due, n & (n-1) azzera il bit impostato meno significativo ed è alla base dei controlli delle potenze di due e del conteggio dei bit e Python non ha overflow a larghezza fissa, quindi i problemi a 32 bit richiedono un mascheramento esplicito con & 0xFFFFFFFF. Ora esploreremo la proprietà di auto-inversione di XOR per risolvere la famiglia di problemi del numero singolo.

Gratis per iniziare

Impara Python con un tutor IA — gratis

Scrivi ed esegui vero codice nel tuo browser, ricevi aiuto istantaneo da un tutor IA disponibile 24/7, e riprendi da dove hai lasciato sul web o nell'app.

Corsi: 30
Lezioni: 120

Inizia a imparare gratis Visualizza il corso completo

Domande Frequenti

La lezione «Operatori bitwise: AND, OR, XOR, NOT e shift» è gratuita?

Sì — il testo completo di «Operatori bitwise: AND, OR, XOR, NOT e shift» è 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 DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.

Cosa imparerò in «Operatori bitwise: AND, OR, XOR, NOT e shift»?

Ripassi tutti e sei gli operatori bitwise con tabelle di verità ed esempi Python e comprenda come gli shift a sinistra e a destra siano collegati alla moltiplicazione e alla divisione per due. Eserciti DSA Interview Prep 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 DSA Interview Prep?

Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.

Quanto tempo richiede la lezione «Operatori bitwise: AND, OR, XOR, NOT e shift»?

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 DSA Interview Prep?

Sì. Ogni lezione DSA Interview Prep 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

Operatori bitwise: AND, OR, XOR, NOT e shift
Single Number e proprietà di XOR
Maschere di bit: impostare, azzerare, invertire e verificare
Conteggio dei bit, numero mancante e inversione dei bit

← Torna a DSA Interview Prep