Come definire e lavorare con una serie di bit in C?

Voglio creare un array molto grande su cui scrivo ‘0 e’ 1. Sto cercando di simulare un processo fisico chiamato adsorbimento sequenziale casuale, in cui unità di lunghezza 2, dimeri, sono depositate su un reticolo n-dimensionale in una posizione casuale, senza sovrapporsi l’un l’altro. Il processo si interrompe quando non vi è più spazio sul reticolo per il deposito di più dimeri (il reticolo è bloccato).

Inizialmente comincio con un reticolo di zero, e i dimeri sono rappresentati da una coppia di “1”. Quando ogni dimero viene depositato, il sito sulla sinistra del dimero viene bloccato, poiché i dimeri non possono sovrapporsi. Quindi simulo questo processo depositando una tripla di “1” sul reticolo. Devo ripetere l’intera simulazione un gran numero di volte e poi calcolare la percentuale di copertura media.

L’ho già fatto utilizzando una serie di caratteri per reticoli 1D e 2D. Al momento sto cercando di rendere il codice il più efficiente ansible, prima di lavorare sul problema 3D e su generalizzazioni più complicate.

Questo è fondamentalmente ciò che il codice appare in 1D, semplificato:

int main() { /* Define latex */ 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; } 

Per il vero progetto che sto facendo, non si tratta solo di dimeri ma trimeri, quadrimeri e di tutti i tipi di forms e dimensioni (per 2D e 3D).

    Speravo di essere in grado di lavorare con singoli bit anziché byte, ma ho letto e fino a quando posso dire che puoi cambiare solo 1 byte alla volta, quindi ho bisogno di fare qualche indicizzazione complicata o c’è un modo più semplice per farlo?

    Grazie per le tue risposte

    Se non sono troppo tardi, questa pagina offre una spiegazione fantastica con esempi.

    Un array di int può essere usato per gestire array di bits . Supponendo che la dimensione di int sia 4 bytes , quando parliamo di un int , abbiamo a che fare con 32 bits . Diciamo che abbiamo int A[10] , significa che stiamo lavorando su 10*4*8 = 320 bits e la seguente figura lo mostra: (ogni elemento dell’array ha 4 grandi blocchi, ognuno dei quali rappresenta un byte e ciascuno dei blocchi più piccoli rappresentano un bit )

    inserisci la descrizione dell'immagine qui

    Quindi, per impostare il k th bit nell’array A :

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

    o nella versione abbreviata

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

    allo stesso modo per cancellare il primo bit:

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

    e per testare se il primo bit:

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

    Come detto sopra, queste manipolazioni possono essere scritte anche come macro:

     #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 

    Ora, ogni long in un bfield_t può contenere sizeof (long) * 8 bit.

    Puoi calcolare l’indice di un grande necessario:

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

    e il tuo numero di bit entro

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

    È quindi ansible cercare il lungo che è necessario e quindi mascherare il bit necessario da esso.

     result = my_field[bindex] & (1< 

    o

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

    Il primo potrebbe essere più veloce su alcuni cpu o potrebbe farti risparmiare lo spostamento indietro di cui hai bisogno per eseguire operazioni tra lo stesso bit in più matrici di bit. Inoltre rispecchia l'impostazione e la cancellazione di un bit sul campo più strettamente rispetto alla seconda implementazione. impostato:

     my_field[bindex] |= 1< 

    chiaro:

     my_field[bindex] &= ~(1< 

    È necessario ricordare che è ansible utilizzare operazioni bit a bit sui long che contengono i campi e che è uguale alle operazioni sui singoli bit.

    Probabilmente vorrete anche esaminare le funzioni ffs, fls, ffc e flc se disponibili. ffs dovrebbe sempre essere disponibile in strings.h . È lì solo per questo scopo: una serie di bit. Ad ogni modo, si trova il primo set ed essenzialmente:

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

    Questa è un'operazione comune per i processori per avere un'istruzione e il compilatore probabilmente genererà quell'istruzione piuttosto che chiamare una funzione come quella che ho scritto. A proposito, x86 ha un'istruzione per questo. Oh, e ffsl e ffsll sono la stessa funzione, tranne prendere lunghe e lunghe lunghe, rispettivamente.

    Puoi usare & (bitwise e) e << (shift a sinistra).

    Ad esempio, (1 << 3) risulta in "00001000" in binario. Quindi il tuo codice potrebbe essere simile a:

     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". 

    Quindi ridimensionalo con una serie di caratteri e calcola prima il byte appropriato da modificare.

    Per maggiore efficienza, è ansible definire un elenco di bitfield in anticipo e inserirli in un array:

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

    Quindi eviti il ​​sovraccarico del bit shifting e puoi indicizzare i tuoi bit, trasformando il codice precedente in:

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

    In alternativa, se puoi usare C ++, puoi semplicemente usare un file std::vector che è definito internamente come un vettore di bit, completo di indicizzazione diretta.

    bitarray.h :

     #include  // 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< 

    Uso:

     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 

    MODIFICA i documenti:

    "dword" = "double word" = valore a 32 bit (senza segno, ma non è molto importante)

     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) recupera la dword contenente il bit i e sposta la parola dword a destra , in modo che il bit i diventi il ​​bit meno significativo. Quindi, un bit a bit e con 1 cancella tutti gli altri bit.

    putbit(array, i, v) prima di tutto controlla il bit meno significativo di v; se è 0, dobbiamo cancellare il bit, e se è 1, dobbiamo impostarlo.
    Per impostare il bit, eseguiamo un bit per bit o della dword che contiene il bit e il valore di 1 spostato a sinistra da bit_index_in_dword: quel bit è impostato e gli altri bit non cambiano.
    Per cancellare il bit, eseguiamo un bit per bit e il dword che contiene il bit e il complemento bit per bit di 1 spostato a sinistra da bit_index_in_dword: quel valore ha tutti i bit impostati su uno tranne l'unico bit zero nella posizione che vogliamo cancellare.
    La macro termina con , 0 perché altrimenti restituirebbe il valore di dword dove il bit i è archiviato e quel valore non è significativo. Si potrebbe anche usare ((void)0) .

    È un compromesso:

    (1) usa 1 byte per ciascun valore a 2 bit – semplice, veloce, ma usa una memoria 4x

    (2) impacchettare i bit in byte – più complessi, alcune prestazioni generali, utilizza memoria minima

    Se hai abbastanza memoria disponibile, vai su (1), altrimenti prendi in considerazione (2).