Posso allocare un numero specifico di bit in C?
https://stackoverflow.com/questions/284519
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Sto cercando di memorizzare una grande quantità di informazioni booleane che vengono determinate in fase di esecuzione. Mi chiedevo quale potesse essere il metodo migliore.
Attualmente sto provando ad allocare la memoria usando:
pStatus = malloc((<number of data points>/8) + 1);
pensando che questo mi darà abbastanza bit con cui lavorare. Potrei quindi fare riferimento a ciascun valore booleano usando il puntatore nella notazione dell'array:
pStatus[element]
Sfortunatamente questo non sembra funzionare molto bene. Innanzitutto, ho difficoltà a inizializzare la memoria sul valore intero 0. Questo può essere fatto usando memset()? Tuttavia, non penso che ciò influisca sul motivo per cui mi arresto in modo anomalo quando provo ad accedere a <=>.
Inoltre, non sono del tutto convinto che questo approccio sia il migliore da utilizzare. Quello che voglio davvero è essenzialmente una gigantesca maschera di bit che riflette lo stato dei valori booleani. Ho perso qualcosa?
Soluzione
pStatus = malloc((<number of data points>/8) + 1);
Questo alloca abbastanza byte per i tuoi bit. Tuttavia,
pStatus[element]
Questo accede all'elemento byte , non bit. Pertanto, quando l'elemento è più di un ottavo del numero totale di bit, si accede alla fine dell'array allocato.
Definirei alcune funzioni di supporto
int get_bit(int element)
{
uint byte_index = element/8;
uint bit_index = element % 8;
uint bit_mask = ( 1 << bit_index);
return ((pStatus[byte_index] & bit_mask) != 0);
}
void set_bit (int element)
{
uint byte_index = element/8;
uint bit_index = element % 8;
uint bit_mask = ( 1 << bit_index);
pStatus[byte_index] |= bit_mask);
}
void clear_bit (int element)
{
uint byte_index = element/8;
uint bit_index = element % 8;
uint bit_mask = ( 1 << bit_index);
pStatus[byte_index] &= ~bit_mask;
}
(errore nel controllo dell'intervallo di elementi lasciato fuori per chiarezza. Potresti anche creare queste macro)
Altri suggerimenti
... pensando che questo mi darà abbastanza bit con cui lavorare. Potrei quindi fare riferimento a ciascun valore booleano usando il puntatore nella notazione dell'array:
pStatus[element]
sta indirizzando byte , non bit. Vuoi qualcosa del tipo:
pStatus[element/8] & (1 << (element % 8))
Piccolo punto: per ottenere memoria sufficiente per memorizzare N bit, (N / 8) + 1 byte è impreciso (può essere uno di troppo).
(N + 7) / 8 è sempre il numero minimo, tuttavia.
Bene, la risposta più semplice sarebbe usare calloc invece di malloc.
È definito per inizializzare la memoria che alloca a zero e spesso può farlo usando i trucchi di mappatura della pagina.
Questo risolverà il problema di inizializzazione della memoria. Le altre dozzine di post qui sembrano affrontare adeguatamente il problema dell'indicizzazione e il fatto che di tanto in tanto assegni un byte extra (oh l'orrore!), Quindi non ripeterò il loro contenuto qui.
pStatus [element] ti darà un intero byte a quell'indirizzo.
Per impostare un elemento particolare dovresti fare qualcosa del tipo:
pStatus[element >> 3] |= 1 << (element & 7);
Per ripristinare un elemento:
pStatus[element >> 3] &= ~1 << (element & 7);
e per testare un elemento:
if (pStatus[element >> 3] & (1 << (element & 7)) != 0)
la dotazione iniziale dovrebbe essere
pstatus = malloc((<number of data points> + 7) / 8)
quello che avevi funzionerà ma sprecherà un byte di tanto in tanto
Non posso fare a meno di notare che tutte le risposte in C qui sembrano supporre che un byte sia 8 bit. Questo non è necessariamente vero in C (anche se ovviamente sarà vero sulla maggior parte dell'hardware tradizionale), quindi fare questo presupposto nel codice è piuttosto male.
Il modo corretto di scrivere codice indipendente dall'architettura è
#include <limits.h>
e quindi utilizzare la CHAR_BIT macro ovunque sia necessario " il numero di bit in un char " ;.
Renditi più felice e definisci un tipo e le funzioni per operare su quel tipo. In questo modo se scopri che gli accessi ai bit sono troppo lenti, puoi cambiare l'unità di memoria per booleano in un byte / parola / long o adottare strutture di dati sparse / dinamiche se la memoria è davvero un problema (cioè, se i tuoi set sono per lo più zeri , potresti semplicemente tenere un elenco con le coordinate degli 1.
Puoi scrivere il tuo codice per essere completamente immune alle modifiche all'implementazione del tuo bit vector.
pStatus [elemento] non risolve il bit. Il byte esatto che ottiene dipende dal tipo di pStatus - presumo char * o equivalente - quindi pStatus [elemento] ti fornisce il byte dell'elemento.
È possibile impostare memset su 0, sì.
pStatus = malloc((<number of data points>/8) + 1);
Quella parte va bene.
pStatus[element]
ecco dove hai problemi. Sei byte di indirizzo, quando vuoi indirizzare i bit.
pStatus[element / 8 ]
ti darà il byte giusto nell'array.
Devi allocare c = malloc((N+7)/8) byte e puoi impostare l'ennesimo con
c[n/8]=((c[n/8] & ~(0x80 >> (n%8))) | (0x80>>(n%8)));
cancella con
c[n/8] &= ~(0x80 >> (n%8));
e prova con
if(c[n/8] & (0x80 >> (n%8))) blah();
Se non ti dispiace dover scrivere wrapper, potresti anche usare bit_set o bit_vector dalla STL di C ++, sembra che (specialmente quest'ultimo) abbiano esattamente ciò di cui hai bisogno, già codificato, testato e impacchettato (e molti campane e fischietti).
È un vero peccato che manchi un modo semplice per usare il codice C ++ nelle applicazioni C (no, creare un wrapper non è semplice per me, né divertente, e significa più lavoro a lungo termine).
Cosa ci sarebbe di sbagliato in std::vector<bool>?
Mi stupisce che qui una sola risposta menzioni CHAR_BIT. Un byte è spesso 8 bit, ma non sempre.
Il codice di allocazione è corretto, vedere le funzioni set_bit() e get_bit() fornite in questa risposta per accedere al valore booleano.
Se sei limitato a pochi bit puoi invece che la soluzione eaanon01 usa anche la funzione c integrata di bitfield (ci sono pochissime occasioni in cui potresti usarli, ma questo sarebbe uno)
Per questa roba da sbattere un po 'posso raccomandare: Herny Warrens & Quot; Hacker Delight & Quot;
Il valore booleano è " mai " un valore separato in C. Quindi potrebbe essere una struttura per farti andare.
È vero che non si inizializza l'area mem, quindi è necessario farlo singolarmente.
Ecco un semplice esempio di come potresti farlo con le strutture e gli enum dei sindacati
typedef unsigned char BYTE;
typedef unsigned short WORD;
typedef unsigned long int DWORD;
typedef unsigned long long int DDWORD;
enum STATUS
{
status0 = 0x01,
status1 = 0x02,
status2 = 0x04,
status3 = 0x08,
status4 = 0x10,
status5 = 0x20,
status6 = 0x40,
status7 = 0x80,
status_group = status0 + status1 +status4
};
#define GET_STATUS( S ) ( ((status.DDBuf&(DDWORD)S)==(DDWORD)S) ? 1 : 0 )
#define SET_STATUS( S ) ( (status.DDBuf|= (DDWORD)S) )
#define CLR_STATUS( S ) ( (status.DDBuf&= ~(DDWORD)S) )
static union {
BYTE BBuf[8];
WORD WWBuf[4];
DWORD DWBuf[2];
DDWORD DDBuf;
}status;
int main(void)
{
// Reset status bits
status.BBuf[0] = 0;
printf( "%d \n", GET_STATUS( status0 ) );
SET_STATUS( status0 );
printf( "%d \n", GET_STATUS( status0 ) );
CLR_STATUS(status0);
printf( "%d \n", GET_STATUS( status0 ) );
SET_STATUS( status_group );
printf( "%d \n", GET_STATUS( status0 ) );
system( "pause" );
return 0;
}
Spero che questo aiuti. Questo esempio può gestire fino a 64 stati booleani e potrebbe essere facilmente esteso.
Questo esempio si basa su Char = 8 bit int = 16 bit long int = 32 bit e long long int = 64 bit
Ora ho anche aggiunto il supporto per i gruppi di stato.
