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

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 32void  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)) )

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

Now, each long in a bfield_t can hold sizeof(long)*8 bits.

You can calculate the index of a needed big by:

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

and your bit number by

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

You can then look up the long you need and then mask out the bit you need from it.

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

or

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

The first one may be faster on some cpus or may save you shifting back up of you needto perform operations between the same bit in multiple bit arrays. It also mirrorsthe setting and clearing of a bit in the field more closely than the second implemention.set:

my_field[bindex] |= 1<<b;

clear:

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

You should remember that you can use bitwise operations on the longs that hold the fieldsand that's the same as the operations on the individual bits.

You'll probably also want to look into the ffs, fls, ffc, and flc functions if available. ffs should always be avaiable in strings.h. It's there just for this purpose -- a string of bits.Anyway, it is find first set and essentially:

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

This is a common operation for processors to have an instruction for and your compiler will probably generate that instruction rather than calling a function like the one I wrote. x86 has an instruction for this, by the way. Oh, and ffsl and ffsll are the same function except take long and long long, respectively.

You can use & (bitwise and) and << (left shift).

For example, (1 << 3) results in "00001000" in binary. So your code could look like:

char eightBits = 0;//Set the 5th and 6th bits from the right to 1eightBits &= (1 << 4);eightBits &= (1 << 5);//eightBits now looks like "00110000". 

Then just scale it up with an array of chars and figure out the appropriate byte to modify first.

For more efficiency, you could define a list of bitfields in advance and put them in an array:

#define BIT8 0x01#define BIT7 0x02#define BIT6 0x04#define BIT5 0x08#define BIT4 0x10#define BIT3 0x20#define BIT2 0x40#define BIT1 0x80char bits[8] = {BIT1, BIT2, BIT3, BIT4, BIT5, BIT6, BIT7, BIT8};

Then you avoid the overhead of the bit shifting and you can index your bits, turning the previous code into:

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

Alternatively, if you can use C++, you could just use an std::vector<bool> which is internally defined as a vector of bits, complete with direct indexing.