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

Question

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 zeri, 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 possibile, prima di lavorare sul problema 3D e su generalizzazioni più complicate.

Questo è fondamentalmente ciò che il codice è simile a 1D, semplificata:

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

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

Speravo che sarei stato 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 fai qualche indicizzazione complicata o c'è un modo più semplice per farlo?

Grazie per le vostre risposte

Answer 1

È possibile utilizzare & (bit a bit e) e < < (spostamento a sinistra).

Ad esempio, (1 < < 3) risulta in "00001000" in binario. Così il vostro codice potrebbe essere simile:

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

Poi basta scalarla con una serie di caratteri e capire il byte opportuno modificare prima.

Per maggiore efficienza, è possibile definire un elenco di campi di bit in anticipo e metterli 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}; 

Allora evitare il sovraccarico del bit spostamento e si può indicizzare le punte, ruotando il precedente codice in:

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

in alternativa, se è possibile utilizzare C++, si potrebbe utilizzare un std::vector<bool> che è definita internamente come un vettore di bit, completi di indicizzazione diretta.

Answer 2

È un compromesso:

(1) utilizzare 1 byte per ciascun valore 2 bit - semplice, veloce, ma utilizza 4x memoria

(2) bit pacchetto in byte - più complessa, alcuni overhead delle prestazioni, utilizza memoria minima

Se si dispone di memoria sufficiente, andare per (1), in caso contrario (2).

Answer 3

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.

È possibile calcolare l'indice di un grande necessaria per:

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

e il numero di bit per

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

È quindi possibile cercare il tempo è necessario e quindi mascherare la punta si bisogno da esso.

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

o

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

Il primo potrebbe essere più veloce su alcune CPU oppure può risparmiare spostando il backup di è necessario per eseguire le operazioni tra la stessa bit in più array bit. Riflette anche l'impostazione e la cancellazione di un bit nel campo più strettamente rispetto alla seconda implementazione. set:

my_field[bindex] |= 1<<b; 

chiaro:

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

Si dovrebbe ricordare che è possibile utilizzare operazioni bit per bit sui anela che tengono i campi e che è la stessa come le 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. In ogni caso, è trovare 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 di avere un'istruzione e il compilatore probabilmente genererà che l'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.

Answer 4

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 \ 
    ) 

Usa:

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 

EDIT la documentazione:

"DWORD" = "parola doppia" = valore a 32 bit (non firmato, 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 DWORD che contiene il bit I e turni DWORD destra, in modo che il bit i diventa il bit meno significativo. Quindi, un 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, facciamo un bit a 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, facciamo un bit a bit e del valore DWORD che contiene il bit e il complemento bit a bit di 1 spostata a sinistra da bit_index_in_dword: che valore non ha tutti i bit impostati a uno, tranne l'unica punta zero la posizione che vogliamo chiarire.
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).

Answer 5

Se non sono in ritardo, la pagina this offre spiegazioni fantastiche con esempi.

Un array di int può essere utilizzato per gestire l'array di bits. Supponendo che le dimensioni di int siano 4 bytes, quando parliamo di un int, abbiamo a che fare con 32 bits. Supponiamo di avere int A[10], significa che lavorando su 10*4*8 = 320 bits e la seguente figura mostra che: (ogni elemento dell'array ha 4 grandi blocchi, ciascuno dei quali rappresentano un byte e ciascuno dei blocchi piccoli rappresentano un bit)

Quindi, per impostare il k esimo bit in ordine di 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] 
    } 

simile per cancellare k esimo bit:

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

e per verificare se il k esimo bit:

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

Come detto sopra, queste manipolazioni può essere scritta come le macro anche:

#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)))