People learning C are sometimes confused about the bitwise operators
|. These operators treat integers as bit vectors and compute logical operations on corresponding bits.
& computes the AND operation, which yields 1 if both operands are 1, and 0 otherwise. Here is an example of
& applied to two 4-bit numbers:
1100 & 1010 ---- 1000
In C, this means that the expression
12 & 10 has the value 8.
| computes the OR operation, which yields 1 if either operand is 1, and 0 otherwise.
1100 | 1010 ---- 1110
So the expression
12 | 10 has the value 14.
^ computes the XOR operation, which yields 1 if either operand is 1, but not both.
1100 ^ 1010 ---- 0110
So the expression
12 ^ 10 has the value 6.
& is used to clear a set of bits from a bit vector,
| is used to set bits, and
^ is used to flip, or “toggle” bits. Here are the details:
Clearing bits: For any value \( x \), \( x\ \& \ 0 \) is 0, and \( x\ \& \ 1 \) is \( x \). So if you AND a vector with 3, it selects only the two rightmost bits, and sets the rest to 0.
xxxx & 0011 ---- 00xx
In this context, the value 3 is called a “mask” because it selects some bits and masks the rest.
Setting bits: Similarly, for any \( x \), \( x\ | \ 0 \) is \( x \), and \( x\ | \ 1 \) is 1. So if you OR a vector with 3, it sets the rightmost bits, and leaves the rest alone:
xxxx | 0011 ---- xx11
Toggling bits: Finally, if you XOR a vector with 3, it flips the rightmost bits and leaves the rest alone. As an exercise, see if you can compute the two’s complement of 12 using
^. Hint: what’s the two’s complement representation of -1?
C also provides shift operators,
>>, which shift bits left and right. Each left shift doubles a number, so
5 << 1 is 10, and
5 << 2 is 20. Each right shift divides by two (rounding down), so
5 >> 1 is 2 and
2 >> 1 is 1.