Comment mettre en œuvre un bitset en C?

J'ai été en utilisant le Bitset classe en Java et je voudrais faire quelque chose de similaire en C. je suppose que je dois le faire manuellement comme la plupart des choses dans C. Ce serait une manière efficace de mettre en œuvre?

byte bitset[]

peut-être

bool bitset[]

Efficace en termes de mémoire ou le PROCESSEUR?
Je suppose qu'en termes de mémoire, en premier lieu. C'est parce que de peu d'possible la charge de traitement, mais grave, les frais généraux en cas de défauts de cache.
il y a une différence? Si il y a un grand nombre de bits, les performances seront liés par les défauts de cache, de sorte que l'emballage les bits d'aussi près que possible de donner de meilleures performances. Seulement si il y a très peu de bits peut-il être plus efficace d'utiliser un ensemble d'octets (ou plus) par bit.

OriginalL'auteur David Robles | 2010-12-07

bitset c

13

Le rclc a un bitset mise en œuvre, vous pouvez utiliser: http://ccan.ozlabs.org/info/jbitset.html

Mais si vous finissez par la mise en œuvre elle-même (par exemple si vous n'aimez pas les dépendances sur le paquet), vous devez utiliser un tableau d'entiers et d'utiliser la taille d'origine de l'ordinateur de l'architecture:
```
#define WORD_BITS (8 * sizeof(unsigned int))

unsigned int * bitarray = (int *)calloc(size / 8 + 1, sizeof(unsigned int));

static inline void setIndex(unsigned int * bitarray, size_t idx) {
    bitarray[idx / WORD_BITS] |= (1 << (idx % WORD_BITS));
}
```
Ne pas utiliser une taille spécifique (par exemple, avec uint64 ou uint32), laissez l'utilisation de l'ordinateur ce qu'il souhaite utiliser et adapter pour que l'utilisation de sizeof.

Peut-être, mais aussi peut-être que vous voulez que la très grande taille, vous pouvez utiliser efficacement. Si vous êtes à la numérisation par le biais bits, c'est peut-être efficace. Là encore, la façon dont certains Processeurs charge des caches de mémoire il n'a pas d'importance ce que la taille que vous choisissez. Mais sur la troisième main ... peut-être vous avez juste à expérimenter et à mesure.
Certainement l'expérience, mais dans mon expérience, à l'aide de la taille de mot de split est généralement plus rapide. Je ne suis pas sûr de comprendre votre premier point?
sizeof est exprimée en octets, pas de bits. Vous devez multiplier par 8 (ou plus généralement CHAR_BIT dans certains de ces expressions.
doh, merci! 🙂
FYI ccan.ozlabs.org/info/jbitset.html n'existe plus

OriginalL'auteur Mike Axiak
10

Personne n'a mentionné que le C FAQ recommande, qui est un tas de bon-vieux-macros:
```
#include <limits.h>     /* for CHAR_BIT */

#define BITMASK(b) (1 << ((b) % CHAR_BIT))
#define BITSLOT(b) ((b) / CHAR_BIT)
#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
#define BITCLEAR(a, b) ((a)[BITSLOT(b)] &= ~BITMASK(b))
#define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))
#define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT)
```
(via http://c-faq.com/misc/bitsets.html)

Mais ce n'est pas toujours garde de macro effets secondaires essayez par exemple: int i = 0, bits; BITSET(bits, i++)
Vous avez un point, mais il semble assez largement utilisé. Il semble que la bonne façon de mettre en œuvre une macro est de l'appelant comprendre que c'est une macro, mettant ainsi le fardeau de la preuve de l'appelant. (Quelqu'un qui n'aime pas cela, pouvez l'envelopper dans un en ligne)

OriginalL'auteur
3

Bien, byte bitset[] semble un peu trompeur, non?

Utiliser des champs de bits dans une struct et puis vous pouvez maintenir une collection de ces types (ou les utiliser autrement comme bon vous semble)
```
struct packed_struct {
  unsigned int b1:1;
  unsigned int b2:1;
  unsigned int b3:1;
  unsigned int b4:1;
  /* etc. */
} packed;
```
Ce n'est pas une mauvaise idée pour une petite collection de drapeaux, mais si vous utilisez un bitset en général, vous voulez qu'il soit indexable par un nombre entier. Voir, par exemple, la Java de la classe bitset.
Ouais, j'ai pensé que plus tard, et alors remarqué que Mike posté quelque chose le long de ces lignes.
Contre-productif utilisation de bitfields et l'utilisation des index dans les noms de variable.

OriginalL'auteur Ed S.
2

Je recommande mon BITSCAN de la bibliothèque C++ (version 1.0 vient de sortir). BITSCAN est spécifiquement orienté pour rapide bitscan opérations. Je l'ai utilisé pour mettre en œuvre un problème NP-Difficile combinatoire des problèmes impliquant simple non orienté graphiques, tels que la clique maximale (voir BBMC algorithme, avec une pointe de solveur exact).

Une comparaison entre BITSCAN et des solutions standard STL bitset et de STIMULER dynamic_bitset est disponible ici:
http://blog.biicode.com/bitscan-efficiency-at-glance/

OriginalL'auteur chesslover

Vous pouvez donner à mon PackedArray code essayer avec un bitsPerItem de 1.

Il met en œuvre un accès aléatoire conteneur, où les articles sont emballés au niveau des bits. En d'autres termes, il agit comme si vous étiez en mesure de manipuler un par exemple uint9_t ou uint17_t tableau:

PackedArray principle:
  . compact storage of <= 32 bits items
  . items are tightly packed into a buffer of uint32_t integers

PackedArray requirements:
  . you must know in advance how many bits are needed to hold a single item
  . you must know in advance how many items you want to store
  . when packing, behavior is undefined if items have more than bitsPerItem bits

PackedArray general in memory representation:
  |-------------------------------------------------- - - -
  |       b0       |       b1       |       b2       |
  |-------------------------------------------------- - - -
  | i0 | i1 | i2 | i3 | i4 | i5 | i6 | i7 | i8 | i9 |
  |-------------------------------------------------- - - -

  . items are tightly packed together
  . several items end up inside the same buffer cell, e.g. i0, i1, i2
  . some items span two buffer cells, e.g. i3, i6

OriginalL'auteur Gregory Pakosz

0

Comme d'habitude, vous devez d'abord décider quel type d'opérations que vous devez effectuer sur votre bitset. Peut-être qu'un sous-ensemble de ce que Java définit? Après cela, vous pouvez décider de la meilleure façon à la mettre en œuvre. Vous pouvez certainement chercher à la source pour l'BitSet.java dans OpenJDK pour des idées.

OriginalL'auteur James K Polk
-2

Faire un tableau de unsigned int 64.

OriginalL'auteur EvilTeach

Vous devez vous connecter pour publier un commentaire.