Comment utiliser Bit-Fields pour économiser de la mémoire?

Il s’agit de la norme ANSI-C (C90). Voici ce que je sais:

  • Je peux directement dire au compilateur combien de bits je veux pour une variable spécifique.
  • Si je veux 1 bit qui peut avoir les valeurs zéro ou un.
  • ou 2 bits pour les valeurs 0,1,2,3, et ainsi de suite …;

Je connais la syntaxe.

J’ai un problème concernant les champs de bits:

  • Je veux définir une structure SET.
  • Il peut avoir un maximum de 1024 éléments (il peut en avoir moins, mais le maximum est de 1024 éléments).
  • Le domaine de l’ensemble est compris entre 1 et 1024. Ainsi, un élément peut avoir n’importe quelle valeur 1-1024.

J’essaie de créer une structure pour un SET et elle doit être aussi efficace que possible pour la partie mémoire.

J’ai essayé:

typedef struct set { unsigned int var: 1; } SET; //now define an array of SETS SET array_of_sets[MAX_SIZE] //didn't define MAX_SIZE, but no more than 1024 elements in each set. 

Je sais que ce n’est pas efficace. peut-être que ce n’est même pas bon pour ce que je veux. C’est pourquoi je cherche de l’aide.

Comme indiqué dans de nombreux commentaires, l’utilisation d’un champ de bits n’est pas la solution. Vous ne pouvez utiliser que 128 octets de stockage pour votre ensemble contenant les valeurs 1..1024. Vous devrez mapper la valeur N sur le bit N-1 (vous disposez donc des bits 0..1023). Vous devez également décider des opérations dont vous avez besoin pour votre ensemble. Ce code prend en charge “create”, “destroy”, “insert”, “delete” et “in_set”. Il ne supporte pas l’itération sur les éléments de l’ensemble; cela peut être ajouté si vous le voulez.

sets.h

 #ifndef SETS_H_INCLUDED #define SETS_H_INCLUDED typedef struct Set Set; enum { MAX_ELEMENTS = 1024 }; extern Set *create(void); extern void destroy(Set *set); extern void insert(Set *set, int value); extern void delete(Set *set, int value); extern int in_set(Set *set, int value); #endif /* SETS_H_INCLUDED */ 

sets.c

 #include "sets.h" #include  #include  #include  #include  typedef unsigned long Bits; #define BITS_C(n) ((Bits)(n)) enum { ARRAY_SIZE = MAX_ELEMENTS / (sizeof(Bits) * CHAR_BIT) }; struct Set { Bits set[ARRAY_SIZE]; }; Set *create(void) { Set *set = malloc(sizeof(*set)); if (set != 0) memset(set, 0, sizeof(*set)); return set; } void destroy(Set *set) { free(set); } void insert(Set *set, int value) { assert(value >= 1 && value <= MAX_ELEMENTS); value--; /* 0..1023 */ int index = value / (sizeof(Bits) * CHAR_BIT); int bitnum = value % (sizeof(Bits) * CHAR_BIT); Bits mask = BITS_C(1) << bitnum; /* printf("I: %d (%d:%d:0x%.2lX)\n", value+1, index, bitnum, mask); */ set->set[index] |= mask; } void delete(Set *set, int value) { assert(value >= 1 && value <= MAX_ELEMENTS); value--; /* 0..1023 */ int index = value / (sizeof(Bits) * CHAR_BIT); int bitnum = value % (sizeof(Bits) * CHAR_BIT); Bits mask = BITS_C(1) << bitnum; /* printf("D: %d (%d:%d:0x%.2lX)\n", value+1, index, bitnum, mask); */ set->set[index] &= ~mask; } /* C90 does not support  */ int in_set(Set *set, int value) { assert(value >= 1 && value <= MAX_ELEMENTS); value--; /* 0..1023 */ int index = value / (sizeof(Bits) * CHAR_BIT); int bitnum = value % (sizeof(Bits) * CHAR_BIT); Bits mask = BITS_C(1) << bitnum; /* printf("T: %d (%d:%d:0x%.2lX) = %d\n", value+1, index, bitnum, mask, (set->set[index] & mask) != 0); */ return (set->set[index] & mask) != 0; } #include  enum { NUMBERS_PER_LINE = 15 }; int main(void) { Set *set = create(); if (set != 0) { int i; int n = 0; for (i = 1; i <= MAX_ELEMENTS; i += 4) insert(set, i); for (i = 3; i <= MAX_ELEMENTS; i += 6) delete(set, i); for (i = 1; i <= MAX_ELEMENTS; i++) { if (in_set(set, i)) { printf(" %4d", i); if (++n % NUMBERS_PER_LINE == 0) { putchar('\n'); n = 0; } } } if (n % NUMBERS_PER_LINE != 0) putchar('\n'); destroy(set); } return 0; } 

Les fonctions devraient vraiment recevoir un préfixe systématique, tel que set_ . La macro BITS_C est basée sur la macro INT64_C (et les autres macros associées) définies dans dans C99 et les versions ultérieures, qui ne fait pas non plus partie de C90.

Comme indiqué dans mes commentaires précédents, voici un exemple de la manière dont vous pouvez regrouper huit éléments 1 bit dans un élément physique char. J’ai seulement implémenté la fonction pour obtenir la valeur d’un élément 1 bit, je laisse la fonction pour la définir (c’est facile à faire).

Remarque: vous pouvez facilement changer le type de l’élément de tableau (unsigned char) et expérimenter des types pouvant contenir plus de bits (par exemple, unsigned int) et vérifier s’ils fonctionnent mieux en termes de vitesse. Vous pouvez également modifier le code pour lui faire gérer des éléments plus gros qu’un bit.

 #include  #include  unsigned int get_el(unsigned char* array, unsigned int index) { unsigned int bits_per_arr_el = sizeof(unsigned char)*CHAR_BIT; unsigned int arr_index = index / bits_per_arr_el; unsigned int bit_offset = index % bits_per_arr_el; unsigned int bitmask = 1 << bit_offset; unsigned int retval; // printf("index=%u\n", index); // printf("bits_per_arr_el=%u\n", bits_per_arr_el); // printf("arr_index=%u\n", arr_index); // printf("bit_offset=%u\n", bit_offset); retval = array[arr_index] & bitmask ? 1 : 0; // can be simpler if only True/False is needed return(retval); } #define MAX_SIZE 10 unsigned char bitarray[MAX_SIZE]; int main() { bitarray[1] = 3; // 00000011 printf("array[7]=%u, array[8]=%u, array[9]=%u, array[10]=%u\n", get_el(bitarray, 7), get_el(bitarray, 8), get_el(bitarray, 9), get_el(bitarray,10)); return 0; } 

les sorties

 array[7]=0, array[8]=1, array[9]=1, array[10]=0 
 typedef struct set { unsigned short var:10; // uint var:1 will be padded to 32 bits } SET; // ushort var:10 (which is max<=1024) padded to 16 bits 

Comme l'a commenté @ Jonathan Leffler, utilisez array (unsigned short []) et définissez les masques de bits

 #define bitZer 0x00 //(unsigned)(0 == 0)? true:true; #define bitOne 0x10 // so from (both inclusive)0-1023 = 1024 ... // added for clarification #define bitTen 0x0A 

regarder dans les bits de chaque élément. http://www.catb.org/esr/structure-packing/ détaillé

Pour stocker une valeur comprise entre 0 et 1023 (ou entre 1 et 1024, qui est essentiellement identique et ne nécessite que l’ajout / la soustraction de 1), vous devez disposer d’un minimum de 10 bits.

Cela signifie que pour les entiers 32 bits (non signés), vous pouvez compresser 3 valeurs sur 30 bits, ce qui donne 2 bits de remplissage inutile.

Exemple:

 %define ELEMENTS 100 uint32_t myArray[ (ELEMENTS + 2) / 3 ]; void setValue(int n, int value) { uint32_t temp; uint32_t mask = (1 << 10) - 1; if(n >= ELEMENTS) return; value--; // Convert "1 to 1024" into "0 to 1023" temp = myArray[n / 3]; mask = mask << (n % 3)*10; temp = (temp & ~mask) | (value << (n % 3)*10); myArray[n / 3] = temp; } int getValue(int n) { uint32_t temp; uint32_t mask = (1 << 10) - 1; if(n >= ELEMENTS) return 0; temp = myArray[n / 3]; temp >>= (n % 3)*10; return (temp & ~mask) + 1; } 

Vous pouvez le faire avec des champs de bits, mais le code pour obtenir / définir des valeurs individuelles finira par utiliser des twigs (par exemple, switch( n%3 ) ), ce qui sera plus lent en pratique.

La suppression de ces deux bits de remplissage coûtera un peu plus de complexité et un peu plus de temps système. Par exemple:

 %define ELEMENTS 100 uint32_t myArray[ (ELEMENTS*10 + 31) / 32 ]; int getValue(int n) { uint64_t temp; uint64_t mask = (1 << 10) - 1; if(n >= ELEMENTS) return 0; temp = myArray[n*10/32 + 1]; temp = (temp << 32) | myArray[n*10/32]; temp >>= (n*10 % 32); return (temp & ~mask) + 1; } 

Cela ne peut pas être fait avec les champs de bits. C’est le moyen le plus économe en espace de stocker un tableau de valeurs allant de 1 à 1024.

Si vous stockez un “tableau de booléens” ou définissez des drapeaux, cela peut être utile. Par exemple, vous pouvez initialiser ou comparer jusqu’à 64 valeurs à la fois.

Ces macros fonctionneront pour les caractères non signés, court, int, long, long … mais simplifient considérablement si vous choisissez un type (vous pouvez donc utiliser une fonction inline statique plus sûre).

 #define getbit(x,n) x[n/(sizeof(*x)*8)] & (typeof(*x))1 << (n&((sizeof(*x)*8)-1)) #define setbit(x,n) x[n/(sizeof(*x)*8)] |= (typeof(*x))1 << (n&((sizeof(*x)*8)-1)) #define flpbit(x,n) x[n/(sizeof(*x)*8)] ^= (typeof(*x))1 << (n&((sizeof(*x)*8)-1)) #define clrbit(x,n) x[n/(sizeof(*x)*8)] &= ~( (typeof(*x))1 << (n&((sizeof(*x)*8)-1)) ) 

pour initialiser un grand nombre de booléens, il suffit de: char cbits[]={0,0xF,0,0xFF};

ou pour tous les zéros char cbits[4]={0};

ou un exemple int: int ibits[]={0xF0F0F0F0,~0};

// 111100001111000011110000111111111111111111111111111111111111111111

Si vous n’accédez qu’à 1 type de tableau, il peut être préférable de transformer les macros en fonctions appropriées telles que:

 static inline unsigned char getbit(unsigned char *x, unsigned n){ return x[n>>3] & 1 << (n&7); } //etc... similar for other types and functions from macros above 

Vous pouvez également comparer plusieurs drapeaux à la fois en '' 'les combinant ensemble et en utilisant les masques' & 'ed; cependant, cela devient un peu plus complexe lorsque vous dépassez les types natifs

Pour votre cas particulier, vous pouvez initialiser à tous les zéros en:

 unsigned char flags[128]={0}; 

ou tous les 1 par:

 uint64_t flags[128] = {~0,~0,~0,~0,~0,~0,~0,~0,~0,~0,~0,~0,~0,~0,~0,~0}; 

Vous pouvez même utiliser des énumérations pour nommer vos drapeaux

 enum{ WHITE, //0 RED, //1 BLUE, //2 GREEN, //3 ... BLACK //1023 } if (getbit(flags,WHITE) && getbit(flags,RED) && getbit(flags,BLUE)) printf("red, white and blue\n"); 

1) La solution appropriée à cette question consiste à utiliser Bit Array.

La question fournissait la solution avec Bit Fields with Struct . Il existe deux méthodes classiques pour économiser de la mémoire pour les problèmes liés aux bits, une autre consiste à utiliser Bit Array . Pour ce cas spécifique dans la question, le meilleur moyen consiste à utiliser Bit Array (présenté comme suit).

  • Si c’est le cas ici comme des drapeaux de bits purement indépendants, optez pour le Bit Array
  • S’il existe un groupe de bits pertinents, tels que l’adresse IP ou la définition du mot de contrôle, il est préférable de les combiner avec une structure, c’est-à-dire d’utiliser des champs de bits avec Sturct.

2) Exemple de code juste pour la démonstration Bit Array

 #include #define BITS_OF_INT (sizeof(int)*CHAR_BIT) void SetBit(int A[], int k) { //Set the bit at the k-th position A[k/BITS_OF_INT] |= 1 <<(k%BITS_OF_INT); } void ClearBit(int A[], int k) { //RESET the bit at the k-th position A[k/BITS_OF_INT] &= ~(1 <<(k%BITS_OF_INT)) ; } int TestBit(int A[], int k) { // Return TRUE if bit set return ((A[k/BITS_OF_INT] & (1 <<(k%BITS_OF_INT)))!= 0) ; } #define MAX_SIZE 1024 int main() { int A[MAX_SIZE/BITS_OF_INT]; int i; int pos = 100; // position for (i = 0; i < MAX_SIZE/BITS_OF_INT; i++) A[i] = 0; SetBit(A, pos); if (TestBit(A, pos)){//do something} ClearBit(A, pos); } 

3) En outre, un sharepoint discussion intéressant de cette question est,

Comment choisir une solution appropriée entre "Bit Array" et "Bit fields with struct" ?

Voici quelques références sur ce sujet.

  • Quand utiliser les champs de bits en C?

  • Champs de bits lisibles et maintenables en C