Rilasciato · in miglioramento
Algorithm
La manipolazione dei bit tratta gli interi come cifre binarie e usa AND, OR, XOR e shift per gestire insiemi, flag e DP con bitmask in modo rapido e compatto.
La manipolazione dei bit considera un intero come una sequenza di 0 e 1 e usa AND, OR, XOR, NOT e shift per leggere, accendere, spegnere o invertire singoli bit. I computer memorizzano gli interi in binario e i negativi in complemento a due, quindi ognuna di queste operazioni corrisponde di solito a una sola istruzione della CPU. Un'espressione breve come x & -x (il bit a 1 più basso) o x & (x - 1) (quel bit azzerato) può sostituire un intero ciclo.
È importante perché un solo intero può rappresentare un insieme di una ventina di elementi: così si possono visitare tutti i sottoinsiemi e usare gli insiemi come stati nella programmazione dinamica con bitmask. Nei colloqui tecnici compaiono spesso l'enumerazione dei sottoinsiemi, le proprietà dello XOR e il popcount, e nel software reale i bit servono per permessi dei file, feature flag, calcolo delle sottoreti, tabelle hash e indici bitmap. Le regole però cambiano da linguaggio a linguaggio: gli interi di Python sono illimitati, JavaScript converte a 32 bit e offre >>>, anche Java ha >>>, e in C++ conviene usare tipi senza segno per le maschere.
Conviene iniziare convertendo a mano i numeri in binario e in complemento a due. Poi si esercitano le quattro operazioni su un singolo bit (accendere, spegnere, invertire, verificare) e si stampano tutti i sottoinsiemi facendo scorrere una maschera da 0 a 2^n - 1. Si passa quindi all'enumerazione delle sottomaschere e ai problemi di DP con bitmask, come l'assegnazione dei compiti o il commesso viaggiatore, e infine si controllano larghezza degli interi e regole di shift dei propri linguaggi.
Un numero negativo si ottiene invertendo tutti i bit e sommando 1. Lo shift a sinistra moltiplica per 2, quello a destra divide per 2, e i linguaggi distinguono tra shift aritmetico e logico.
Con la maschera 1 << i, OR accende il bit i, AND NOT lo spegne e XOR lo inverte. x & -x isola il bit a 1 più basso e x & (x - 1) lo rimuove.
I sottoinsiemi di n elementi corrispondono uno a uno agli interi da 0 a 2^n - 1, e unione, intersezione e differenza richiedono una sola operazione bit a bit.
I bit a 1 si contano ripetendo x &= x - 1 o con una funzione integrata. Poiché a ^ a = 0, lo XOR trova il valore senza coppia e fornisce distanze di Hamming e codici Gray.
popcount conta i bit a 1 azzerando il più basso con x &= x - 1 finché non ne resta nessuno. subsets fa scorrere una maschera da 0 a 2^n - 1 e sceglie gli elementi il cui bit è acceso, generando tutti i sottoinsiemi. L'ultima riga mostra 12 & -12 = 4 (il bit a 1 più basso), 12 & 11 = 8 (quel bit azzerato) e x ^ x = 0. Si esegue con python bit_manipulation.py.
bit_manipulation.py
def popcount(x: int) -> int:
count = 0
while x:
x &= x - 1 # clear the lowest set bit
count += 1
return count
def subsets(items):
n = len(items)
for mask in range(1 << n):
yield mask, [items[i] for i in range(n) if (mask >> i) & 1]
for mask, chosen in subsets(["a", "b", "c"]):
print(format(mask, "03b"), popcount(mask), chosen)
x = 12
print(x & -x, x & (x - 1), x ^ x) # 4 8 0
python bit_manipulation.pySei capitoli che ti accompagnano dall'installazione ai concetti chiave di Manipolazione dei bit.
Fai domande, condividi la tua esperienza e scambia opinioni su Manipolazione dei bit.
Ancora nessuna discussione. Avvia la prima.
0 commenti
Accedi · Accedi per lasciare un commento.
Scrivi tu il primo commento.