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.
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.
Le operazioni più comuni su un bit array includono:
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:
Esempi di operazioni bitwise: dati i due bit array "01010101" e "00001111", le operazioni bitwise ritornano i seguenti risultati:
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.
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.
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.
Molti linguaggi di programmazione offrono librerie o strutture dati integrate per lavorare con i bit array. Ad esempio:
std::bitset, che implementa un bit array con una lunghezza fissa.bitarray o tramite l'uso di oggetti int e operazioni bitwise.BitSet di Java implementa un bit array dinamico, che consente di espandere o ridurre la dimensione del bit array durante l'esecuzione.