Iterate through bits in C

Question

I have a big char *str where the first 8 chars (which equals 64 bits if I'm not wrong), represents a bitmap. Is there any way to iterate through these 8 chars and see which bits are 0? I'm having alot of trouble understanding the concept of bits, as you can't "see" them in the code, so I can't think of any way to do this.

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

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

For one char b you can simply iterate like this :

for (int i=0; i<8; i++) {
  printf("This is the %d-th bit : %d\n",i,(b>>i)&1);
}

You can then iterate through the chars as needed.

What you should understand is that you cannot manipulate directly the bits, you can just use some arithmetic properties of number in base 2 to compute numbers that in some way represents some bits you want to know.

How does it work for example ? In a char there is 8 bits. A char can be see as a number written with 8 bits in base 2. If the number in b is b7b6b5b4b3b2b1b0 (each being a digit) then b>>i is b shifted to the right by i positions (in the left 0's are pushed). So, 10110111 >> 2 is 00101101, then the operation &1 isolate the last bit (bitwise and operator).

Answer 6

If you want to iterate through all char.

char *str = "MNO"; // M=01001101, N=01001110, O=01001111
int bit = 0;

for (int x = strlen(str)-1; x > -1; x--){ // Start from O, N, M
    
    printf("Char %c \n", str[x]);
 
    for(int y=0; y<8; y++){ // Iterate though every bit
    // Shift bit the the right with y step and mask last position
        if( str[x]>>y & 0b00000001 ){ 
            printf("bit %d = 1\n", bit);
        }else{
            printf("bit %d = 0\n", bit);
        }
        bit++;
    }
    
}

output

Char O
bit 0 = 1
bit 1 = 1
bit 2 = 1
bit 3 = 1
bit 4 = 0
bit 5 = 0
bit 6 = 1
bit 7 = 0
Char N 
bit 8 = 0
bit 9 = 1
bit 10 = 1
...