Ich habe die Bitset Klasse in Java verwendet und ich würde gerne etwas ähnliches in C machen. Ich nehme an, dass ich es manuell machen müsste wie die meisten Sachen in C. Was wäre eine effiziente Art zu implementieren?Wie implementiert man ein Bitset in C?
byte bitset[]
vielleicht
bool bitset[]
?
CCAN hat eine bitset Implementierung Sie verwenden können: http://ccan.ozlabs.org/info/jbitset.html
Aber wenn Sie es selbst Umsetzung am Ende tun (zum Beispiel, wenn Sie auf dieses Paket die Abhängigkeiten nicht mögen), sollten Sie ein Array von ints verwenden und verwenden sie die native Größe der Computerarchitektur:
#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));
}
sie nicht eine bestimmte Größe (zB mit uint64 oder uint32), lassen sie den Computer verwenden, was es will, dass die Verwendung von sizeof zu bedienen und anzupassen.
Vielleicht, aber vielleicht möchten Sie auch die größte Größe, auf der Sie effizient arbeiten können. Wenn Sie durch Bits scannen, kann dies effizient sein. Die Art und Weise, wie einige CPUs Caches aus dem Speicher laden, spielt keine Rolle, welche Größe Sie wählen. Aber auf der dritten Seite ... vielleicht musst du nur experimentieren und messen. –
Sicher experimentieren, aber nach meiner Erfahrung ist die Verwendung der Wortgröße zum Aufteilen in der Regel am schnellsten. Ich bin mir nicht sicher, ob ich deinen ersten Punkt verstehe? –
'sizeof' ist in Bytes, nicht in Bits. Sie müssen mit 8 multiplizieren (oder allgemeiner 'CHAR_BIT' in einigen dieser Ausdrücke. –
Nun, Byte-Bitset [] scheint ein wenig irreführend, nein?
Verwenden Bit-Felder in einer Struktur und dann können Sie eine Sammlung dieser Art halten (oder sie anderweitig verwenden, wie Sie sehen, passen)
struct packed_struct {
unsigned int b1:1;
unsigned int b2:1;
unsigned int b3:1;
unsigned int b4:1;
/* etc. */
} packed;
Dies ist keine schlechte Idee für eine kleine Sammlung von Flags, aber wenn Sie ein Bitset verwenden, möchten Sie normalerweise, dass es durch eine ganze Zahl indexierbar ist. Siehe zum Beispiel die Java-Bitset-Klasse. –
Ja, darüber habe ich später nachgedacht und dann gemerkt, dass Mike etwas in diese Richtung gepostet hat. –
Gegenproduktive Verwendung von Bitfeldern und Verwendung von Indizes in Variablennamen. –
Machen Sie es ein Array von unsigned int 64
Wie immer müssen Sie zuerst entscheiden, welche Art von Operationen Sie auf Ihrem Bitset ausführen müssen. Vielleicht eine Teilmenge von dem, was Java definiert? Danach können Sie entscheiden, wie Sie es am besten implementieren. Sie können sicherlich die Quelle für BitSet.java in OpenJDK nach Ideen suchen.
Niemand erwähnt, was die C FAQ empfiehlt, die eine Reihe von guten alten Makros ist:
#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)
Aber das schützt nicht immer vor Makro-Nebenwirkungen zum Beispiel: 'int i = 0, Bits; BITSET (Bits, i ++) ' –
@LukeSmith Sie haben einen Punkt, aber es sieht ziemlich weit verbreitet aus. Es scheint, dass die richtige Art, ein Makro zu implementieren, darin besteht, dem Anrufer zu verdeutlichen, dass es sich um ein Makro handelt, wodurch der Anrufer in die Pflicht genommen wird. (Wer das nicht mag, kann es in eine Inline-Funktion verpacken) – Opux
Sie können meine PackedArray Code einen Versuch mit einem bitsPerItem von geben 1.
Es implementiert einen Container mit wahlfreiem Zugriff, in dem Elemente auf der Bit-Ebene gepackt werden. Mit anderen Worten, es verhält sich so, als ob Sie in der Lage wären, z.B. uint9_t oder uint17_t Array:
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
Ich empfehle meine BITSCAN C++ library (Version 1.0 wurde soeben veröffentlicht). BITSCAN ist speziell auf schnelle Bit-Scan-Operationen ausgerichtet. Ich habe es verwendet, um NP-Hard-kombinatorische Probleme zu implementieren, die einfache ungerichtete Graphen wie maximale Clique beinhalten (siehe BBMC Algorithmus für einen führenden exakten Solver).
Ein Vergleich zwischen BITSCAN und Standardlösungen STL bitset und dynamic_bitset BOOST finden Sie hier: http://blog.biicode.com/bitscan-efficiency-at-glance/
Effiziente in Bezug auf Speicher oder CPU? – robert
@robert: Ich nehme an, dass in Bezug auf Speicher in erster Linie. Es ist wegen des geringen möglichen Verarbeitungsaufwands, aber ernster Overheads im Falle von Cache-Misses. – ruslik
@robert: Es gibt einen Unterschied? Wenn es eine große Anzahl von Bits gibt, wird die Leistung durch Cache-Fehltreffer gebunden, so dass das bestmögliche Packen der Bits die beste Leistung ergibt. Nur wenn es sehr wenige Bits gibt, könnte es effizienter sein, ein ganzes Byte (oder mehr) pro Bit zu verwenden. –