Kann ich eine bestimmte Anzahl von Bits in C zuweisen?

Question

Ich versuche, eine große Menge an boolean Informationen zu speichern, die während der Laufzeit bestimmt wird. Ich frage mich, was die beste Methode sein könnte.

Ich habe gerade versucht, den Speicher zu reservieren mit:

pStatus = malloc((<number of data points>/8) + 1);

denken, dass dies gibt mir genug Bits zu arbeiten. Ich konnte dann jeden Booleschen Wert mit dem Zeiger in Array-Notation Referenz:

pStatus[element]

Leider scheint dies nicht sehr gut zu funktionieren. Erstens, ich habe Schwierigkeiten, den Speicher zu dem ganzzahligen Wert 0 initialisiert. Kann dies mit memset() getan werden? Dennoch glaube ich nicht, dass wirkt sich, warum ich abstürzen, wenn pStatus[element] zuzugreifen versuchen.

Ich bin auch nicht ganz überzeugt, dass dieser Ansatz die beste ist mit sein. Was ich wirklich will, ist im Wesentlichen ein Riesen-Bitmaske, die den Status der Boolesche Werte widerspiegelt. Habe ich etwas verpasst?

Answer 1

pStatus = malloc((<number of data points>/8) + 1);

Dies ist genug Bytes für Ihre Bits zuzuteilen. Allerdings

pStatus[element]

Diese greift auf die element'th Byte , nicht wenig. Also, wenn das Element mehr als ein Achtel der Gesamtzahl von Bits ist, die Sie Zugriff auf off zugewiesen das Ende des Arrays.

Ich würde ein paar Hilfsfunktionen

definieren

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;
}

(Fehler auf Bereich des Elements Überprüfung links aus Gründen der Übersichtlichkeit aus. Sie könnten diese Makros machen, auch)

Answer 2

... denkt, dass dies mir genug Bits geben wird, mit zu arbeiten. Ich konnte dann jeden Booleschen Wert mit dem Zeiger in Array-Notation Referenz:

pStatus[element]

-Element Adressierung Bytes , nicht Bits. Sie wollen so etwas wie:

pStatus[element/8] & (1 << (element % 8))

Answer 3

Kleiner Punkt:. Genügend Speicher bekommen N Bits zu speichern, (N / 8) + 1 Byte ist ungenau (kann man zu viele sein)

(N + 7) / 8 ist immer die Mindestzahl, though.

Answer 4

Nun, die einfachste Antwort wäre calloc zu verwenden anstelle von malloc.

Es wird definiert, um den Speicher weist er auf Null zu initialisieren und kann es oft von Seite Mapping Tricks.

Das wird von den Speichern Initialisierungsproblem kümmern. Die anderen Dutzende Beiträge scheinen hier angemessen die Indizierung Problem und die Tatsache zu richten, dass Sie gelegentlich ein zusätzliches Byte (oh das Grauen!) Zuordnen, so dass ich nicht ihren Inhalt hier wiederholen.

Answer 5

pStatus [element] werden Sie an dieser Adresse ein ganzes Byte geben.

Um ein bestimmtes Element setzen Sie etwas tun würden, wie:

pStatus[element >> 3] |= 1 << (element & 7);

ein Element zurück:

pStatus[element >> 3] &= ~1 << (element & 7);

und ein Element zu testen:

if (pStatus[element >> 3] & (1 << (element & 7)) != 0)

die ursprüngliche Aufteilung sollte

pstatus = malloc((<number of data points> + 7) / 8)

, was man hat funktioniert aber Abfälle ein Byte gelegentlich

Answer 6

kann ich nicht umhin zu bemerken, dass alle Antworten in C hier scheinen anzunehmen, dass ein Byte 8 Bits. Dies ist nicht unbedingt wahr in C (obwohl es natürlich auf den meisten Mainstream-Hardware wahr sein), so macht diese Annahme in Code ist eher schlechte Form.

Der richtige Weg, architekturneutrale Code zu schreiben ist zu

#include <limits.h>

und dann die CHAR_BIT Makro verwenden, wo immer Sie „die Anzahl der Bits in einem char“ benötigen.

Answer 7

Machen Sie sich glücklicher und eine Art und Funktionen definieren, die auf diese Art zu arbeiten. Auf diese Weise, wenn Sie feststellen, dass Bit-Zugriffe sind zu langsam, zu entdecken, können Sie das Gerät Speicher pro boolean auf ein Byte / Wort ändern / lang oder spärliche / dynamische Datenstrukturen annehmen, wenn der Speicher wirklich ein Problem ist (dh, wenn Ihre Sätze sind meist Nullen Sie konnte nur eine Liste mit den Koordinaten der 1en halten.

Sie können Ihren Code schreiben völlig immun gegen Änderungen an der Umsetzung Ihrer Bitvektor zu sein.

Answer 8

pStatus [element] spricht nicht das Bit. Die genaue Byte wird es hängt von der Art der pStatus - Ich gehe davon aus char * oder äquivalent - so pStatus [element] bekommt man das element'th Byte

.

Sie könnten memset auf 0 zu setzen, ja.

Answer 9

 pStatus = malloc((<number of data points>/8) + 1);

, die Teil ist in Ordnung.

 pStatus[element]

ist hier, wo Sie Probleme haben. Sie sind Adressbytes, wenn Sie Bits ansprechen wollen.

 pStatus[element / 8 ]  

finden Sie das richtige Byte in dem Array erhalten.

Answer 10

Sie müssen c = malloc((N+7)/8) Bytes zuweisen, und Sie können die n-te Satz mit

 c[n/8]=((c[n/8] & ~(0x80 >> (n%8))) | (0x80>>(n%8)));

klar mit

 c[n/8] &= ~(0x80 >> (n%8));

und Test mit

 if(c[n/8] & (0x80 >> (n%8))) blah();

Answer 11

Wenn Sie nicht mit nichts dagegen Wrapper zu schreiben, können Sie auch entweder BIT_SET oder bit_vector von C ++ 's STL verwenden könnte, scheint, wie sie (vor allem die letztere) haben genau das, was Sie benötigen, bereits codiert, getestet und verpackt (und viel Schnickschnack).

Es ist wirklich schade, fehlt uns ein straight forward Weg C ++ Code in C-Anwendungen zu verwenden (nein, einen Wrapper zu schaffen mir nicht geradlinig ist, noch Spaß und bedeutet mehr Arbeit auf lange Sicht).

Answer 12

Was mit std::vector<bool> falsch sein würde?

Answer 13

Es erstaunt mich, dass nur eine Antwort hier erwähnt CHAR_BIT. Ein Byte ist oft 8 Bit, aber nicht immer.

Answer 14

Sie Zuordnung Code korrekt ist, die set_bit() und get_bit() Funktionen gegeben in diese Antwort die boolean zuzugreifen.

Answer 15

Wenn Sie nur ein paar Bits beschränkt sind, können Sie statt eaanon01 Lösung auch die c builtin Einrichtung von bitfield verwenden (es gibt nur sehr wenige Gelegenheit, wo Sie sie verwenden können, aber das wäre ein)

Für dieses Bit hämmern Sachen kann ich recommendate: Herny Warrens "Hacker Delight"

Answer 16

Der boolean ist „nie“ ein separater Wert in C. So eine Struktur, um sein könnte um Sie gehen.

Es ist wahr, dass Sie nicht den mem-Bereich zu tun initialisieren, so dass Sie, dass individuell müssen tun.

Hier ist ein einfaches Beispiel dafür, wie Sie es mit den Gewerkschaften structs und Aufzählungen tun könnten

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;
}

Hoffe, das hilft. Dieses Beispiel kann bis 64 Status booleans handhaben und einfach erweitert werden kann.

Dieses exapmle basiert auf Char = 8 Bits int = 16 Bits long int = 32 Bits und long long int = 64 bits

Ich habe jetzt auch Unterstützung für Statusgruppen hinzugefügt.