Bit Manipulation: Bitwise Operations
C can perform six different bitwise operations: OR, AND, XOR, NOT, left shift, and right shift. As the names seem to imply, these operations are very similar to their logical counterparts, but there are crucial differences. If an operation is bitwise, then it applies to each individual bit in the bitstring. If an operation is logical, then it applies to the bitstring as a whole.
The bitwise OR operator is represented as | in C. As we know, an OR gate outputs 1 if and only if at least one of its inputs is 1. From the properties of Boolean algebra, we know that 1 OR X = 1, and 0 OR X = X. Since this is the case, we can say that ORing any bit with 1 sets it to 1, whereas ORing any bit with 0 does not change the bit. As such, you may see the OR operation referred to as a set operation. To demonstrate, if we had the bitstrings 11000010 and 01101011, and bitwise OR’d them, the result would be 11000010 | 01101011 = 11101011. Notice that Bits 0, 3, and 5 of the first bitstring went from 0 to 1, since the respective bits in the second bitstring were also 1. Going back to the eight LEDs example, we had the bitstring 00101101, and we wanted to turn LED #1 on. In order to do that, we could bitwise OR that bitstring with 00000010, resulting in 00101101 | 00000010 = 00101111. Notice that the only Bit 1 was changed from the original bitstring; everything else remained unchanged.
The bitwise AND operator is represented as & in C. As previously known, an AND gate outputs 1 if and only if both of its inputs are 1. The properties of Boolean algebra also state that 0 AND X = 0 and 1 AND X = X. This presents opposite behavior as the OR operation. ANDing any bit with 0 clears it to 0, whereas ANDing any bit with 1 leaves it unaffected. Thus, the AND operation can also be called a clear or reset operation. To put it into focus, let’s take the same example as before, but with a bitwise AND instead. So, 11000010 & 01101011 = 01000010. Notice that Bit 7 of the first bitstring went from 1 to 0, since Bit 7 of the second bitstring was also 0. Following up from the eight LEDs example, we turned on LED #1, but now we want to turn off LED #3. Given that our bitstring is 00101111, we could bitwise AND that with 11110111, resulting in 00101111 | 11110111 = 00100111. Notice that only Bit 3 was changed from the original bitstring; everything else remained unchanged.
The bitwise XOR operator is represented as ^ in C. From prior knowledge, we know that a two-input XOR gate outputs 1 if and only if one of its inputs is 1, but not both. Given this nature, we can derive that 1 XOR X = NOT X and 0 XOR X = X. We now have more curious behavior than the previous operations. XORing any bit with 1 returns the complement of that bit, and XORing any bit with 0 leaves the bit unchanged. In other words, the XOR operation is a toggle operation. With the same example as with the previous operations, applying a bitwise XOR operation to 11000010 and 01101011 leads to 11000010 ^ 01101011 = 10101001. Notice that Bits 0, 1, 3, 5, and 6 of the original bitstring have the opposite values now, since the respective bits of the second bitstring were 1. Returning to the eight LEDs example, suppose we wanted to arbitrarily toggle the state of LED #4. Now, from our bitstring 00100111, we know that LED #4 is off, so toggling its state would be the same as setting Bit 4 to 1. The usefulness in the toggle operation comes in the case where we either don’t know or don’t care about the current state of LED #4, we just want the opposite of it. So, in order to accomplish the task of toggling LED #4, we could bitwise XOR that bitstring with 00010000. Thus, 00100111 ^ 00010000 = 00110111. Notice that only Bit 4 was changed from the original bitstring; everything else remained unchanged.
The bitwise NOT operation is represented as ~ in C. Simply put, a NOT gate outputs the complement of its input. So applying a NOT operation to a bit simply flips it. Thus, a bitwise NOT operation just flips each bit in a bitstring. Unlike the previous operations, the NOT operation only needs one operand (as opposed to two). For example, taking 11000010 and applying a bitwise NOT operation returns ~11000010 = 00111101. Notice that every bit in the original bitstring is now the opposite of its original value. You may notice a similarity with the bitwise XOR operation in that the NOT operation toggles each bit. Indeed, bitwise NOT is the same as bitwise XOR with a bitstring of all 1’s (e.g., ~11000010 is the same as 11000010 ^ 11111111). The important difference is that bitwise XOR is useful for toggling specific bits, whereas bitwise NOT is useful for toggling every bit. So, for the eight LEDs example, given 00110111, if you want to toggle the state of every LED, you could apply a bitwise NOT to that bitstring, resulting in ~00110111 = 11001000. So, LEDs #0, #1, #2, #4, and #5 are all turned off, while LEDs #3, #6, and #7 are all on.
Finally, the shift operations are represented in C as << and >> for left shift and right shift, respectively. As a note, these shifts are logical shifts, thus a shifted bit is replaced with a 0 (as opposed to arithmetic shifts, where right shifts copies the signed bit). Even though the operation itself only requires one operand, in C, the operations take two operands: the bitstring to be shifted, and how many times it should be shifted. For example, 11111111 << 1 = 11111110. This is a left shift performed on 11111111 only once. As opposed to 1111111 << 3 = 11111000, which is a left shift on the same number done three times. This is the same for the right shift operation, where 11111111 >> 1 = 01111111 and 11111111 >> 4 = 00001111. These shift operations aren’t as applicable to the eight LEDs example; however, they are very useful for creating bitmasks.