How to define and work with an array of bits in C?

Question

I want to create a very large array on which I write '0's and '1's. I'm trying to simulate a physical process called random sequential adsorption, where units of length 2, dimers, are deposited onto an n-dimensional lattice at a random location, without overlapping each other. The process stops when there is no more room left on the lattice for depositing more dimers (lattice is jammed).

Initially I start with a lattice of zeroes, and the dimers are represented by a pair of '1's. As each dimer is deposited, the site on the left of the dimer is blocked, due to the fact that the dimers cannot overlap. So I simulate this process by depositing a triple of '1's on the lattice. I need to repeat the entire simulation a large number of times and then work out the average coverage %.

I've already done this using an array of chars for 1D and 2D lattices. At the moment I'm trying to make the code as efficient as possible, before working on the 3D problem and more complicated generalisations.

This is basically what the code looks like in 1D, simplified:

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

For the actual project I'm doing, it involves not just dimers but trimers, quadrimers, and all sorts of shapes and sizes (for 2D and 3D).

I was hoping that I would be able to work with individual bits instead of bytes, but I've been reading around and as far as I can tell you can only change 1 byte at a time, so either I need to do some complicated indexing or there is a simpler way to do it?

Thanks for your answers

Answer 1

If I am not too late, this page gives awesome explanation with examples.

An array of int can be used to deal with array of bits. Assuming size of int to be 4 bytes, when we talk about an int, we are dealing with 32 bits. Say we have int A[10], means we are working on 10*4*8 = 320 bits and following figure shows it: (each element of array has 4 big blocks, each of which represent a byte and each of the smaller blocks represent a bit)

So, to set the kth bit in 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]
}

or in the shortened version

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

similarly to clear kth bit:

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

and to test if the kth bit:

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

As said above, these manipulations can be written as macros too:

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