Skip to main content
\(\newcommand{\doubler}[1]{2#1} \newcommand{\binary}{\mathtt} \newcommand{\hex}{\mathtt} \newcommand{\octal}{\mathtt} \newcommand{\prog}{\mathtt} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section4.3C/C++ Bit Operations

The C/C++ bitwise logical operators are:

and &
inclusive or |
exclusive or ^
complement ~

It is easy to see what each of these operators does by using truth tables. To illustrate how truth tables work, consider the algorithm for binary addition. In Section 3.1 we saw that the \(i^{th}\) bit in the result is the sum of the \(i^{th}\) bit of one number plus the \(i^{th}\) bit of the other number plus the carry produced from adding the \((i - 1)^{th}\) bits. This sum will produce a carry of zero or one. In other words, a bit adder has three inputs—the two corresponding bits from the two numbers being added and the carry from the previous bit addition, and two outputs—the result and the carry.

In a truth table we have a column for each input and each output. We write down all possible input bit combinations and then show the output(s) in the corresponding row. A truth table for the bit-by-bit addition of z = x + y is shown in Table 4.3.1. We use the notation x[i] to represent the \(i^{th}\) bit in the variable x.

inputs outputs
x[i] y[i] carry[(i-1)] z[i] carry[i]
\(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\)
\(\binary{0}\) \(\binary{1}\) \(\binary{0}\) \(\binary{1}\) \(\binary{0}\)
\(\binary{1}\) \(\binary{0}\) \(\binary{0}\) \(\binary{1}\) \(\binary{0}\)
\(\binary{1}\) \(\binary{1}\) \(\binary{0}\) \(\binary{0}\) \(\binary{1}\)
\(\binary{0}\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\) \(\binary{0}\)
\(\binary{0}\) \(\binary{1}\) \(\binary{1}\) \(\binary{0}\) \(\binary{1}\)
\(\binary{1}\) \(\binary{0}\) \(\binary{1}\) \(\binary{0}\) \(\binary{1}\)
\(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\)
Table4.3.1Truth table for the bit-by-bit z = x + y operation. x[i] is the \(i^{th}\) bit of x; carry[i-1] is the carry from adding the \((i - 1)^{th}\) bits.

The bitwise logical operators act on the corresponding bits of two operands as shown in Table 4.3.2Table 4.3.5.

x[i] y[i] x[i] & y[i]
\(\binary{0}\) \(\binary{0}\) \(\binary{0}\)
\(\binary{0}\) \(\binary{1}\) \(\binary{0}\)
\(\binary{1}\) \(\binary{0}\) \(\binary{0}\)
\(\binary{1}\) \(\binary{1}\) \(\binary{1}\)
x[i] y[i] x[i] | y[i]
\(\binary{0}\) \(\binary{0}\) \(\binary{0}\)
\(\binary{0}\) \(\binary{1}\) \(\binary{1}\)
\(\binary{1}\) \(\binary{0}\) \(\binary{1}\)
\(\binary{1}\) \(\binary{1}\) \(\binary{1}\)
Table4.3.3inclusive or
x[i] y[i] x[i] ^ y[i]
\(\binary{0}\) \(\binary{0}\) \(\binary{0}\)
\(\binary{0}\) \(\binary{1}\) \(\binary{1}\)
\(\binary{1}\) \(\binary{0}\) \(\binary{1}\)
\(\binary{1}\) \(\binary{1}\) \(\binary{0}\)
x[i] ~x[i]
\(\binary{0}\) \(\binary{1}\)
\(\binary{1}\) \(\binary{0}\)
Table4.3.4exclusive or

Make sure that you distinguish these bitwise logical operators from the C/C++ logical operators, &&, ||, and !. The logical operators work on groups of bits organized into integral data types rather than individual bits. For comparison, the truth tables for the C/C++ logical operators are shown in Table 4.3.6Table 4.3.8.

x y x && y
\(\binary{0}\) \(\binary{0}\) \(\binary{0}\)
\(\binary{0}\) non-zero \(\binary{0}\)
non-zero \(\binary{0}\) \(\binary{0}\)
non-zero non-zero \(\binary{1}\)
x y x || y
\(\binary{0}\) \(\binary{0}\) \(\binary{0}\)
\(\binary{0}\) non-zero \(\binary{1}\)
non-zero \(\binary{0}\) \(\binary{1}\)
non-zero non-zero \(\binary{1}\)
x !x
\(\binary{0}\) \(\binary{1}\)
non-zero \(\binary{0}\)