¿Cómo definir y trabajar con una matriz de bits en C?

Question

Quiero crear una matriz muy grande en la que escribo '0' y '1'. Estoy tratando de simular un proceso físico llamado adsorción aleatoria secuencial, donde las unidades de longitud 2, dímeros, se depositan en una red n-dimensional en una ubicación aleatoria, sin superposición entre sí. El proceso se detiene cuando ya no queda más espacio en el enrejado para depositar más dímeros (el enrejado está atascado).

Inicialmente empiezo con un enrejado de ceros, y los dímeros están representados por un par de '1's. A medida que se deposita cada dímero, el sitio a la izquierda del dímero se bloquea, debido al hecho de que los dímeros no se pueden superponer. Así que simulo este proceso depositando un triple de '1 en el enrejado. Necesito repetir toda la simulación una gran cantidad de veces y luego calcular el% de cobertura promedio.

Ya he hecho esto usando una matriz de caracteres para redes 1D y 2D. Por el momento estoy tratando de hacer que el código sea lo más eficiente posible, antes de trabajar en el problema 3D y generalizaciones más complicadas.

Esto es básicamente lo que el código se ve como en 1D, simplificado:

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

Para el proyecto actual que estoy haciendo, se trata no sólo de los dímeros de trímeros, pero quadrimers, y todo tipo de formas y tamaños (para 2D y 3D).

Tenía la esperanza de poder trabajar con bits individuales en lugar de bytes, pero he estado leyendo y, por lo que puedo ver, solo se puede cambiar 1 byte a la vez, así que o bien necesito ¿Haces alguna indexación complicada o hay una manera más simple de hacerlo?

Gracias por sus respuestas

Answer 1

Puede utilizar & (bit a bit y) y < < (desplazamiento a la izquierda).

Por ejemplo, (1 < < 3) resultados en "00001000" en binario. Así que el código podría ser:

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

A continuación, sólo ampliarlo con una serie de caracteres y averiguar el byte apropiado modificar en primer lugar.

Para mayor eficiencia, se puede definir una lista de campos de bits de antemano y ponerlos en una matriz:

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

A continuación, evitar la sobrecarga del desplazamiento de bits y que puede indexar sus pedazos, convirtiendo la anterior código en:

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

Alternativamente, si se puede usar C++, es posible que utilices una std::vector<bool> que se define internamente como un vector de bits, completo con la indexación directa.

Answer 2

Es una disyuntiva:

(1) utilizar 1 byte para cada valor de 2 bits - sencillo, rápido, pero utiliza 4x memoria

(2) bits de paquete en bytes - más compleja, algunos sobrecarga de rendimiento, usa memoria mínima

Si tiene suficiente memoria disponible, vaya por (1), de lo contrario considere (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 

Ahora, cada longitud en un bfield_t puede contener sizeof (long) * 8 bits.

Se puede calcular el índice de un grande que necesita:

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

y el número de bits por

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

A continuación, puede buscar el tiempo que necesita y luego enmascarar el bit se necesita de eso.

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

o

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

El primero puede ser más rápido en algunas CPUs o puede ahorrar cambiando una copia de seguridad de lo que necesita para llevar a cabo operaciones entre el mismo bit en varias matrices de bits. También refleja la configuración y el borrado de un bit en el campo más de cerca que la segunda implementación. conjunto:

my_field[bindex] |= 1<<b; 

claro:

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

Usted debe recordar que se puede utilizar en las operaciones bit a bit largos que sostienen los campos y eso es lo mismo que las operaciones en los bits individuales.

Probablemente también quiera examinar las funciones ffs, fls, ffc y flc si están disponibles. ffs siempre debe estar disponible en strings.h. Está ahí solo para este propósito: una cadena de bits. todos modos, es Buscar conjunto primero y esencialmente:

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

Esta es una operación común para los procesadores tengan una instrucción para su compilador y probablemente generarán que la instrucción en lugar de llamar a una función como la que yo escribí. x86 tiene una instrucción para esto, por cierto. Ah, y ffsl y ffsll son la misma función, excepto tomar long y long long, respectivamente.

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

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 

EDITAR los docs:

"DWORD" = "doble palabra" = valor de 32 bits (sin firmar, pero eso no es realmente 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) Obtiene el valor DWORD que contiene el bit I y turnos DWORD derecha, por lo que el bit i se convierte en el bit menos significativo. Entonces, un en bits y con 1 borra todos los demás bits.

putbit(array, i, v) primero comprueba el bit menos significativo de v; si es 0, tenemos que borrar el bit, y si es 1, tenemos que configurarlo.
para establecer el bit, hacemos un bit a bit o del DWORD que contiene el bit y el valor de 1 desplazado a la izquierda por bit_index_in_dword: se establece que los bits, y otros bits no cambian.
Para borrar el bit, hacemos un bit a bit y del DWORD que contiene el bit y el complemento bit a bit de 1 desplazado a la izquierda por bit_index_in_dword: ese valor tiene todos los bits puestos a uno, excepto el único bit cero en la posición que queremos borrar
La macro finaliza con , 0 porque de lo contrario devolvería el valor de dword donde está almacenado el bit i, y ese valor no es significativo. También se podría usar ((void)0).

Answer 5

Si no soy demasiado tarde, la página this ofrece una explicación increíble con ejemplos.

Una matriz de int se puede utilizar para tratar con matriz de bits. Suponiendo que el tamaño de int es 4 bytes, cuando hablamos de int, nos ocupamos de 32 bits. Digamos que tenemos int A[10], significa que estamos trabajando en 10*4*8 = 320 bits y siguiente figura muestra que: (cada elemento de matriz tiene 4 bloques grandes, cada uno de los cuales representan una byte y cada uno de los bloques más pequeños representan un bit)

por lo tanto, para establecer el k ésimo bit en serie 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 en la versión acortada

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

de manera similar a despejar k ésimo bit:

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

y para probar si el k ésimo bit:

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

Como se ha dicho anteriormente, estas manipulaciones se puede escribir como macros también:

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