C Answers to Exercises
Chapter 5
Solution to Exercise 5.1
We assume that each long represents one row of the image and that the pixels of each row are stored in the least significant bits. We can then read the bits in each row from left to right and output a sequence of ones and zeros, as shown in Listing C.28.
Listing C.28ch5 / BitmapFont
public static void writePbm(
long[] image, int width, String fileName)
throws IOException {
try (var out = new PrintWriter(fileName)) {
out.println("P1");
out.printf("%d %d\n", width, image.length);
for (long row : image) {
long mask = 1L << (width - 1);
for (int i = 0; i < width; i++) {
out.print((row & mask) != 0 ? "1 " : "0 ");
mask >>>= 1;
}
out.println();
}
}
}
JDK: PrintWriter, String
Solution to Exercise 5.2
For left rotations we append the highest \(n\) bits to the lowest \(32-n\) bits, and for right rotations we append the highest \(32-n\) bits to the lowest \(n\) bits:
public static int rotl(int value, int n) {
return (value << n) | (value >>> (32 - n));
}
public static int rotr(int value, int n) {
return (value >>> n) | (value << (32 - n));
}
Solution to Exercise 5.3
The resulting images look as follows:
Solution to Exercise 5.4
First swap the two 16-bit halves and then exchange the bytes in each half:
static int reverseBytes(int value) {
int tmp = (value << 16) | (value >>> 16);
return ((tmp >>> 8) & 0x00ff00ff) | ((tmp & 0x00ff00ff) << 8);
}
Solution to Exercise 5.5
The bit pattern of \(-1\) is obtained by converting the number \(2^w + (-1)=2^w-1\) to binary; the binary representation of this number always consists of \(w\) ones.
Solution to Exercise 5.6
With ten bits we can store numbers between \(-512\) and \(511\), inclusively. Here is the completed table:
| number | bit pattern |
| 0 | 0000000000 |
| \(-1\) | 1111111111 |
| \(489\) | 0111101001 |
| \(-384\) | 1010000000 |
| \(-417\) | 1001011111 |
| \(231\) | 0011100111 |
Solution to Exercise 5.7
The expression computes \(2x+1\) and works for all integers \(x\), provided \(2x+1\) doesn’t overflow. This is easy to see: For every even number in two’s-complement representation, setting the least significant bit is equivalent to incrementing the number by 1. (Of course, there are is no reason to prefer this solution to 2*x + 1 in practice.)
Solution to Exercise 5.8
The expression -1 >> k is always \(\lfloor -1/2^k\rfloor =-1\), and the resulting bit pattern consists of 32 ones. The expression -1 >>> k produces a bit pattern that consists of \(32-k\) ones.
Solution to Exercise 5.9
The sum is an expansion of the binary representation of the multiplier, so there is one term for each 1 in \(1111_2=15\).
It is sometimes possible to reduce the number of operations even further by factorizing the multiplier appropriately. For instance, we can rewrite \(15x\) as \(5\cdot (3\cdot x)\) to save one addition:
t = (x << 1) + x r = (t << 2) + (t << 1)
A similar technique can be used to speed up the computation of integer powers; see [60, Section 4.6.3].
Solution to Exercise 5.10
It’s an alternative way of testing whether s is a subset of t.
Solution to Exercise 5.11
The XOR operator returns the bits that are contained in exactly one of its two arguments. This operation is also known as the symmetric difference of two sets, which is usually denoted by the \(\triangle \) operator:
\(\seteqnumber{0}{C.}{4}\)\begin{equation*} \{1, 4, 7\} \mathbin {\triangle } \{0, 5, 7\} = \{1, 4, 5\} \end{equation*}
Solution to Exercise 5.12
If \(n=0\), there is no least significant bit that could be cleared, which is consistent with the result \(n\AND (n-1) = 0 \AND -1 =0\). If \(n\not =0\), we can write its bit pattern in the form \(\alpha 10^k\), where the single 1 denotes the least significant 1-bit, \(0^k\) the sequence of \(k\) zeros in the lowest bits of \(n\), and \(\alpha \) the most significant bits of \(n\), which we don’t care about. In two’s-complement representation, the bit pattern of \(n-1\) is \(\alpha 01^k\), both for positive and negative integers, so we have
\(\seteqnumber{0}{C.}{4}\)\begin{equation*} n \AND (n-1) = \alpha 10^k \AND \alpha 01^k = \alpha 0^{k+1}, \end{equation*}
which is the bit pattern of \(n\) with the least significant bit turned off. This argument also works for the smallest negative number \(n=-2^{w-1}\), where \(w\) is the bit-width. In this case, subtracting 1 from \(n\) overflows and produces the largest positive number \(n-1=2^{w-1}-1\),
Solution to Exercise 5.13
We can find the number of 1-bits in \(n\) by repeatedly clearing the least significant bit of \(n\) and counting the number of iterations required until \(n=0\) (Listing C.29). This algorithm for counting bits is known as Kernighan’s algorithm:1
Listing C.29ch5 / BitCount
// Kernighan's algorithm for counting bits.
public static int bitCountKernighan(long value) {
int count = 0;
while (value != 0) {
value &= value - 1;
count++;
}
return count;
}
Solution to Exercise 5.14
All powers of 2 have just a single bit set, so we can simple clear the least significant bit and check whether the result is 0:
public static boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
The simpler test (n & (n - 1)) == 0 is almost correct but fails for \(n=0\). Alternatively, we can check if the number is positive and has exactly one bit set:
public static boolean isPowerOfTwo(int n) {
return n > 0 && Integer.bitCount(n) == 1;
}
Solution to Exercise 5.15
a)The rule produces a checkerboard pattern.
b)Since \(00110010_2=50\), it’s rule 50.
c)We can store the current state of all cells as an array of integers cells: the \(k\)th cell is active if cells[k] is 1 and inactive if it is 0. Listing C.30 demonstrates how to compute the next generation of cells: We read the state of each cell and its two neighbors and compute its new state using nextState(). Computing the next state is easy once you understand how the numbering scheme for rules works. Given the rule’s number \(r\) and the current state of the cell and its neighbors \(c_0\), \(c_1\), and \(c_2\), the new state of the cell is simply the binary digit of \(r\) at position \((c_0c_1c_2)_2\).
Listing C.30ch5 / Cellular1D
// Evolve an array of elementary cellular automata.
public static void evolveCells(int rule, int[] cells, int[] next) {
for (int k = 0; k < cells.length; k++) {
int c0 = cells[k == 0 ? cells.length - 1 : k - 1];
int c1 = cells[k];
int c2 = cells[k == cells.length - 1 ? 0 : k + 1];
next[k] = nextState(c0, c1, c2, rule);
}
}
static int nextState(int c0, int c1, int c2, int rule) {
int neighborhood = (c0 << 2) | (c1 << 1) | c2;
return (rule & (1 << neighborhood)) != 0 ? 1 : 0;
}
d)Figures C.7 and C.8 show the evolution of rules 0 to 31 for two configurations of cells. In the first image, the top row contains exactly one active cell in the middle, whereas in the second image the top contains a random selection of active cells. Many rules eventually lead to a stable state in which each row is a (shifted) copy of a previous row, but a few rules produce fractal or chaotic patterns, including rules 18, 22, 26, and 30.
Solution to Exercise 5.16
a)All operations on an individual number \(k\) require us to locate the corresponding bit in bits[]. The “address” of \(k\) has two parts: the index of the long integer inside bits[], which is computed by dividing \(k\) by 64 (or by using an equivalent right-shift), and the bit index of the bit inside bits[index], which is the remainder of dividing \(k\) by 64. If index is larger than the current size of bits[] we have to reallocate the array (Listing C.31).
Listing C.31ch5 / BitSet
// Add a nonnegative number to the bit set.
public boolean add(int value) {
if (value < 0)
throw new IllegalArgumentException("Negative value");
int index = value >> 6;
long mask = 1L << (value & 0x3f);
if (index >= bits.length)
bits = Arrays.copyOf(bits, index + 1);
long oldValue = bits[index];
bits[index] |= mask;
return oldValue != bits[index];
}
JDK: Arrays, IllegalArgumentException
•BitSet
b)For numbers outside the allowed range, the contains() and remove() methods in Listing C.32 do nothing and simply return false. For all other values, contains() checks the correspondng bit, and remove() sets it to 0.
Listing C.32ch5 / BitSet
// Check whether 'value' is contained in the set.
public boolean contains(int value) {
int index = value >> 6;
long mask = 1L << (value & 0x3f);
return value >= 0 && index < bits.length
&& (bits[index] & mask) != 0;
}
// Remove 'value' from the set.
public boolean remove(int value) {
int index = value >> 6;
long mask = 1L << (value & 0x3f);
if (value >= 0 && index < bits.length) {
long oldValue = bits[index];
bits[index] &= ~mask;
return oldValue != bits[index];
}
return false;
}
c)The two constructors are shown in Listing C.33. The first one copies the given bit set by searching for the first nonzero entry in its bits[] array and then use Arrays.copyOf() to create an appropriately sized copy. The other constructor simply iterates over the integers in the collection and adds them to the bit set.
Listing C.33ch5 / BitSet
public BitSet(BitSet other) {
int n = other.bits.length;
while (n > 0 && other.bits[n - 1] == 0)
n--;
bits = Arrays.copyOf(other.bits, n);
}
public BitSet(Collection<Integer> c) {
for (int v : c)
add(v);
}
JDK: Arrays, Collection
•BitSet
d)The implementations of equals() and hashCode() are shown in Listing C.34. A bit set is considered equal to another object o if o is of type BitSet and both bit sets that have 1-bits at the same positions. To compare the 1-bits, we first check that the smaller of the two bits[] arrays is equal to the first part of the larger array and then verify that the larger array doesn’t contain any additional 1-bits. To compute the hash code of a bit set, we hash the contents of the bits[] array. We iterate over the array from right to left to ensure that the hash code isn’t affected by trailing zeros in bits[].
Listing C.34ch5 / BitSet
public boolean equals(Object o) {
if (!(o instanceof BitSet other))
return false;
int n = Math.min(bits.length, other.bits.length);
if (!Arrays.equals(bits, 0, n, other.bits, 0, n))
return false;
long[] rest = bits.length > n ? bits : other.bits;
for (int i = n; i < rest.length; i++) {
if (rest[i] != 0)
return false;
}
return true;
}
public int hashCode() {
int h = 0;
for (int i = bits.length - 1; i >= 0; i--)
h = h * 31 + Long.hashCode(bits[i]);
return h;
}
e)For the implementation of size(), we iterate over all elements of bits[] and use Long.bitCount() to count all 1-bits. For isEmpty(), we search for any nonzero entry in bits[].
Listing C.35ch5 / BitSet
public int size() {
int count = 0;
for (long b : bits)
count += Long.bitCount(b);
return count;
}
public boolean isEmpty() {
for (long b : bits) {
if (b != 0)
return false;
}
return true;
}
f)To implement the four set operations, we have to iterate over the bits of both bit sets and use the correspondences in Table 5.1. The main complication is that the bits arrays can differ in size. As in the implementation of equals(), we therefore split each function into two parts: The first part iterates over the common array entries and the second handles entries that exist only in the larger array. Listing C.36 demonstrates how to do this for containsAll(); the other three methods are implemented similarly.
Listing C.36ch5 / BitSet
public boolean containsAll(BitSet other) {
int n = Math.min(bits.length, other.bits.length);
for (int i = 0; i < n; i++) {
long a = bits[i], b = other.bits[i];
if ((a & b) != b)
return false;
}
for (int i = bits.length; i < other.bits.length; i++) {
if (other.bits[i] != 0)
return false;
}
return true;
}
// The implementations of addAll(), removeAll(), and retainAll()
// are similar and have been omitted.
g)The iterator for BitSet resembles the BitIterator class discussed in Section 5.5. The main difference is that we now iterate over an array of long integers and therefore have to keep track of the current position index inside this array (Listing C.37). The constructor Iter() initializes index and currentBits by searching the elements of bits[] for the first nonzero entry.
Listing C.37ch5 / BitSet.Iter
// Internal iterator class for BitSet.
private class Iter implements Iterator<Integer> {
int index = -1; // current position in BitSet.bits[]
long currentBits = 0; // remaining bits at current position
int lastValue = -1; // last value returned by next()
Iter() {
while (currentBits == 0 && index < bits.length - 1)
currentBits = bits[++index];
}
@Override
public boolean hasNext() {return currentBits != 0;}
@Override
public Integer next() {
lastValue =
(index << 6) + Long.numberOfTrailingZeros(currentBits);
currentBits &= currentBits - 1;
while (currentBits == 0 && index < bits.length - 1)
currentBits = bits[++index];
return lastValue;
}
@Override
public void remove() {BitSet.this.remove(lastValue);}
}
// Return an iterator that iterates over the numbers in this bit set.
@Override
public Iterator<Integer> iterator() {return new Iter();}
The remaining members of Iter implement the three methods of the Iterator interface: hasNext() checks whether the last bit has been reached, which in our case is only the case if currentBits is zero; next() computes the position of the current bit, which is obtained by adding the position of the least significant bit in currentBits to \(64\cdot \mathtt {index}\), and then advances the iterator by adjusting currentBits and index. Finally, the remove() method removes the last value returned by next() from the bit set.
Solution to Exercise 5.17
Listing C.38 demonstrates how to count the bits in a 64-bit integer by repeatedly adding adjacent groups of bits.
Listing C.38ch5 / BitCount
// Count bits using a divide-and-conquer scheme.
public static int bitCountSubdivide(long n) {
n = (n & 0x5555555555555555L) + ((n >> 1) & 0x5555555555555555L);
n = (n & 0x3333333333333333L) + ((n >> 2) & 0x3333333333333333L);
n = (n & 0x0f0f0f0f0f0f0f0fL) + ((n >> 4) & 0x0f0f0f0f0f0f0f0fL);
n = (n & 0x00ff00ff00ff00ffL) + ((n >> 8) & 0x00ff00ff00ff00ffL);
n = (n & 0x0000ffff0000ffffL) + ((n >> 16) & 0x0000ffff0000ffffL);
n = (n & 0x00000000ffffffffL) + ((n >> 32) & 0x00000000ffffffffL);
return (int) n;
}
Solution to Exercise 5.18
a)There are two 1-bit numbers, \(0_2\) and \(1_2\). The number of trailing zeros of \(0_2\) is 1 and the number of trailing zeros of \(1_2\) is 0, so we have
\(\seteqnumber{0}{C.}{4}\)\begin{equation*} \text {ntz}(1, v) = 1-v. \end{equation*}
b)The implementation in Listing C.39 expands the recursive function calls and eliminates the final call to \(\text {ntz}(1, v)\) by handling the case value == 0 at the start of the function. This implementation can be sped up even further by replacing the last three if statements with a lookup table.
Listing C.39ch5 / TrailingZeros
// Count the number of trailing zeros using a form of binary search.
public static int countTrailingZeros(long value) {
if (value == 0)
return 64;
int count = 0;
if ((value & 0xffffffffL) == 0) {
value >>>= 32;
count += 32;
}
if ((value & 0xffffL) == 0) {
value >>>= 16;
count += 16;
}
if ((value & 0xffL) == 0) {
value >>>= 8;
count += 8;
}
if ((value & 0xfL) == 0) {
value >>>= 4;
count += 4;
}
if ((value & 0x3L) == 0) {
value >>>= 2;
count += 2;
}
if ((value & 0x1L) == 0)
count += 1;
return count;
}
c)We use a similar expression as in the case of the \(\text {ntz}\) function:
\(\seteqnumber{0}{C.}{4}\)\begin{equation} \label {eq:nlz64} \text {nlz}(64, v) = \begin{cases} 32+\text {nlz}(32, v) & \text {if the upper 32~bits of $v$ are zero};\\ \text {nlz}(32, v \shr 32) & \text {otherwise}. \end {cases} \end{equation}
d)In this case, getting rid of the recursion is slightly more difficult because there is no obvious way to replace the two occurrences of nlz in Eq. (C.5) with a single function call. The trick is to rewrite the literal translation
if ((v & ~0xffffffff) == 0) {
return 32 + nlz(32, v)
} else {
return nlz(32, v >>> 32);
}
as
int count = 32;
if ((v & ~0xffffffff) != 0) {
count -= 32;
v >>>= 32;
}
return count + nlz(32, v)
and then expand nlz(32, v) in the same way. This gives us the implementation shown in Listing C.40.
Listing C.40ch5 / LeadingZeros
// Count the number of trailing zeros using a form of binary search.
public static int countLeadingZeros(long value) {
if (value == 0)
return 64;
int count = 63;
if ((value & ~0xffffffffL) != 0) {
value >>>= 32;
count -= 32;
}
if ((value & ~0xffffL) != 0) {
value >>>= 16;
count -= 16;
}
if ((value & ~0xffL) != 0) {
value >>>= 8;
count -= 8;
}
if ((value & ~0xfL) != 0) {
value >>>= 4;
count -= 4;
}
if ((value & ~0x3L) != 0) {
value >>>= 2;
count -= 2;
}
if ((value & ~0x1L) != 0)
count -= 1;
return count;
}