Iterate through bits in C

In the C language, chars are 8-bit wide bytes, and in general in computer science, data is organized around bytes as the fundamental unit.

In some cases, such as your problem, data is stored as boolean values in individual bits, so we need a way to determine whether a particular bit in a particular byte is on or off. There is already an SO solution for this explaining how to do bit manipulations in C.

To check a bit, the usual method is to AND it with the bit you want to check:

int isBitSet = bitmap & (1 << bit_position);

If the variable isBitSet is 0 after this operation, then the bit is not set. Any other value indicates that the bit is on.

Here is a way to iterate over each of the set bits of an unsigned integer (use unsigned rather than signed integers for well-defined behaviour; unsigned of any width should be fine), one bit at a time.

Define the following macros:

#define LSBIT(X)                    ((X) & (-(X)))
#define CLEARLSBIT(X)               ((X) & ((X) - 1))

Then you can use the following idiom to iterate over the set bits, LSbit first:

unsigned temp_bits;
unsigned one_bit;

temp_bits = some_value;
for ( ; temp_bits; temp_bits = CLEARLSBIT(temp_bits) ) {
    one_bit = LSBIT(temp_bits);
    /* Do something with one_bit */
}

I'm not sure whether this suits your needs. You said you want to check for 0 bits, rather than 1 bits — maybe you could bitwise-invert the initial value. Also for multi-byte values, you could put it in another for loop to process one byte/word at a time.

It's true for little-endian memory architecture:

const int cBitmapSize = 8;
const int cBitsCount = cBitmapSize * 8;
const unsigned char cBitmap[cBitmapSize] = /* some data */;

for(int n = 0; n < cBitsCount; n++)
{
  unsigned char Mask = 1 << (n % 8);
  if(cBitmap[n / 8] & Mask)
  {
    // if n'th bit is 1...
  }
}

Imagine you have only one byte, a single char my_char. You can test for individual bits using bitwise operators and bit shifts.

unsigned char my_char = 0xAA;
int what_bit_i_am_testing = 0;

while (what_bit_i_am_testing < 8) {
  if (my_char & 0x01) {
     printf("bit %d is 1\n", what_bit_i_am_testing);
  }
  else {
     printf("bit %d is 0\n", what_bit_i_am_testing);
  }

  what_bit_i_am_testing++;
  my_char = my_char >> 1;
}

The part that must be new to you, is the >> operator. This operator will "insert a zero on the left and push every bit to the right, and the rightmost will be thrown away".

That was not a very technical description for a right bit shift of 1.