Bit-Feld gegen Bitset

Question

Ich möchte Bits in einem Array (ähnlich einer Struktur) speichern. Daher kann ich entweder einen der folgenden beiden Ansätze verfolgen

Ansatz Nummer 1 (AN 1)

struct BIT
{
   int data : 1
};

int main()
{
   BIT a[100];
   return 0;
}

Ansatz Nummer 2 (AN 2)

int main()
{
    std::bitset<100> BITS;
    return 0;
}

Warum würde jemand AN 2 AN 1 vorziehen?

Answer 1

Weil Ansatz Nr. 2 tatsächlich 100 Bits Speicher verwendet, zuzüglich einiger sehr geringfügiger (konstanter) Overheads, während Nr. 1 typischerweise vier Bytes Speicher pro Bit-Struktur verwendet. Im Allgemeinen ist eine struct gemäß dem C++-Standard mindestens ein Byte groß.

#include 
#include 

struct Bit { int data : 1; };

int main()
{
    Bit a[100];
    std::bitset<100> b;
    std::cout << sizeof(a) << "\n";
    std::cout << sizeof(b) << "\n";
}

druckt aus

400
16

Abgesehen davon verpackt bitset Ihr Bit-Array in einen schönen Objektrepräsentation mit vielen nützlichen Operationen.

Answer 2

Eine gute Wahl hängt davon ab, wie Sie die Bits verwenden werden.

std::bitset ist von fester Größe. Visual C++ 10.0 entspricht nicht den Standards in Bezug auf Konstruktoren; im Allgemeinen müssen Sie eine Lösung bereitstellen. Ironischerweise war dies darauf zurückzuführen, was Microsoft für eine Fehlerbehebung hielt - sie führten einen Konstruktor ein, der ein int Argument akzeptiert, soweit ich mich erinnere.

std::vector ist ähnlich wie std::bitset optimiert. Kosten: Die Indizierung liefert nicht direkt eine Referenz (es gibt keine Verweise auf einzelne Bits in C++), sondern gibt stattdessen ein Proxy-Objekt zurück - was Ihnen erst auffällt, wenn Sie versuchen, es als Referenz zu verwenden. Vorteil: minimaler Speicherbedarf, und der Vektor kann bei Bedarf neu dimensioniert werden.

Einfach z.B. unsigned zu verwenden ist auch eine Option, wenn Sie mit einer kleinen Anzahl von Bits arbeiten (in der Praxis 32 oder weniger, obwohl die formale Garantie nur 16 Bits beträgt).

Zu guter Letzt sind ALLE GROSSBUCHSTABEN Bezeichner üblicherweise (außer bei Microsoft) für Makros reserviert, um die Wahrscheinlichkeit von Namenskollisionen zu reduzieren. Es ist daher eine gute Idee, ALLE GROSSBUCHSTABEN Bezeichner nicht für anderes als Makros zu verwenden. Und für Makros sollten immer ALLE GROSSBUCHSTABEN Bezeichner verwendet werden (das erleichtert auch die Erkennung).

Prost & Gruß,

Answer 3

Bitset hat mehr Operationen

Answer 4

Ansatz Nummer 1 wird höchstwahrscheinlich als ein Array von 4-Byte-Integer compiliert und ein Bit jedes wird verwendet, um Ihre Daten zu speichern. Theoretisch könnte ein intelligenter Compiler dies optimieren, aber darauf würde ich mich nicht verlassen.

Gibt es einen Grund, warum Sie std::bitset nicht verwenden möchten?

Answer 5

Um cplusplus.com's Seite zu bitset zu zitieren, "Die Klasse ähnelt sehr einem regulären Array, optimiert jedoch für Speicherplatzallokation". Wenn Ihre ints 4 Bytes sind, verwendet ein bitset 32-mal weniger Speicherplatz.

Sogar die Verwendung von bool bits[100], wie von sbi vorgeschlagen, ist immer noch schlechter als ein bitset, weil die meisten Implementierungen bools mit >= 1 Byte haben.

Falls Sie aus reinem intellektuellem Interesse Ihr eigenes bitset implementieren wollten, könnten Sie dies mit Bitmasken tun:

typedef struct {
  unsigned char bytes[100];
} MyBitset;

bool getBit(MyBitset *bitset, int index)
{
  int whichByte = index / 8; 
  return bitset->bytes[whichByte] && (1 << (index = % 8));
}

bool setBit(MyBitset *bitset, int index, bool newVal)
{
  int whichByte = index / 8;

  if (newVal)
  {
    bitset->bytes[whichByte] |= (1 << (index = % 8));
  }
  else
  {
    bitset->bytes[whichByte] &= ~(1 << (index = % 8));
  }
}

(Entschuldigung, dass ich eine Struktur anstelle einer Klasse verwendet habe. Ich denke gerade in reinem C, weil ich mitten in einer Low-Level-Aufgabe für die Schule bin. Offensichtlich sind zwei große Vorteile der Verwendung einer Klasse das Operatorüberladen und die Möglichkeit, ein variabel großes Array zu haben.)