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.

Prizefight

Suggest showing sample "first 8 chars". What do you mean by "first 8 chars" and then "these 4 chars"? – Pyrophotometer

4 was just a typo. When I say the first 8 chars I mean str[1,2,...,8] – Prizefight

Surely you mean 0...7 instead of 1...8 ? Because array indizes in C begin at 0. – Cite

possible duplicate of How do you set, clear and toggle a single bit in C/C++? – Pearlstein

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.

Papp

Would be good to emphasize that my_char must be unsigned for this code to work correctly for all values (and not run forever for some values). – Onida

yes, you are correct. but since he said his context was a bitmap image, to be clear and concise i omitted all of those considerations. too much info might confuse a newcomer. – Papp

Thank you for the answer. Why have you used my_char & 0x01? – Prizefight

this is the important part, its a bitmask. read en.wikipedia.org/wiki/Mask_(computing) they put it well there – Papp

This is a destructive solution, if OP wants to read the bits of a bitmap, this is unsuitable. – Epithalamium

@Jean-BaptisteYunès Why is that unsuitable? my_char can just be a temp var... my_char = my_bitmap[1234]; – Papp

Answer 2

Here is a way to iterate over each of the set bits of an unsigned integer, one bit at a time.

Use unsigned rather than signed integers for well-defined behaviour; unsigned of any width should be fine.

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.

Decennial

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.

Pearlstein

s/8-bit wide/at least 8-bit wide – Necking

In the C language, chars are CHAR_BIT wide bytes. CHAR_BIT is at least 8. – Pyrophotometer

@chux The only modern systems which have super-octet bytes are highly specialized embedded systems. There are no modern super-octet general computing architectures, so from a practical point of view a char is always 8-bits. – Pearlstein

@Tyler Durden 1 ) This question digs into present day situation concerning the rare CHAR_BIT != 8. 2) As C does not require new systems to use CHAR_BIT == 8, future systems may use super-octet char. – Pyrophotometer

@Tyler Durden 3) Much like 2014 systems overwhelmingly use of 2's complement for int and so int overflow should be well defined. Since the C spec leaves int overflow as undefined to accommodate those old pesky obsolete sign-magnitude, 1’s complement, padded integers, smarter compilers have taken advantage of that and create code that breaks former code that relied on well-defined 2's complement overflow. Why did coders count on well-defined 2's complement overflow – because “all” modern systems use 2’s complement. – Pyrophotometer

@Tyler Durden 3b) In a likewise fashion, a savvy compiler may take advantage that CHAR_BIT may be greater than 8 for some future optimization. Suggest using (u)int8_t if code needs an 8-bit integer. – Pyrophotometer

Answer 4

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

Dannadannel

OK, now that you've got it fixed, I suggest including <limits.h> and changing 8 to CHAR_BIT. – Onida

By the way, if you have some char b equal the binary value of 10110111, and you do b >> 2, what you get is 11101101, not 00101101. This is because char is signed char by default, and when performing right-shift on a signed variable, the sign-bit follows to the right. For b >> 2 to yield 00101101, you must declare unsigned char b. – Onida

I didn't want to be such pedantic. He needed only basic advices about bit manipulation. – Epithalamium

Don't be cheap on pedanticism here, especially if it's only a few of more lines of information. OP (and other users reading this answer in the future) will just end up running into a different problem instead. – Onida

To be pedantic: char is unsigned on some platforms. – Sherbrooke

Answer 5

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

Gapin

And also for big-endian, so why mention it? Endianness has only to do with the ordering of bytes inside larger units (shorts, integers, and larger). Bit order, quite fortunately, is the same for big, middle, and little-endian systems. – Errant

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

Hf