Puis-je allouer un nombre spécifique de bits en C?
https://stackoverflow.com/questions/284519
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'essaie de stocker une grande quantité d'informations booléennes déterminées au moment de l'exécution. Je me demandais quelle serait la meilleure méthode.
J'essaie actuellement d'allouer la mémoire en utilisant:
pStatus = malloc((<number of data points>/8) + 1);
pensant que cela me donnerait assez de bits pour travailler. Je pourrais ensuite référencer chaque valeur booléenne en utilisant le pointeur en notation tableau:
pStatus[element]
Malheureusement, cela ne semble pas fonctionner très bien. Premièrement, j'ai des difficultés à initialiser la mémoire à la valeur entière 0. Cela peut-il être fait avec memset()? Néanmoins, je ne pense pas que cela ait un impact sur la cause de mon plantage lors de la tentative d'accès à <=>.
Je ne suis pas non plus convaincu que cette approche soit la meilleure à utiliser. Ce que je veux vraiment, c’est essentiellement un masque de bits géant qui reflète l’état des valeurs booléennes. Ai-je oublié quelque chose?
La solution
pStatus = malloc((<number of data points>/8) + 1);
Ceci alloue suffisamment d'octets pour vos bits. Cependant,
pStatus[element]
Ceci accède à l'élément octet , pas bit. Ainsi, lorsque l'élément représente plus d'un huitième du nombre total de bits, vous accédez à la fin du tableau alloué.
Je définirais quelques fonctions d'assistance
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;
}
(vérification d'erreur sur la plage d'élément laissé pour plus de clarté. Vous pouvez également créer cette macro)
Autres conseils
... pensant que cela me donnerait assez de bits pour travailler. Je pourrais ensuite référencer chaque valeur booléenne en utilisant le pointeur en notation tableau:
pStatus[element]
s’adresse à octets , pas à des bits. Vous voulez quelque chose comme:
pStatus[element/8] & (1 << (element % 8))
Petit point: obtenir assez de mémoire pour stocker N bits, (N / 8) + 1 octet est imprécis (peut être un de trop).
(N + 7) / 8 est toujours le nombre minimal, cependant.
La réponse la plus simple serait d'utiliser calloc au lieu de malloc.
Il est défini pour initialiser la mémoire allouée à zéro et peut souvent le faire en utilisant des astuces de mappage de pages.
Cela réglera votre problème d’initialisation de la mémoire. Les douze autres articles publiés ici semblent résoudre correctement le problème d’indexation et le fait que vous allouiez occasionnellement un octet supplémentaire (oh l’horreur!), Je ne vais donc pas en répéter le contenu ici.
pStatus [element] vous donnera un octet entier à cette adresse.
Pour définir un élément particulier, procédez comme suit:
pStatus[element >> 3] |= 1 << (element & 7);
Pour réinitialiser un élément:
pStatus[element >> 3] &= ~1 << (element & 7);
et pour tester un élément:
if (pStatus[element >> 3] & (1 << (element & 7)) != 0)
l'allocation initiale doit être
pstatus = malloc((<number of data points> + 7) / 8)
ce que vous aviez fonctionnera mais gaspillera occasionnellement un octet
Je ne peux pas m'empêcher de remarquer que toutes les réponses en C semblent supposer qu'un octet est de 8 bits. Ce n’est pas forcément vrai en C (bien que ce soit évidemment vrai pour la plupart des matériels traditionnels), donc cette hypothèse dans le code est plutôt mauvaise.
La bonne façon d'écrire du code indépendant de l'architecture est de
#include <limits.h>
puis utilisez la macro CHAR_BIT partout où vous avez besoin & "; le nombre de bits dans un char &";
Rendez-vous plus heureux et définissez un type et des fonctions pour fonctionner sur ce type. Ainsi, si vous découvrez que les accès aux bits sont trop lents, vous pouvez modifier l’unité de mémoire par booléen en octet / mot / long ou adopter des structures de données fragmentées / dynamiques si la mémoire pose vraiment problème (c'est-à-dire si vos ensembles sont principalement à zéros. , vous pouvez simplement garder une liste avec les coordonnées du 1.
Vous pouvez écrire votre code pour qu'il soit totalement immunisé contre les modifications apportées à la mise en œuvre de votre vecteur de bits.
pStatus [élément] ne traite pas le bit. L’octet exact qu’il obtient dépend du type de pStatus - je suppose que char * ou l’équivalent - afin que pStatus [élément] vous fournisse l’objet de l’élément.
Vous pouvez memset régler à 0, oui.
pStatus = malloc((<number of data points>/8) + 1);
Cette partie va bien.
pStatus[element]
voici où vous avez des problèmes. Vous êtes adresse, lorsque vous souhaitez adresser des bits.
pStatus[element / 8 ]
vous obtiendra le bon octet dans le tableau.
Vous devez attribuer c = malloc((N+7)/8) octets et vous pouvez définir le nième avec
c[n/8]=((c[n/8] & ~(0x80 >> (n%8))) | (0x80>>(n%8)));
effacer avec
c[n/8] &= ~(0x80 >> (n%8));
et testez avec
if(c[n/8] & (0x80 >> (n%8))) blah();
Si cela ne vous dérange pas d’avoir à écrire des wrappers, vous pouvez aussi utiliser bit_set ou bit_vector à partir du fichier STL de C ++. Il semble qu’ils (surtout le dernier) aient exactement ce dont vous avez besoin, déjà codé, testé et emballé (et plein cloches et sifflets).
C’est vraiment dommage que nous n’ayons pas de solution simple pour utiliser le code C ++ dans les applications C (non, créer un wrapper n’est pas simple pour moi, ni amusant, et signifie plus de travail à long terme).
Quel serait le problème avec std::vector<bool>?
Cela me surprend qu'une seule réponse ici mentionne CHAR_BIT. Un octet contient souvent 8 bits, mais pas toujours.
Votre code d’attribution est correct. Voir les fonctions set_bit() et get_bit() décrites dans cette réponse pour accéder au booléen.
Si vous êtes limité à quelques bits, vous pouvez utiliser la fonction intégrée c de bitfield au lieu de la solution eaanon01.
Je peux recommander ces trucs un peu cinglants: Herny Warrens & "Le plaisir des pirates &";
Le booléen est & "jamais &"; une valeur distincte en C. Une structure peut donc vous être utile.
Il est vrai que vous n'initialisez pas la zone mémoire, vous devez donc le faire individuellement.
Voici un exemple simple montrant comment vous pouvez le faire avec des structures et des énumérations d'unions
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;
}
J'espère que ça aide. Cet exemple peut gérer jusqu'à 64 statuts et peut être facilement étendu.
Cet exemple est basé sur Char = 8 bits int = 16 bits long int = 32 bits et long long int = 64 bits
J'ai également ajouté un support pour les groupes de statut.
