Bit array

Un bit array (chiamato anche bitset o bit vector) è una struttura dati che memorizza una sequenza binaria di bit, in cui ogni bit rappresenta una variabile indipendente. Questa struttura è molto utilizzata in informatica per rappresentare in modo compatto insiemi di dati in cui ogni elemento può assumere solo un valore binario.

Struttura e rappresentazione

Un bit array è tipicamente implementato riservando una quantità di memoria, espressa in bit, di dimensione pari alla dimensione dell'array: ad esempio, un bit array di lunghezza 8 (contenente 8 bit) occuperà un byte di memoria.

In alcune implementazioni, i bit array sono rappresentati come array di interi, in cui ciascun intero codifica una porzione di bit array. Ogni bit di un intero è utilizzato per rappresentare un valore binario, e l'accesso a un singolo bit viene effettuato tramite operazioni bitwise.

Operazioni comuni

Le operazioni più comuni su un bit array includono:

Assegnamento (Set): assegna a un determinato bit il valore 1.
Azzeramento (Clear): assegna a un determinato bit il valore 0.
Controllo (Test): verifica il valore di un determinato bit, se 1 o 0.
Complemento (Toggle) o negazione (NOT): inverte il valore di un determinato bit.
Operazioni su base bit (bitwise): operazioni booleane AND, OR, XOR che vengono applicate a bit a bit tra due o più bit array.

Esempio di operazioni

Considerando il bit array "11110000", dove il bit meno significativo ha indice "0" e quello più significativo ha indice "7", le operazioni descritte sopra determinano questo risultato:

Set(bit 0): "11110000" diventa "11110001"
Clear(bit 7): "11110000" diventa "01110000"
Test(bit 6): ritorna come risultato "1"
Toggle applicato all'intero bit array: "11110000" diventa "00001111"

Esempi di operazioni bitwise: dati i due bit array "01010101" e "00001111", le operazioni bitwise ritornano i seguenti risultati:

01010101 AND 00001111 = 00000101
01010101 OR 00001111 = 01011111
01010101 XOR 00001111 = 01011010

Utilizzo

Rappresentazione di insiemi

Un uso comune dei bit array è nella rappresentazione di insiemi, dove ogni bit corrisponde a un elemento dell'insieme. Un bit impostato a 1 indica che l'elemento è presente nell'insieme, mentre un bit impostato a 0 indica che l'elemento non è presente.

Algoritmi e ottimizzazione della memoria

I bit array sono spesso utilizzati per risparmiare memoria rispetto ad altre strutture dati più grandi come gli array di interi. Ad esempio, se un insieme ha solo pochi elementi su un grande intervallo di possibili valori, un bit array può essere utilizzato per rappresentare l'insieme in modo molto compatto.

Reti e compressione

In alcuni algoritmi di compressione e in applicazioni legate alle reti, i bit array sono utilizzati per rappresentare e manipolare flussi di dati binari, come nelle operazioni di codifica e decodifica.

Esempi di utilizzo

Banchi di memoria: I bit array sono utilizzati nei banchi di memoria per gestire e rappresentare lo stato di ciascun blocco di memoria.
Filtri di Bloom: I bit array sono utilizzati come parte fondamentale dell'implementazione dei filtri di Bloom, una struttura dati probabilistica per la rappresentazione di insiemi di elementi con il rischio di falsi positivi.
Compressione di dati: Strutture come i bit array sono fondamentali in alcuni algoritmi di compressione, dove è essenziale manipolare i dati a livello di bit per ridurre la dimensione dei file.

Implementazioni nei linguaggi di programmazione

Molti linguaggi di programmazione offrono librerie o strutture dati integrate per lavorare con i bit array. Ad esempio:

C++: La libreria standard di C++ fornisce la classe std::bitset, che implementa un bit array con una lunghezza fissa.
Python: In Python, i bit array sono rappresentati tramite moduli come bitarray o tramite l'uso di oggetti int e operazioni bitwise.
Java: La classe BitSet di Java implementa un bit array dinamico, che consente di espandere o ridurre la dimensione del bit array durante l'esecuzione.

Vantaggi

Compattezza: I bit array sono altamente compatti in memoria, poiché ogni bit occupa solo un singolo bit di spazio.
Velocità: Le operazioni bitwise sono generalmente molto veloci e possono essere effettuate in modo molto efficiente dalla maggior parte delle architetture hardware.
Facilità di utilizzo in algoritmi: I bit array sono utili in numerosi algoritmi che richiedono operazioni su insiemi o su sequenze di valori binari.

Svantaggi

Limitata flessibilità: La lunghezza di un bit array è solitamente fissa, e non supporta facilmente operazioni di ridimensionamento dinamico.
Difficoltà di gestione: In alcuni casi, lavorare con bit array può risultare più complesso rispetto a strutture dati più astratte, come gli array di interi.