Previous Table of Contents Next


3.3.5. Bitwise Operators

The bitwise operators operate conceptually on the individual bits of binary numbers. They are perhaps the lowest level of C’s operators, closest to the machine instructions that might otherwise be accessed only through assembly language. However, these operators find plenty of uses in higher-level algorithms and are used in a number of common idioms as well.

The &, |, and ^ operators perform boolean operations across the individual bits of two operands. The & operator performs bitwise AND, the | performs bitwise OR, and the ^ operator performs bitwise exclusive-OR (XOR). The truth tables for these operators can be summarized as follows:

  0x0011       0x0011       0x0011
& 0x0101     | 0x0101     ^ 0x0101
--------     --------     --------
  0x0001       0x0111       0x0110

A bit in the result of a bitwise AND operator is 1 if the corresponding bits in the first and second operands are both 1 (otherwise, the resulting bit is 0). A bit in the result of a bitwise OR operator is 1 if the corresponding bits in either the first or second operands (or both) are 1. A bit in the result of a bitwise XOR operator is 1 if one of the corresponding bits in either the first or second operands (but not both) is 1. (The preceding three examples use carefully chosen hexadecimal constants that suggest base-2 numbers, though they are not. As a fourth example, 0x7d & 0x5e yields 0x5a.)

The unary ~ operator takes the one’s complement of its operand, changing all 0 bits to 1 and 1 bits to 0. On a machine with 16-bit ints, ~0x0101 is 0xfefe.

The left- and right-shift operators << and >> shift their left operands left or right by a number of bits given by their right operands. The expression 0x0101 >> 4 yields 0x0010, and the expression 0x1234 << 1 yields 0x2468. Bits that are shifted away are discarded. The left-shift operator << always fills with 0 bits at the right. The right-shift operator >> fills with 0 bits at the left if the left operand has an unsigned type. If the left operand is signed, it is implementation defined whether the right-shift operator shifts in 0 bits or copies of the sign bit. The results are undefined if the right operand is negative or is greater than or equal to the size of the left operand in bits.

The bitwise operators are commonly used to encode a set of 1-bit flags within an integer. The expression flags = flags | 0x10 sets the fifth bit from the right in flags to 1 (whether it was 1 or not). The expression flags = flags & ~0x10 clears the fifth bit to 0. (The expression ~0x10 is preferable in this application to 0xffef or 0xffffffef because it is independent of the size of an int.) The expression flags & 0x10 tests the fifth bit, yielding a zero value if the fifth bit is 0 and a nonzero value if it is 1, and can therefore be used directly in conditionals, as in if(flags & 0x10) …. It is also possible to construct bit masks “on the fly” by using the shift operators: the mask 0x10 could be computed from its (0-based) bit number using 0x01 << 4.

The bitwise operators can also be used to extract subfields from integer values. For example, the expression val & 0x0ff0 extracts the middle 8 bits from a (presumably) 16-bit value. By using the properties of binary numbers, these masks, too, can be computed on-the-fly. The expression (1 << 6) - 1 yields the mask 0x3f, which could be used to extract the low-order 6 bits of an integer. The expression ((1 << 8) - 1) << 4 yields the mask 0x0ff0.

The exclusive-OR operator ^ has an “information preserving” property (roughly speaking, it changes as many 0’s to 1’s as it changes 1’s to 0’s), which makes it useful in several situations. Returning to the bit flags example, the expression flags = flags ^ 0x10 toggles the fifth bit from 0 to 1 or from 1 to 0. If val is a data value and key is an encryption key, the expression xval = val ^ key yields a scrambled value xval with the property that the original value can be recovered simply by computing xval ^ key. (This rudimentary example has almost no security, but it forms the basis of many useful encryption algorithms, especially those that are self inverse.) If val1, val2, and val3 are three values that are to be transmitted via an unreliable communications channel, the expression val4x = val1 ^ val2 ^ val3 computes a fourth value, which, if it is transmitted along with the first three, can be used to recover any of them. For example, if it is discovered that val2 was damaged in transit, the expression val1 ^ val3 ^ val4x recovers val2.

The precedence of the bitwise operators is not always obvious; in particular, the precedence of &, ^, and | is quite low (below +, ==, <<, and so on). A condition of the form if(val & 0xf == 5) does not behave as intended, if the intent was the condition that is correctly written as if((val & 0xf) == 5). See the table in section 3.3.9 for complete information on the precedence of these operators.


Previous Table of Contents Next