Wie definiere und arbeite ich mit einem Array von Bits in C?

Ich möchte ein sehr großes Array erstellen, in das ich 0 und 1 schreibe. Ich versuche, einen physikalischen Prozess namens zufällige sequentielle Adsorption zu simulieren, bei dem Einheiten der Länge 2, Dimere, an einem zufälligen Ort auf einem n-dimensionalen Gitter abgelagert werden, ohne sich gegenseitig zu überlappen. Der Prozess stoppt, wenn auf dem Gitter kein Platz mehr für die Ablagerung weiterer Dimere ist (Gitter klemmt).

Anfangs beginne ich mit einem Gitter aus Nullen, und die Dimere werden durch ein Paar „1“ dargestellt. Bei der Ablagerung jedes Dimers wird die Stelle links vom Dimer blockiert, da sich die Dimere nicht überlappen können. Also simuliere ich diesen Vorgang, indem ich ein Tripel von Einsen auf dem Gitter hinterlege. Ich muss die gesamte Simulation viele Male wiederholen und dann die durchschnittliche Abdeckung in % berechnen.

Ich habe dies bereits mit einem Array von Zeichen für 1D- und 2D-Gitter gemacht. Im Moment versuche ich, den Code so effizient wie möglich zu gestalten, bevor ich an dem 3D-Problem und komplizierteren Verallgemeinerungen arbeite.

So sieht der Code vereinfacht in 1D aus:

int main()
{
    /* Define lattice */
    array = (char*)malloc(N * sizeof(char));

    total_c = 0;

    /* Carry out RSA multiple times */
    for (i = 0; i < 1000; i++)
        rand_seq_ads();

    /* Calculate average coverage efficiency at jamming */
    printf("coverage efficiency = %lf", total_c/1000);

    return 0;
}

void rand_seq_ads()
{
    /* Initialise array, initial conditions */
    memset(a, 0, N * sizeof(char));
    available_sites = N;
    count = 0;

    /* While the lattice still has enough room... */
    while(available_sites != 0)
    {
        /* Generate random site location */
        x = rand();

        /* Deposit dimer (if site is available) */
        if(array[x] == 0)
        {
            array[x] = 1;
            array[x+1] = 1;
            count += 1;
            available_sites += -2;
        }

        /* Mark site left of dimer as unavailable (if its empty) */
        if(array[x-1] == 0)
        {
            array[x-1] = 1;
            available_sites += -1;
        }
    }

    /* Calculate coverage %, and add to total */
    c = count/N
    total_c += c;
}

Für das eigentliche Projekt, das ich mache, handelt es sich nicht nur um Dimere, sondern auch um Trimere, Quadrimere und alle möglichen Formen und Größen (für 2D und 3D).

Ich hatte gehofft, dass ich mit einzelnen Bits anstelle von Bytes arbeiten könnte, aber ich habe herumgelesen und soweit ich das beurteilen kann, können Sie jeweils nur 1 Byte ändern, also muss ich entweder eine komplizierte Indizierung durchführen oder gibt es eine einfachere Möglichkeit?

Danke für deine Antworten

Wenn ich nicht zu spät bin, Dies Seite gibt tolle Erklärung mit Beispielen.

Eine Reihe von int kann verwendet werden, um mit einem Array von umzugehen bits. Angenommen Größe von int sein 4 byteswenn wir über ein sprechen intwir beschäftigen uns mit 32 bits. Sagen wir, wir haben int A[10]bedeutet, dass wir daran arbeiten 10*4*8 = 320 bits und die folgende Abbildung zeigt es: (Jedes Element des Arrays hat 4 große Blöcke, von denen jeder a darstellt byte und jeder der kleineren Blöcke repräsentiert a bit)

Also, um das einzustellen ktes Bit im Array A:

// NOTE: if using "uint8_t A[]" instead of "int A[]" then divide by 8, not 32
void  SetBit( int A[],  int k )
{
    int i = k/32;        //gives the corresponding index in the array A
    int pos = k%32;      //gives the corresponding bit position in A[i]

    unsigned int flag = 1;   // flag = 0000.....00001

    flag = flag << pos;      // flag = 0000...010...000   (shifted k positions)

    A[i] = A[i] | flag;      // Set the bit at the k-th position in A[i]
}

oder in der gekürzten Version

void  SetBit( int A[],  int k )
{
    A[k/32] |= 1 << (k%32);  // Set the bit at the k-th position in A[i]
}

ähnlich klar ktes Bit:

void  ClearBit( int A[],  int k )                
{
    A[k/32] &= ~(1 << (k%32));
}

und um zu testen, ob die ktes Bit:

int TestBit( int A[],  int k )
{
    return ( (A[k/32] & (1 << (k%32) )) != 0 ) ;     
}

Wie oben gesagt, können diese Manipulationen auch als Makros geschrieben werden:

// Due order of operation wrap 'k' in parentheses in case it
// is passed as an equation, e.g. i + 1, otherwise the first
// part evaluates to "A[i + (1/32)]" not "A[(i + 1)/32]"
#define SetBit(A,k)     ( A[(k)/32] |= (1 << ((k)%32)) )
#define ClearBit(A,k)   ( A[(k)/32] &= ~(1 << ((k)%32)) )
#define TestBit(A,k)    ( A[(k)/32] & (1 << ((k)%32)) )

typedef unsigned long bfield_t[ size_needed/sizeof(long) ];
// long because that's probably what your cpu is best at
// The size_needed should be evenly divisable by sizeof(long) or
// you could (sizeof(long)-1+size_needed)/sizeof(long) to force it to round up

Nun kann jedes long in einem bfield_t sizeof(long)*8 Bits enthalten.

Sie können den Index eines benötigten Big berechnen, indem Sie:

bindex = index / (8 * sizeof(long) );

und Ihre Bitnummer durch

b = index % (8 * sizeof(long) );

Sie können dann die Länge nachschlagen, die Sie benötigen, und dann das benötigte Bit daraus ausblenden.

result = my_field[bindex] & (1<<b);

oder

result = 1 & (my_field[bindex]>>b); // if you prefer them to be in bit0

Der erste kann auf einigen CPUs schneller sein oder kann Ihnen das Zurückschalten ersparen, wenn Sie Operationen zwischen demselben Bit in mehreren Bit-Arrays ausführen müssen. Es spiegelt auch das Setzen und Löschen eines Bits im Feld genauer wider als die zweite Implementierung. einstellen:

my_field[bindex] |= 1<<b;

klar:

my_field[bindex] &= ~(1<<b);

Sie sollten daran denken, dass Sie bitweise Operationen auf die Longs anwenden können, die die Felder enthalten, und das ist dasselbe wie die Operationen auf den einzelnen Bits.

Sie werden wahrscheinlich auch einen Blick auf die Funktionen ffs, fls, ffc und flc werfen wollen, falls verfügbar. ffs sollte immer verfügbar sein in strings.h. Es ist nur für diesen Zweck da – eine Reihe von Bits. Wie auch immer, es ist der erste Satz und im Wesentlichen:

int ffs(int x) {
    int c = 0;
    while (!(x&1) ) {
        c++;
        x>>=1;
    }
    return c; // except that it handles x = 0 differently
}

Dies ist eine übliche Operation, für die Prozessoren eine Anweisung haben müssen, und Ihr Compiler wird wahrscheinlich diese Anweisung generieren, anstatt eine Funktion wie die von mir geschriebene aufzurufen. x86 hat übrigens eine Anleitung dafür. Oh, und ffsl und ffsll sind die gleichen Funktionen, außer dass sie long bzw. long long sind.

Sie können & (bitweises Und) und << (Linksverschiebung) verwenden.

Beispiel: (1 << 3) ergibt binär "00001000". Ihr Code könnte also so aussehen:

char eightBits = 0;

//Set the 5th and 6th bits from the right to 1
eightBits &= (1 << 4);
eightBits &= (1 << 5);
//eightBits now looks like "00110000". 

Dann skalieren Sie es einfach mit einem Array von Zeichen und ermitteln Sie das entsprechende Byte, das zuerst geändert werden soll.

Für mehr Effizienz könnten Sie im Voraus eine Liste von Bitfeldern definieren und sie in ein Array einfügen:

#define BIT8 0x01
#define BIT7 0x02
#define BIT6 0x04
#define BIT5 0x08
#define BIT4 0x10
#define BIT3 0x20
#define BIT2 0x40
#define BIT1 0x80

char bits[8] = {BIT1, BIT2, BIT3, BIT4, BIT5, BIT6, BIT7, BIT8};

Dann vermeiden Sie den Overhead der Bitverschiebung und können Ihre Bits indizieren, indem Sie den vorherigen Code in Folgendes umwandeln:

eightBits &= (bits[3] & bits[4]);

Wenn Sie C++ verwenden können, können Sie alternativ auch einfach eine verwenden std::vector<bool> die intern als Vektor von Bits definiert ist, komplett mit direkter Indizierung.

bitarray.h:

#include <inttypes.h> // defines uint32_t

//typedef unsigned int bitarray_t; // if you know that int is 32 bits
typedef uint32_t bitarray_t;

#define RESERVE_BITS(n) (((n)+0x1f)>>5)
#define DW_INDEX(x) ((x)>>5)
#define BIT_INDEX(x) ((x)&0x1f)
#define getbit(array,index) (((array)[DW_INDEX(index)]>>BIT_INDEX(index))&1)
#define putbit(array, index, bit) \
    ((bit)&1 ?  ((array)[DW_INDEX(index)] |= 1<<BIT_INDEX(index)) \
             :  ((array)[DW_INDEX(index)] &= ~(1<<BIT_INDEX(index))) \
             , 0 \
    )

Verwenden:

bitarray_t arr[RESERVE_BITS(130)] = {0, 0x12345678,0xabcdef0,0xffff0000,0};
int i = getbit(arr,5);
putbit(arr,6,1);
int x=2;            // the least significant bit is 0
putbit(arr,6,x);    // sets bit 6 to 0 because 2&1 is 0
putbit(arr,6,!!x);  // sets bit 6 to 1 because !!2 is 1

BEARBEITEN die dokumente:

“dword” = “double word” = 32-Bit-Wert (unsigned, aber das ist nicht wirklich wichtig)

RESERVE_BITS: number_of_bits --> number_of_dwords
    RESERVE_BITS(n) is the number of 32-bit integers enough to store n bits
DW_INDEX: bit_index_in_array --> dword_index_in_array
    DW_INDEX(i) is the index of dword where the i-th bit is stored.
    Both bit and dword indexes start from 0.
BIT_INDEX: bit_index_in_array --> bit_index_in_dword
    If i is the number of some bit in the array, BIT_INDEX(i) is the number
    of that bit in the dword where the bit is stored.
    And the dword is known via DW_INDEX().
getbit: bit_array, bit_index_in_array --> bit_value
putbit: bit_array, bit_index_in_array, bit_value --> 0

getbit(array,i) holt das dword, das das Bit i enthält, und Verschiebungen das Doppelwort Rechts, so dass das Bit i zum niederwertigsten Bit wird. Dann ein bitweise und mit 1 werden alle anderen Bits gelöscht.

putbit(array, i, v) überprüft zuerst das niedrigstwertige Bit von v; wenn es 0 ist, müssen wir das Bit löschen, und wenn es 1 ist, müssen wir es setzen.
Um das Bit zu setzen, machen wir a bitweise bzw des Dwords, das das Bit und den Wert 1 enthält nach links verschoben durch bit_index_in_dword: dieses Bit ist gesetzt und andere Bits ändern sich nicht.
Um das Bit zu löschen, machen wir a bitweise und des Dwords, das das Bit und die enthält bitweise Ergänzung von 1 nach links verschoben von bit_index_in_dword: Bei diesem Wert sind alle Bits auf Eins gesetzt, mit Ausnahme des einzigen Null-Bits an der Position, die wir löschen möchten.
Das Makro endet mit , 0 weil es sonst den Wert von dword zurückgeben würde, wo das Bit i gespeichert ist, und dieser Wert ist nicht aussagekräftig. Könnte man auch verwenden ((void)0).

Es ist ein Kompromiss:

(1) Verwenden Sie 1 Byte für jeden 2-Bit-Wert – einfach, schnell, aber verbraucht 4x Speicher

(2) Bits in Bytes packen – komplexer, etwas Leistungsaufwand, verbraucht minimalen Speicher

Wenn Sie genügend Speicher zur Verfügung haben, wählen Sie (1), andernfalls überlegen Sie sich (2).