There are three major bitwise operators that can be used to combine two numbers: AND, OR, and XOR. When I say that an operator is bitwise, it means that the operation is actually applied separately to each bit of the two values being combined. For example, if x = y AND z, that means that bit 0 of x is actually bit 0 of y ANDed with bit 0 of z. Make sense? Let’s look at each operator in turn and see how they work. Once we’ve been through all of that, we’ll be in a position to come up with some practical applications of each.
The AND Operator
There are two kinds of AND operators in the C language: the logical AND, and the bitwise AND. The former is represented by the && operator, and the latter uses the & operator. You’ve probably seen the first on e numerous times, as it’s often used in if statements. Here’s an example of the logical AND in action:
if ((x == 5) && (y == 7)) DoSomething();
in this case, you would expect that the function will only be called if x is 5 and y is 7. The bitwise AND works very much the same way, except that it works with two bits instead of two expressions. The bitwise AND operation returns 1 if and only if both of its operands are equal to 1. In other words, we have the following truth table for the bitwise AND:
The first column shows the result of a bitwise AND when combining explicitly defined bits. But it’s the second column that’s interesting. It says that if you AND any bit with 0, the result is 0; and if you AND any bit with 1, the result is the original bit. This little piece of information will be the key to making the bitwise AND work for us later, so keep it in mind. To finish up, let’s see an example of combining two words using the bitwise AND operator:
0110 1011 1000 0101
& 0001 1111 1011 1001
0000 1011 1000 0001
Do you see why we get the result we do? There is a 1 in the result only in the positions where the corresponding bits in both operands are also equal to 1. That’s all there is to the bitwise AND operation. Let’s move on.
The OR Operator
Just as with the AND operation, there are two different types of OR in the C language. The logical OR uses the || operator, and the bitwise OR uses the | operator. A use of the logical OR might look something like this:
if ((x == 5) || (y == 7)) DoSomething();
In this example, the function will be called if x is 5, if y is 7, or both.The only way the function is not called is if both of the conditions are false. The bitwise OR is very similar, in that it returns 0 if and only if both of its operands are 0. To illustrate this, we have the following truth table:
Once again, the second column is the interesting one.
Note that whenever you OR a bit with 0, the result is the original bit, and whenever you OR a bit with 1, the result will always be 1. This will be the key to using OR effectively a little later on. For now, let’s just look at an example of using the bitwise OR operation on two words:
0110 1011 1000 0101
| 0001 1111 1011 1001
0111 1111 1011 1101
Here you can see that the result contains a 0 only when the corresponding bits in both of the operands are also 0. Now we’ve got just one more combinational operator to look at, and that’s XOR.
The XOR Operator
The XOR is a little strange because there is no logical equivalent for it in C, even though many languages include one. The XOR operation is symbolized by the ^ character in C. The term XOR stands for “exclusive OR,” and means “one or the other, but not both.” In other words, XOR returns 1 if and only if exactly one of its operands is 1. If both operands are 0, or both are 1, then XOR returns 0. To see this, take a look at the truth table for XOR:
The truth table here is interesting. Note from the first column that anything XORed with itself returns 0. This fact will lead to an interesting application of XOR later on. In the second column, we see that any bit XORed with 0 yields the original bit, and any bit XORed with 1 yields the complement of the original bit. This is something you may not have seen before: the bitwise NOT. It is a unary operator, meaning that it only takes one operand, like a negative sign. A bitwise NOT simply inverts all the bits in its operand, meaning that all 0s are changed to 1s, and vice versa. Now, let’s take a look at an example of using XOR on two words:
0110 1011 1000 0101
^ 0001 1111 1011 1001
0111 0100 0011 1100
So there you have it, the last of the combinational operators, plus the only unary bitwise operator, the NOT. Before we can look at any applications of these, there is one other class of bitwise operator I need to show you, called shifts. Don’t worry, this will go pretty quickly, and then we can get on to the interesting stuff.
There are two bitwise shift operators, namely shift left and shift right. In C, they are represented by the << and >> operators, respectively. These operations are very simple, and do exactly what they say: shift bits to the left or to the right. The syntax for a shift operation is as follows:
[integer] [operator] [number of places];
A statement of this form shifts the bits in [integer] by the number of places indicated, in the direction specified by the operator. Probably the best way to visualize this is with an example. Take a look at the following code, which demonstrates a shift left.
// Precondition: x == 0000 0110 1001 0011 // Postcondition: y == 0000 1101 0010 0110 x = x << 1;
From this example, you should be able to see what’s going on. Every bit in x is shifted to the left by one place. When you do this, the MSB (most significant bit, remember?) of x is lost, because there isn’t another place to shift it to. Similarly, after a shift left, the LSB of x will always be 0. There is no position to the right of the LSB, and so there’s nothing to shift into the LSB, so it’s assigned a value of 0. Just to make sure you’ve got the idea of this, let’s take a look at a shift right:
// Precondition: x == 0110 1111 1001 0001 // Postcondition: y == 0000 0110 1111 1001 x = x >> 4;
Here, the bits are being shifted right by four places. Got it? Good. That finishes out the set of bitwise operators, so now we can finally get around to seeing what they’re good for.