So far we have treated the bits in an integer as abstract “bit patterns,” but there is an alternative interpretation that is just as useful. If we identify each bit with its position in the pattern, a group of bits can also be regarded as a set of integers. For instance, a group of four bits can represent all possible sets
of the four integers \(0, 1, 2, 3\):
The \(k\)th bit is set to 1 if the number \(k\) is contained in the set. The same idea works for any number of bits: There is a one-to-one correspondence between \(n\)-bit patterns and sets of integers in the range \(0\isep n-1\). Bit patterns that are used in this way are also called bit sets. When working with sets of small integers, bit sets consume far less memory than other set data structures, and they are also significantly faster. As we will see, most set operations can be expressed using simple bit operations.
Constructing Bit Sets
Let’s start with a few ways of constructing bit sets. The empty set \(\emptyset \) is trivial to construct since it is always represented by the number 0, and for singleton sets that contain a single integer \(\{k\}\), the corresponding bit set consists of a single bit at position \(k\), which we can construct by shifting 1 the required number of places to the
left:
\(\seteqnumber{0}{5.}{8}\)
\begin{align*}
\emptyset \quad &\longleftrightarrow \quad 0\\ \{k\}\quad &\longleftrightarrow \quad 1 \shl k
\end{align*}
The bitwise OR of two or more such singleton sets produces a bit set that contains multiple integers. For instance, the bit set that contains two integers \(k\) and \(l\) has 1-bits at those same positions:
\(\seteqnumber{0}{5.}{8}\)
\begin{align*}
\{k,l\}\quad &\longleftrightarrow \quad (1\shl k) \OR (1\shl l).
\end{align*}
Similar relationships hold for more than two elements.
The functions bit() and bits() in Listing 5.5 implement these two operations and return long integers with bits at the specified positions. Notice that the bits() functions has normal set semantics in the sense that the entries in positions can be in any order and contain
duplicates. For instance, just as \(\{3, 3, 1\} \) and \(\{1, 3\}\) denote the same set of integers, the two calls bits(3, 3, 1) and bits(1, 3) produce the same bit set.
Listing 5.5ch5β―/β―Bits
// Return a long integer that has the k-th bit set.
public static long bit(int k) {return 1L << k;}
// Return a long integer that has the specified bits set.
public static long bits(int... positions) {
long bits = 0;
for (int n : positions)
bits |= 1L << n;
return bits;
}
A different approach is useful for constructing bit sets that consist of a sequence of consecutive integers. As we discussed in Section 5.2, the bit pattern of \(2^n-1\) consists of \(n\) ones in the least significant bits and
zeros elsewhere, whereas the bit pattern of \(-2^n\) consists of \(n\) zeros in the least significant and ones elsewhere. We therefore have the following correspondence between sets and bit sets:
\(\seteqnumber{0}{5.}{8}\)
\begin{align*}
\{0,1,\ldots ,n-1\}\quad &\longleftrightarrow \quad 2^{n}-1\\ \{n,n+1,\ldots ,63\}\quad &\longleftrightarrow \quad -2^{n}
\end{align*}
Likewise, the set \(\{k, k+1, \ldots , k+n-1\}\) can be obtained by first computing \(2^n-1\) and then shifting the result \(k\) places to the left. The two functions in Listing 5.6 use these identities to create bit
sets for ranges of integers. The first range() function with two arguments creates a bit set that includes every integer from first up to but not including stop. For instance, range(0,0) returns the empty set and range(5, 8) the set \(\{5, 6, 7\}\). The range()
function with one argument creates a bit set that includes the numbers between first and 63.
Listing 5.6ch5β―/β―Bits
// The bit set containing the numbers first to stop (exclusive).
public static long range(int first, int stop) {
int n = stop - first;
long nBits = n == 64 ? -1L : (1L << n) - 1;
return nBits << first;
}
// The bit set containing the numbers from first to 63.
public static long range(int first) {
return -(1L << first);
}
A technical detail is worth noting about the implementation of range(). In line 4, where we compute a bit pattern that contains n 1-bits, we handle the case for
n == 64 specially. This is necessary because in Java all shift operators don’t behave as expected when shifting a long by 64 or more places or a int by 32 or more
places. The details are explained in the following note.
The exact rules Java uses to evaluate bit shifts are somewhat arcane because they are modeled after the behavior of bit shifts instructions on microprocessors in the 1990s. The general rule is that bit shifts of the form x << k, x >> k, and x >>> k use only the lowest six bits of k when x is a 64-bit integer, and only the lowest five bits if x is a 32-bit
integer. For this reason, the expression 1L << 64 is equivalent to 1L << 0 because the lowest six bits of 64 are zero; similarly, 1L << 65 is equivalent to
1L << 1. An unfortunate consequence of this rule is that 1L << 64 produces a different result than (1L << 63) << 1. Because this is rarely the expected outcome, it is usually best to shift by at most
63 or 31 places and handle other cases explicitly.
Set Operations
In the implementations of bits() in Listing 5.5, we used the bitwise OR operator to combine multiple individual bits.
It’s not hard to see that the OR operator computes the union of two bit sets in general. For example, the union of the two sets \(A=\{1, 4, 7\}\) and \(B=\{0, 5, 7\}\) is \(\{0, 1, 4, 5, 7\}\), and for the corresponding bit sets we have
\(\seteqnumber{0}{5.}{8}\)
\begin{equation*}
\begin{array}{rr} S & \bits {10010010}\\ T & \bits {10100001}\\ \midrule S \OR T & \bits {10110011} \end {array}
\end{equation*}
Similarly, the bitwise AND operator computes the intersection of two sets, that is, the set of all elements that are contained in both sets. The intersection of \(\{1, 4, 7\}\) and \(\{0, 5, 7\}\) is \(\{7\}\), and for the corresponding bits sets we have
\(\seteqnumber{0}{5.}{8}\)
\begin{equation*}
\begin{array}{rr} S & \bits {10110011}\\ T & \bits {10100001}\\ \midrule S\AND T & \bits {10000000} \end {array}
\end{equation*}
Just like the intersection of two sets determines which elements they have in common, the intersection of two bit sets determines which 1-bits they have in common. We therefore have the following correspondences:
\(\seteqnumber{0}{5.}{8}\)
\begin{equation*}
\boxed { \begin{aligned} S\cup T\quad &\longleftrightarrow \quad S \OR T\\ S\cap T\quad &\longleftrightarrow \quad S \AND T \end {aligned} }
\end{equation*}
Finally, the set difference \(S-T\) is defined as the set of elements that are contained in \(S\) but not in \(T\). For example, if \(S=\{1, 4, 7\}\) and \(T=\{0, 5, 7\}\), the set difference is \(S-T=\{1, 4\}\). Conceptually, there are two ways to compute the set difference: You either
remove the elements of \(S\) that are also contained in \(T\), or you retain the elements of \(S\) that are not contained in \(T\). This second definition can be expressed as the intersection of \(S\) with the complement of \(T\), that is, the set \(\overline {T}\) that contains all elements that are not in \(T\):
\(\seteqnumber{0}{5.}{8}\)
\begin{equation}
\label {eq:setdiff} S-T = S \cap \overline {T}.
\end{equation}
If \(S=\{1, 4, 7\}\) and \(T=\{0, 5, 7\}\), as in the example above, the set difference can be computes as
The set \(\{1, 2, 3, 4, 6, 8, \ldots \}\) contains all integers except 0, 5, and 7.
The main advantage of expressing set differences in this way is that Eq. (5.9) can be translated directly into bit operations. The complement of a bit set is obtained by inverting all bits using
the NOT operator, so the set difference \(S-T\) can be written as S & ~T:
For instance, if \(S=\bits {10010010}\) and \(T=\bits {10100001}\), the complement of \(T\) is \(\NOT T=\bits {01011110}\) and the set difference \(S\AND \NOT T\) becomes
\(\seteqnumber{0}{5.}{9}\)
\begin{equation*}
\begin{array}{rr} S & \bits {10010010}\\ \NOT T & \bits {01011110}\\ \midrule S \AND \NOT T & \bits {00010010} \end {array}
\end{equation*}
The resulting bit pattern 00010010 can again be interpreted as the set \(\{1, 4\}\).
We can use set intersections to implement several important membership tests for bit sets. For example, two sets share no elements if their intersection is empty, and at least one element if it is nonempty. Similarly, if \(S\) is any set and \(x\) is a single element, the intersection
\(S\cap \{x\}\) is empty only if \(S\) doesn’t contain \(x\) :
The functions containsNone(), containsSome(), and contains() in Listing 5.7 implement these three operations for bit sets.
Listing 5.7ch5β―/β―Bits
// Return true if the bit sets 's' and 't' are disjoint.
public static boolean containsNone(long s, long t) {
return (s & t) == 0;
}
// Return true if the bit sets 's' and 't' have common elements.
public static boolean containsSome(long s, long t) {
return (s & t) != 0;
}
// Return true if the bit set 'set' contains the number 'k'.
public static boolean contains(long set, int k) {
return (set & (1L << k)) != 0;
}
// Return true if the bitset 't' is a subset of 's'.
public static boolean containsAll(long s, long t) {
return (s & t) == t;
}
Finally, \(T\) is a subset of \(S\) if the intersection of \(S\) and \(T\) is equal to \(T\):
\(\seteqnumber{0}{5.}{9}\)
\begin{equation*}
T\subseteq S\quad \text {if and only if}\quad S\cap T=T.
\end{equation*}
For bit sets, the right-hand side again translates to a simple expression involving bit operations:
\[ \boxed { T\subseteq S \quad \longleftrightarrow \quad S \AND T = T } \]
The function containsAll() in Listing 5.7 can be used to test whether one bit set is a subset of another. A summary of set operations and
their implementation using bits is provided in Table 5.1.
Table 5.1
Correspondence between sets and bit sets
.
Operation
Sets
Bit sets
Empty set
\(\emptyset \)
0
Singleton set
\(\{x\}\)
1 << x, bit(x)
Sets of integers
\(\{x_0, x_1,\ldots \}\)
(1 << x0) | (1 << x1) | ...
bits(x0, x1, ...)
\(\{a, a+1, \ldots , b-1\}\)
range(a, b)
\(\{a, a+1, \ldots , 63\}\)
range(a)
Complement
\(\overline S\)
~s
Intersection
\(S\cap T\)
s & t
Union
\(S\cup T\)
s | t
Difference
\(S-T\)
s & ~t
Containment
\(x\in S\)
s & (1 << x) != 0
Equality
\(S=T\)
s == t
Subset
\(T\subseteq S\)
(s & t) == t
Exercises
Exercise 5.10.Given two bit sets s and t, what is the meaning of the expression (s | t) == t?
Exercise 5.11.If \(S\) and \(T\) are bit sets, what is the interpretation of \(S\XOR T\), where “\(\XOR \)” is the XOR operator?