Bitwise Logic in C

Question

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 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 the bit flags for the open() function and produces the following output using the display_flags function, which 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:

• How byte = (value & mask) / shift isolate individual bits?
• Why if(byte & 0x80) means "If the most significant bit in a byte is not 0?"
• Like these lines: byte *= 2; , mask /= 256; and shift /= 256; move bits and why is this operation significant?

Answer 1

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

mask is a pattern bit that always has 8 consecutive bits set to 1, the rest is 0 (starts with 0xff000000 , then 0x00ff0000 , etc. Therefore, when you accept the bitwise and mask and value , all bits from value will be set to 0, except those that match the byte specified by mask . They retain their value.

shift set to the corresponding value, which by dividing with shift exactly those bits that survived in the disguise fall into the rightmost bits (see the answer to question 3, how it works).

Suppose value is 0xDEADBEEF , mask has an initial value of 0xff000000 , and shift has an initial value of 256*256*256 . Then value & mask is 0xDE000000 , and the final result is 0x000000DE .

In binary format, the example will be

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

2. Why if(byte & 0x80) means "If the most significant bit in a byte is not 0?"

Here, the author of the code believes that byte is an 8-bit variable. Although this is technically larger, higher bits are never used here. Therefore, when the author refers to the “high bit”, think about the 8th bit on the right (the most significant bit that would be there if the byte was actually only one byte in size).

Now notice that 0x80 is 10000000 in binary format. Therefore, when you take byte & 0x80 , all bits from byte will be set to 0, except for the "highest" (8th on the right). Thus, byte & 0x80 is zero if the most significant bit from byte is zero and greater than zero, if the “highest” bit of byte is 1.

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

Multiplying from 2 is equivalent to shifting the bits to the left by 1. Consider, for example, the value 9, which is 1001 in binary format. Multiplying by 2 gives 18, which is 10010 in binary format.

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

Full Feature Description

With this knowledge, we can see what the full function does. In the outer loop, it bypasses four bytes that are in value , starting with the leftmost and ending with the rightmost. It does this by masking the current byte and storing it in a byte .

The inner loop then goes through 8 bits, which are stored in the byte . It always looks at the eighth bit on the right and prints 1 or 0, respectively. Then it shifts the bits to the left, so that in the second iteration, the bit that was the seventh on the right is now the eighth on the right and will be printed, and then the next, etc., Until all 8 bits are printed on the right - the 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(" "); } 

It will just traverse all the bits from value in order from left to right. The expression value (1 << i) selects the desired bit from value , starting from the 32nd on the right (when i is 31) and ending with the 1st on the right (when i is 0).

Answer 2

The most important thing to remember is that bitwise logic bitwise based on operations on bits . Thus, for all purposes and tasks, bitwise & (and) is a multiplication modulo 1 and bitwise | (or) | (or) is a modulo 1 addition. The easiest way to see this is with an example:

If you have some byte 0xF0 , and you want to know if the most significant bit is set, you will and it with 0x80 . Here's what happens:

  11110000 = 0xF0 x 10000000 = 0x80 ========== 10000000 = 0x80 

Thus, if the most significant bit in 0xF0 not actually set, the result will be 0 and instead of 0x80 . You can do this with any bit position or sequence of bit positions by creating a binary number. For example, 0x88 = 10001000 will check the most significant bit in the byte, as well as for the 4th bit.

The important thing with binary is to notice that each position is a multiplication by two. So, 00000001 = 1 , but then 00000010 = 2 and 00000100 = 4 , etc. Thus, multiplying by 2 similar to a left shift ( << ) by one. Dividing by 256 is the right shift ( >> ) by 8. This is most easily seen by thinking of the strengths of the two. 2^8 = 256 . Thus, since each bit is one of these 2 , dividing 256 equivalent to shifting to the right by 8 (exponent / number of the two necessary).

Answer 3

1) value and mask force all bytes to null, except what interests you. dividing this by a shift, moves it to byte 0 (personally, I would use the operator →).

2), and 0x80 deletes all bits except the highest. 0x80 - 10,000,000 in binary, 1 bit corresponds to the highest bit in a byte. the results will be either 0 or 10,000,000 (in hexadecimal format 0x80). IF will be right only if the upper bit has been set.

3) byte * = 2 - left shift by 1 bit. I would use byte <<= 1. Seems more obvious.

mask / = 256 - shift to the right by 8 bits. I would use a mask → = 8. ditto

divide and multiple can use shift operators if you use permissions 2. It seems more obvious to me to use shift operators.

order matters to get the values ​​in the correct order.

Answer 4

You can shift any binary value by multiplying or dividing by powers of 2 by how binary math works.

Answer 5

Well, it seems your difficulty is to see how bitwise operations are related to arithmetic.

• Firstly, multiplying by 2 is the same as shifting the binary 1st step to the left.
• secondly, if you do this several times, you move a few steps to the left.
• Excessively, if you divide by 2, you will move one step to the right.

The best notation for all these operations will use the "real" shift operators:

 (value & mask) / (256*256*256) 

better to write how

 (value & mask) >> (3*8) 

Does it help?

I liked the idea of ​​splitting the number into two parts using "DIV" and "MOD" - where N DIV 256 is an integer division that discards the remainder - so it effectively shifts the right by 8 bits, discarding the low byte, AND Conversely, N MOD 256 , which simply takes the remainder. This is AND efficient at 255, and leaves only the low byte. From the result of DIV and MOD you can restore the original number:

 LO = X & 255; // equivalent to (byte)X if X is unsigned HI = X >> 8 ; // equivalent to (X / 256) in this case original = LO | (HI << 8) // equivalent to LO + (HI * 256), in this case 

Answer 6

mask disables all bits included, except those that are in the first byte, for example

  0110 0000 0000 0000 0000 0000 0000 0110 0000 & 1111 1111 0000 0000 0000 0000 0000 0000 0000 = 0110 0000 0000 0000 0000 0000 0000 0000 0000 

because 1 & 0 or 0 & 1 or 0 & 0 == 0 and 1 & 1 == 0

Division by 2 shifts of all bits to the right, multiplication by 2 shifts them all to the left.

0x80 == 1000 0000 So, & with this value disables everything except the first bit.

If the first bit is set, the resulting value is> 0 and therefore corresponds to a logical true value, if it is non-zero and false.