rotacion - matrices en lenguaje c
¿Cómo definir y trabajar con una matriz de bits en C? (5)
Quiero crear una matriz muy grande en la que escribo ''0''s'' y ''1''s''. 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 parece el código 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 real que estoy haciendo, involucra no solo dímeros sino trímeros, cuadrimers 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 debo hacer una indexación complicada. o hay una manera más simple de hacerlo?
Gracias por tus respuestas
Es una compensación:
(1) utilice 1 byte para cada valor de 2 bits: simple, rápido, pero usa memoria 4x
(2) pack bits en bytes - más complejo, algunos gastos generales de rendimiento, utiliza la memoria mínima
Si tiene suficiente memoria disponible, vaya por (1), de lo contrario considere (2).
Puede usar & (bitwise and) y << (left shift).
Por ejemplo, (1 << 3) da como resultado "00001000" en binario. Entonces su código podría verse así:
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, amplíelo con una serie de caracteres y determine el byte apropiado para modificar primero.
Para mayor eficiencia, puede definir una lista de campos de bits por adelantado 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};
Luego, evita la sobrecarga del cambio de bit y puede indexar sus bits, convirtiendo el código anterior en:
eightBits &= (bits[3] & bits[4]);
Alternativamente, si puede usar C ++, puede usar un std::vector<bool> que se define internamente como un vector de bits, completo con indexación directa.
Si no soy demasiado tarde, this página ofrece una explicación increíble con ejemplos.
Una matriz de int se puede usar para tratar con una matriz de bits . Suponiendo que el tamaño de int sea de 4 bytes , cuando hablamos de un int , estamos tratando con 32 bits . Digamos que tenemos int A[10] , significa que estamos trabajando en 10*4*8 = 320 bits y la siguiente figura lo muestra: (cada elemento de la matriz tiene 4 bloques grandes, cada uno representa un byte y cada uno de los bloques más pequeños) representar un bit )
Por lo tanto, para establecer el k ésimo bit en el conjunto 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 abreviada
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 limpiar k th 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 dijo anteriormente, estas manipulaciones también pueden escribirse como macros:
#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)) )
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 /
)
Utilizar:
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 documentos:
"dword" = "palabra doble" = valor de 32 bits (sin signo, 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) recupera el dword que contiene el bit i y desplaza el dword a la derecha , de modo que el bit i se convierte en el bit menos significativo. Entonces, un bitwise y con 1 borra todos los demás bits.
putbit(array, i, v) comprueba en primer lugar 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 bitwise o del dword que contiene el bit y el valor de 1 desplazado a la izquierda por bit_index_in_dword: ese bit está establecido, y otros bits no cambian.
Para borrar el bit, hacemos un bitwise 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 configurados en uno excepto el único bit cero en la posición que queremos borrar.
La macro termina 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) .
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 bfield_t puede contener sizeof (long) * 8 bits.
Puede calcular el índice de una gran necesidad de:
bindex = index / (8 * sizeof(long) );
y su número de bit por
b = index % (8 * sizeof(long) );
Luego puede buscar todo lo que necesita y luego enmascarar la broca que necesita.
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 ahorrarte una copia de seguridad de la necesidad de realizar operaciones entre el mismo bit en matrices de múltiples 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);
Debe recordar que puede usar operaciones bit a bit en los largos que contienen los campos y que 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. De todos modos, es encontrar el primer conjunto 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 que los procesadores tengan una instrucción y su compilador probablemente generará esa instrucción en lugar de llamar a una función como la que 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.