Bit Vectors

It should come as no surprise that the author has a fairly large collection of games. A small sampling of games, with some of their properties, is listed in Figure 12-1.

When the author gets together with friends, he often has to answer the question, "Which game shall we play?" Sometimes people want something quick and light that can be played while waiting for others to arrive. Other times, people are ready to settle down for an evening-long brain-burner. If, for example, there are five people and they want to play a strategy game taking 12 hours, the options are Formula Dé, El Grande, and Puerto Rico. Let's write a program to list the appropriate games for any situation.

We could maintain a set of Game objects, each of which has a field for each of the various attributes. A more space-efficient option is to maintain, for each game, a single integer encoding all of the game's attributes (except the title). This representation is called a bit vector (Figure 12-2).

Figure 12-2. In a bit vector, each bit represents a single feature of the game. For example, El Grande can take 2, 3, 4, or 5, players, plays in 12 hours, is of high difficulty, and involves strategy.

(This item is displayed on page 327 in the print version)

If we think of each game as having a set of features, we recognize this as a variation of direct addressing (Section 11.4). For example, the bit vector for Bohnanza represent the set of features:

{3-player, 4-player, 5-player, 6-player, 7-player, less-than-1-hour, medium-difficulty, diplomacy, luck}

Bit vectors make it easy to efficiently perform certain set operations, such as intersection and union. For example, if we want to know what Bohnanza and El Grande have in common, we take the intersection of their feature sets (Figure 12-3).

Figure 12-3. The bitwise intersection of two bit vectors tells what elements two sets have in common. In the resulting bit vector, the bits that are on in both of the others are on. Here, Bohnanza and El Grande can both handle 35 players.

(This item is displayed on page 327 in the print version)

If we want to know if a game is suitable for a particular situation, we can make up a bit vector for the situation (Figure 12-4). The intersection of a game's bit vector with the situation bit vector with the situation bit vector tells what they have in common. If this is equal to the situation bit vector, the game has all of the required features.

Figure 12-4. If a game's intersection with the situation equals the situation, the game is suitable. It does not matter that this situation does not specify a desired difficulty level.

(This item is displayed on page 327 in the print version)

In Java, we can represent a bit vector with up to 32 features using an int. The bit vector

represents the number 4 in binary. In our example, this bit vector also represents a 3-player game, with the extra bits at the left being ignored.

In binary, the number 2i is represented by a bit vector with only the ith bit from the right turned on. Put another way, it is a 1 with i zeroes after it.

Java has an operator << for shifting a pattern of bits to the left a given number of spaces. If we want a bit vector with only the fifth bit turned on, we use the Java expression:

1 << 5

If we want several bits turned on, we simply take the union of the bit vectors for the individual bits. The bitwise or operator | allows us to find the union of two bit vectors. For example, to produce the bit vector

we use the Java expression:

(1 << 0) | (1 << 5) | (1 << 9)

Manipulating individual bits like this manually would be incredibly tedious and error prone. Instead, we define constants (Figure 12-5). The static method playerRange() is provided because many games can accept a range of player numbers.

Figure 12-5. Constants and the playerRange() function make specifying bit vectors for games much easier.

Now we can specify the bit vector for Lord of the Fries simply as:

playerRange(3, 8) | LESS_THAN_AN_HOUR | MEDIUM_DIFFICULTY | LUCK

Java's bitwise operators are listed in Figure 12-6. Almost all modern processors have built-in instructions for these operations, so they are extremely fast.

Figure 12-7 provides some examples of these operations.

A couple of things to watch out for:

• Be careful not to confuse the logical and operator && with the bitwise and operator &. The former is used with boolean values, the latter with numerical primitive types. For added confusion, if you use & on two boolean values, you'll get their logical andbut not short-circuited! A similar warning applies to || vs |.
• There are two different shift right operators, which differ in the way they handle the leftmost bit. Suppose we have the bit vector:

  10000000010000000000001000000000

  Shifting it two places to the right with >>> does what we would expect:

  00100000000100000000000010000000

  In contrast, shifting it two places to the right with >> copies the leftmost bit:

  11100000000100000000000010000000

  This option is included because bitwise operators are also sometimes used to multiply and divide ints by powers of two. In decimal notation, we can multiply a number by 103 = 1,000 by shifting it three places left. Similarly, in binary, we can multiply a number by 23 = 8 by shifting it three places left. To divide by a power of two, we shift to the right.

  Computers represent negative integers using a special binary notation which is beyond the scope of this book. The important detail here is that the leftmost bit is a 1 in a negative number, so shifting a negative number to the right with >>> would incorrectly produce a positive result. The >> works correctly for division.

  We should use >> for numerical division by powers of two, but >>> for shifting bit vectors to the right.

We now know more than enough to write the GameCollection class (Figure 12-8). The only nonconstant field is games, which maps Strings (game titles) to Integers (bit vectors).

Figure 12-8. The GameCollection class.

The loop on lines 2731 iterates through the entries in this map. Each value of game is of type Map.Entry, so we can extract the key (title) or value (attribute bit vector) of the entry as needed.

A main() method which adds all of the games in Figure 12-1 and then invokes findGames() is shown in Figure 12-9.

Figure 12-9. After adding a bunch of games to the database, we can ask for one fitting certain constraints.

BitSets

If we want to keep track of a set with more than 32 potential elements, we can use the BitSet class in the java.util package (Figure 12-10). A BitSet represents a long bit vector as a series of binary numbers. It performs arithmetic (similar to that we'll do in Section 12.3) to find the right bit in the right number. Like an ArrayList, a BitSet can also grow as necessary. Of course, since BitSet is an encapsulated class, we don't have to think about the details; we can simply treat it as an arbitrarily long bit vector.

Figure 12-10. UML class diagram showing some of the methods in the java.util.BitSet class.

The and(), or(), and xor() methods have return types of void. Rather than returning a new BitSet, each of these modifies the existing BitSet. For example, if a is the BitSet 101100 and b is the BitSet 1010, then invoking a.or(b) changes a to 101110.

The cardinality() method returns the number of bits in a BitSet which are on. In contrast, length() returns the number of bits which are "in use," ignoring any leading zeroes. Continuing the example above, b.cardinality() returns 2, but b.length() returns 4.

The other methods are self-explanatory, given that int arguments specify indices in the BitSet. See the API for additional details and a few other methods.

Exercises