Bitwise Logic in C

binarybitcoperator-keyword

I have some familiarity with bitwise operations, but this function just went over my head.

void binary_print(unsigned int value) {
  unsigned int mask = 0xff000000;   // Start with a mask for the highest byte.
  unsigned int shift = 256*256*256; // Start with a shift for the highest byte.
  unsigned int byte, byte_iterator, bit_iterator;

  for (byte_iterator=0; byte_iterator < 4; byte_iterator++) {
    byte = (value & mask) / shift; // Isolate each byte.
    printf(" ");

    for (bit_iterator=0; bit_iterator < 8; bit_iterator++) {
      // Print the byte's bits.
      if (byte & 0x80) // If the highest bit in the byte isn't 0,
        printf("1");   // print a 1.
      else
        printf("0");   // Otherwise, print a 0.

      byte *= 2;       // Move all the bits to the left by 1.
    }
    mask /= 256;       // Move the bits in mask right by 8.
    shift /= 256;      // Move the bits in shift right by 8.
  }
}

This function receives bit flags for the open() function and produces the following output with the help of a display_flags function that adds the appropriate labels:

O_RDONLY : 0 : 00000000 00000000 00000000 00000000
O_WRONLY : 1 : 00000000 00000000 00000000 00000001
O_RDWR : 2 : 00000000 00000000 00000000 00000010
O_APPEND : 1024 : 00000000 00000000 00000100 00000000
O_TRUNC : 512 : 00000000 00000000 00000010 00000000
O_CREAT : 64 : 00000000 00000000 00000000 01000000
O_WRONLY|O_APPEND|O_CREAT : 1089 : 00000000 00000000 00000100 01000001

I have no problem understanding the output, but I don't understand the actual process:

  1. How does byte = (value & mask) / shift isolate individual bits?
  2. Why if(byte & 0x80) means "If the highest bit in the byte isn't 0?"
  3. How do these lines: byte *= 2; , mask /= 256; and shift /= 256; move bits and why is this operation significant?

Best Answer

1. How does byte = (value & mask) / shift isolate individual bits?

mask is a bit pattern that always has 8 consecutive bits set to 1, the rest to 0 (it starts with 0xff000000, then 0x00ff0000, and so on. So when you take the bitwise and of mask and value, all bits from value will be set to 0, except those that correspond to the byte that is specified by mask. Those keep their value.

shift is set to the corresponding value that by the division with shift exactly those bits that survived the masking will end up in the rightmost bits (see answer to question 3 how that works).

So assume value is 0xDEADBEEF, mask has its initial value 0xff000000, and shift has its initial value 256*256*256. Then value & mask is 0xDE000000, and the final result is 0x000000DE.

In binary the example would be

value       = 11011110101011011011111011101111
mask        = 11111111000000000000000000000000
byte & mask = 11011110000000000000000000000000
result      = 00000000000000000000000001101111

2. Why if(byte & 0x80) means "If the highest bit in the byte isn't 0?"

Here the code author thinks of byte being an 8-bit variable. Although it is technically larger, the higher bits are never used here. So when the author refers to the "highest bit", think of the 8th bit from the right (the highest bit that would be there if byte was actually only one byte in size).

Now note that 0x80 is 10000000 in binary. So when you take byte & 0x80, all bits from byte will be set to 0, except the "highest" (8th from right) one. So byte & 0x80 is zero, if the highest bit from byte is zero, and greater than zero, if the "highest" bit from byte is 1.

3. How do these lines: byte *= 2;, mask /= 256; and shift /= 256; move bits and why is this operation significant?

Multiplication with 2 is equivalent to a shift of bits to the left by 1. Consider for example the value 9, which is 1001 in binary. A multiplication by 2 gives 18, which is 10010 in binary.

Similar for a division by 2, this is a shift to the right by 1. Division by 256 is equivalent to 8 divisions by 2, so dividing by 256 is equivalent to a right shift by 8 bits. These operations are used here for example to change the value mask from 0xff000000 to 0x00ff0000, 0x0000ff00, and finally to 0x000000ff.

Description of full function

With this knowledge, we can see what the full function does. In the outer loop it loops over the 4 bytes that are in value, starting with the left-most one and ending with the right-most one. It does so by masking out the current byte and stores it in byte.

The inner loop then goes over the 8 bits that are stored in byte. It always looks at 8th bit from the right and prints 1 or 0 accordingly. Then it shifts the bits to the left, so that in the second iteration the bit that was the 7th from right is now the 8th from right and will be printed, and then next one etc. until all 8 bits are printed in right-to-left order.

An alternative way to write this function would be

for (int i = 31; i >= 0; i--) {
  if (value & (1 << i))
    printf("1");
  else
    printf("0");

  if (i % 8 == 0)
    printf(" ");
}

This would simply go through all bits from value in left-to-right order. The expression value (1 << i) selects the desired bit from value, starting with the 32th from right (when i is 31), and ending with the 1st from right (when i is 0).

Related Topic