Exercise 5.15.A cellular automaton is a simple “machine” that can change its internal state in response to the states of nearby automata. We already met such automata in Exercise 2.6: in the Game of Life, cells live and die on a two-dimensional grid depending on the number of neighbors in their immediate vicinity.
In this exercise we are concerned with elementary cellular automata, which are the simplest such automata: They have two internal states, on or off, and are influenced by their direct neighbors to the left and right. The behavior of such an automaton can be
specified graphically as follows:
The three squares in the top row show the current state of a cell and its two neighbors. Since each cell can be either on or off, there are \(2^3=8\) different configurations of these three cells. The single square in the bottom row indicates the new state of the cell in the center. For example, the first column
tells us that a cell turns off if it is surrounded by two active cells. This transition table is also called the automaton’s rule.
We can visualize the behavior of different rules by starting with a row of cells in which only the one in the center is on:
We assume that cells wrap around, which means that the leftmost and rightmost cells are considered neighbors; this convention is also known as periodic boundary conditions. We can now determine the new state of each cell using the rule shown above. Since most cells and their neighbors are off, the last column of the rule tells us that they remain off; The exception
are the three cells in the center, which turn on. After the first step the cells are in the following state:
In the next generation, the three cells in the center have more than one active cell in their neighborhood so they turn off, but the two cells on the boundary turn on:
If you continue in this way and stack all the generations on top of each other, you obtain the image shown in Fig. 5.7. It’s our old friend the Sierpiński triangle, this time produced using a cellular automaton.
Figure 5.7 Successive generations of the cellular automaton discussed in the text. The top row contains a single active cell in the center, and each successive row shows the evolution of the previous row.
a) Consider the rule shown in the following picture:
Start again with a single active cell and manually construct the next five generations. What pattern do you observe?
In our discussion so far, we have described cellular automata in a tabular form, by listing all combinations of cells and their two direct neighbors in the top row and the resulting state in the bottom row. The top row is fixed, but the bottom row can be chosen freely, so there
are \(2^8=256\) different elementary automata. We can assign a unique integer to each such automaton by interpreting the bottom row as a binary number. For instance, the bottom row of the cellular automaton that generates the Sierpiński triangle corresponds to the binary number \(00010110_2\), which
is 22 in decimal; this rule is therefore called rule 22.
b) What is the number of the rule in part (a)?
c) Write a program that takes a rule as a number between 0 and 255 and simulates the corresponding cellular automaton by evolving a one-dimensional array of cells, returning a new array of cells. Use periodic boundary conditions.
d) Study the behavior of all 256 elementary cellular automata by creating images similar to the one in Fig. 5.7. Which rules generate interesting patterns?
Large Bit Sets
Exercise 5.16.In Section 5.4 we discussed how to represent sets of small integers using bits
and how to perform elementary set operations using bit operations. In this exercise we will implement a class BitSet that uses arrays of integers to store and manipulate bit sets of arbitrary size.
An outline of the class we will implement is shown in Listing 5.10. There is a single field bits[] that holds the bit set itself. The size of the array determines the range of integers that can be stored in the data structure: An array
of \(n\) long integers has \(64n\) bits and can therefore represent sets of integers in the range from 0 up to and including \(64n-1\). All methods that modify the bit set must enlarge the array if necessary.
Listing 5.10ch5 / BitSet
// A set of integers stored in an array of bits.
public class BitSet implements Iterable<Integer> {
private long[] bits = new long[1];
public BitSet() {}
// ...
}
Let’s start with our first set of methods that handles access to individual elements of the set.
a) Implement an add() method that adds a number to the bit set by setting the corresponding bit to 1. The method must enlarge the bits[] array if
necessary.
public boolean add(int value);
The return value of add() indicates whether the set was modified by the operation, in other words, it returns true if value wasn’t contained in the set before.
b) Implement contains() and remove().
public boolean contains(int value);
public boolean remove(int value);
The contains() method tests whether an integer is contained in the set, and remove()
removes an integer from the set. How do you handle numbers that lie outside the range of the current bits[] array?
The default constructor in Listing 5.10 creates an empty set, but often it’s convenient to be able to initialize the set using either an existing bit set or an arbitrary collection of integers.
c) Implement the following two constructors:
public BitSet(BitSet other);
public BitSet(Collection<Integer> other);
Both constructors create a new bit set from a given set or collection of integers.
d) Implement equals() and hashCode().
public boolean equals(Object o);
public int hashCode();
The equals() and hashCode() methods should be implemented in such a way that any two
BitSets that contain the same numbers are considered equal and have the same hash code.
e) Implement size() and isEmpty().
public int size();
public boolean isEmpty();
The size() method returns the number of elements in the bit set (that is, the population count of the bit pattern), and isEmpty() checks if the set is empty.
f) Implement the following four methods.
public boolean containsAll(BitSet other);
public boolean addAll(BitSet other);
public boolean removeAll(BitSet other);
public boolean retainAll(BitSet other);
The containsAll() method implements the subset relation \(\mathtt {this}\subseteq \mathtt {other}\) and returns true if all elements of this are also
contained in other. The other three methods modify the elements of this based on the elements of other: addAll() adds all elements of other, effectively computing the set union \(S\cup T\); removeAll() removes all elements
contained in other which corresponds to the set difference \(S-T\); and retainAll() removes all elements that are not contained in other which corresponds to the set intersection \(S\cap T\).
BitSet implements the Iterable interface, which makes it possible to iterate over the elements of the set. This interface requires that we implement a single method iterator() that creates a new Iterator object that can be used to loop over the numbers stored in the set.
// Iteration
public Iterator<Integer> iterator();
(The Iterator interface is described in Appendix B.5.)
g) Design a class Iter that implements Iterator and can be used to iterate over the elements of a BitSet. Implement BitSet.iterator(). Hint: Since the class needs access to the internal representation of BitSet, it should be defined as a nested class.
Counting Bits
Exercise 5.17.The number of 1-bits in a bit sequence, often called its population count, is an important quantity that naturally occurs in many applications. The population count is simply the sideways sum of the binary digits; for example, the population count of \(11010111\)
is \(1+1+0+1+0+1+1+1=6\). In this exercise we discuss a fast algorithm for computing the population count.2
To count the 1-bits in a number \(n\), we can use a divide-and-conquer algorithm that is similar to the recursive min function we discussed in Section 3.1: split \(n\) into to halves,
count the bits in each half and then add the results. If we repeat this process recursively, splitting each sequence of bits into smaller and smaller parts, we are eventually left with the problem of computing the population count of a single bit, which is just the value of the bit itself. For example, to count the
bits in 11010010, we first split it into two halves 1101 and 0010, then into groups of two bits, and finally into individual bits as shown in the left part of Fig. 5.8.
Figure 5.8 Counting bits using divide-and-conquer. First divide the bits into smaller groups, then add them pairwise.
We then work our way up, counting the number of bits in each subtree by starting at the leaves and replacing each node with the sum of its two children. For the 2-bit groups, the population counts are 2, 1, 0, and 1; for the 4-bit groups \(2+1=3\) and \(0+1=1\), and for the original 8-bit
number \(3+1=4\). This phase of the algorithm illustrated in the right part of Fig. 5.8.
By itself, this decomposition doesn’t buy us anything: To compute the population count of a \(B\)-bit integer, it still requires \(B-1\) additions, which is no better than iterating over the bits one by one. But there is a trick that lets us compute the numbers at each level of the tree in parallel. Consider
the nodes just above the leaves, each of which holds the sum of of a pair of adjacent bits. We can compute these four sums in parallel by extracting the bits at odd positions and the bits at even positions, aligning the resulting bit patterns by shifting the bits at odd positions one place to the right, and then
adding the bit patterns as if they were regular integers.
Let’s see how this works for \(n=11010010_2\). First we extract from the bit pattern of \(n\) the bits at even and the bits at odd positions and shift the odd bits one place to the right:
\(\seteqnumber{0}{5.}{9}\)
\begin{align*}
n \AND 01010101_2 &= 01010000_2 && \text {even bits}\\ (n \AND 10101010_2) \shr 1 &= 01000001_2 && \text {odd bits}
\end{align*}
Adding these two bit patterns yields
\(\seteqnumber{0}{5.}{9}\)
\begin{align*}
& 01010000_2\\ + & 01000001_2\\ = & 10010001_2.
\end{align*}
If we interpret the result as four 2-bit numbers, the result is \((10_2,01_2,00_2,01_2)\) or \((2, 1, 0, 1)\), which is the number of bits in the 2-bit groups of the original number \(n\). The whole computation can be implemented using just a few bit operations and one addition:
int n2 = (n & 0x55) + ((n >>> 1) & 0x55);
(By shifting n before extracting the bits at even positions, we can use the same bit mask0x55 twice.) By adding even and odd bits in this way, we effectively perform four additions in parallel!
Each 2-bit block of n2 now contains a number between 0 and 2. Using almost the same trick again, we can sum all 2-bit blocks in parallel:
int n4 = (n2 & 0x33) + ((n2 >>> 2) & 0x33)
This extracts all 2-bit blocks at odd and even positions, aligns them, and adds them to produce two 4-bit numbers that again hold contain the number of bits in the corresponding region of the original number \(n\). Finally, we add the two resulting 4-bit numbers:
int n8 = (n & 0x0f) + ((n >>> 4) & 0x0f)
The variable n8 now holds the population count of the original number n.
Extend this scheme to compute the population count of a 64-bit integer and implement the resulting algorithm.
Exercise 5.18.There is an elegant algorithm for counting the number of trailing zero-bits in an integer that is based on the idea of binary
search. Suppose we want to compute \(\text {ntz}(64, v)\), the number of trailing zeros in a 64-bit integer \(v\). If the lower 32 bits of \(v\) are all 0, we count the number of trailing zeros in the upper half of \(v\) and
add \(32\); otherwise, we simply count the number of trailing zeros in the lower half of \(v\):
\(\seteqnumber{0}{5.}{9}\)
\begin{equation*}
\text {ntz}(64, v) = \begin{cases} 32+\text {ntz}(32, v \shr 32) & \text {if the lower 32~bits of $v$ are zero};\\ \text {ntz}(32, v) & \text {otherwise}. \end {cases}
\end{equation*}
We can use the same idea to express \(\text {ntz}(32,v)\) in terms of \(\text {ntz}(16, v)\), and so on. Since every step halves the number of bits that must be inspected, computing the number of trailing zeros of an \(n\)-bit integer requires just \(O(\log _2 n)\) steps.
a) The base case of the recursive scheme sketched above is the function \(\text {ntz}(1, v)\), which computes the number of trailing zeros of a 1-bit number \(v\). How is this function defined?
b) Use this technique to implement a function countTrailingZeros() that computes the number of trailing zeros of a long integer. Hint: you can get rid of the recursion by
rewriting code of the form
if (v & 0xffffffff != 0) {
return 32 + ntz(32, v >>> 32);
} else {
return ntz(32, v);
}
as
int count = 0;
if (v & 0xffffffff != 0) {
count += 32;
v >>>= 32;
}
return count + ntz(32, v);
c) Use the same idea to define a function \(\text {nlz}(64, v)\) that computes the number of leading zeros of a 64-bit integer \(v\), that is, the number of zeros to the left of the most significant 1-bit.
d) Implement a function that computes the number of leading zeros. Can you find a trick to get rid of the recursion?
2 In practice, the fastest way to compute the population count is usually the bitCount() function defined in Long and Integer, which uses hardware instructions if available.
