TAOCP 7.1.3 Exercise 168

We start by separating three independent issues: the word packing geometry, the toroidal indexing, and the correctness of the bit-parallel update.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 168. ▶ [23] [23] To keep an image finite, we might insist that a 3 × 3 cellular automaton treats a M ×N bitmap as a torus, wrapping around seamlessly between top and bottom and between left and right. The task of simulating its actions efficiently with bitwise operations is somewhat tricky: We want to minimize references to memory, yet each new pixel value depends on old values that lie on all sides. Furthermore the shifting of bits between neighboring words tends to be awkward, taxing the capacity of a register. Show that such difficulties can be surmounted by maintaining an array of n-bit words Ajk for 0 ≤j ≤M and 0 ≤k ≤N ′ = ⌈N/(n−2)⌉. If j ̸= M and k ̸= 0, word Ajk should contain the pixels of row j and columns (k −1)(n −2) through k(n −2) + 1, inclusive; the other words AMk and Aj0 provide auxiliary buffer space. (Notice that some bits of the raster appear twice.)

Verified: no
Solve time: 2m33s

We start by separating three independent issues: the word packing geometry, the toroidal indexing, and the correctness of the bit-parallel update. The original argument was essentially correct about the packing idea, but it conflated word arithmetic with bitwise parallel logic and did not justify that no cross-lane interference occurs.

1. Word representation and coverage of the bitmap

Let each machine word have $n$ bits, indexed from $0$ (least significant) to $n-1$. We reserve the least significant and most significant bit positions of each word as overlap cells, so each word carries $n-2$ useful pixels.

Define

$$ N' = \left\lceil \frac{N}{n-2} \right\rceil. $$

We store the bitmap in words $A_{jk}$, where $0 \le j \le M$ and $0 \le k \le N'$. For $1 \le j \le M-1$ and $1 \le k \le N'-1$, the word $A_{jk}$ encodes the pixels in row $j$, columns

$$ (k-1)(n-2), \ldots, k(n-2)-1, $$

placed into bit positions $1,2,\ldots,n-2$ of the word.

Thus adjacent words overlap in exactly two pixel columns: the rightmost payload bit of $A_{j,k-1}$ and the leftmost payload bit of $A_{jk}$ represent adjacent spatial columns. This overlap ensures that when we later shift a word left or right by one bit, every neighbor cell needed for a $3 \times 3$ stencil is present in at least one of the two adjacent words.

The boundary words $A_{j0}$, $A_{jN'}$, $A_{0k}$, and $A_{Mk}$ are used purely as buffers implementing wrap-around. For each fixed $j$, we define row periodicity by

$$ A_{0k} = A_{Mk}, \quad A_{M k} = A_{1k}, $$

and similarly for columns through the overlap convention, so that every access to $j-1$ or $j+1$, and every horizontal shift across block boundaries, has a valid representative. No conditional tests are required during evaluation.

2. Why a 2-bit overlap is sufficient

Each cell depends on a $3 \times 3$ neighborhood, so horizontally a cell at position $i$ depends on columns $i-1,i,i+1$. When columns are packed in blocks of width $n-2$, a boundary column $i$ and its neighbors $i \pm 1$ may lie in adjacent words.

When a word is shifted left or right by one bit, the only information that crosses a word boundary is exactly one column of pixels. Because adjacent words already redundantly store the boundary column via the overlap, every required neighbor bit is present either in the current word or in one of its two adjacent words. No second-level propagation is ever required, since a shift by at most one position is sufficient to align all horizontal neighbors.

Thus every $3 \times 3$ neighborhood is contained within the union of three adjacent words in each row band.

3. Correct bit-parallel evaluation without cross-lane interference

The critical correction concerns arithmetic. The original solution incorrectly appealed to “word addition.” Ordinary integer addition is not used at all, because carries would mix unrelated bit positions.

Instead, each bit position of the word is treated as an independent Boolean lane. All operations are performed using bitwise logical operators, which act independently on each bit position. No operation introduces interaction between different bit positions.

For each cell, define the nine input bit-planes:

$$ x_{NW}, x_N, x_{NE}, x_W, x, x_E, x_{SW}, x_S, x_{SE}, $$

each represented as a word.

We must compute, for each bit position independently, the integer

$$ s = x_{NW}+x_N+x_{NE}+x_W+x+x_E+x_{SW}+x_S+x_{SE} \in {0,\ldots,9}. $$

This is a per-bit population count of nine Boolean variables. It is computed using a carry-save adder tree, but crucially all “carries” remain within the same bit position; there is no cross-bit propagation because we never use arithmetic word addition.

We proceed in a standard bitwise fashion. First group the nine inputs into triples and apply the carry-save identity on each bit position:

$$ \text{sum}(a,b,c) = a \oplus b \oplus c, $$

$$ \text{carry}(a,b,c) = (a \wedge b)\ \vee\ (a \wedge c)\ \vee\ (b \wedge c). $$

Both expressions are purely bitwise, so they act independently on every bit position of the word. Importantly, no shifting is used in these identities, so no information moves between bit positions.

We combine the nine inputs into three intermediate words $S_1, C_1$, then again into $S_2, C_2$, and finally obtain a binary representation of the per-bit counts. At every stage, each word represents one bit-plane of the per-cell count, not an arithmetic integer across the word.

After this reduction we obtain, for each cell position independently, a 4-bit binary number representing the number of ones in its $3 \times 3$ neighborhood.

4. Threshold evaluation

The cellular automaton rule is

$$ 2 < s < 4, $$

which is equivalent to $s \in {3}$ in the Life-style interpretation used here.

Let $s_0, s_1, s_2, s_3$ be the bit-planes of the final 4-bit count. The condition $s=3$ is detected by the Boolean expression

$$ \text{next} = s_1 \wedge s_0 \wedge \neg s_2 \wedge \neg s_3, $$

applied bitwise across the word. Again, this is purely per-bit logic with no cross-position interaction.

Thus each output word $A'_{jk}$ is computed entirely by a fixed number of shifts and bitwise logical operations applied to a constant number of neighboring words.

5. Torus consistency and indexing

The arrays $A_{0k}$ and $A_{Mk}$ duplicate rows to implement vertical wrap-around:

$$ A_{0k} = A_{M-1,k}, \quad A_{M k} = A_{1k}. $$

Similarly, horizontal wrap-around is handled by interpreting column indices modulo $N$ at the level of pixel positions before packing into blocks. Because boundary columns are also duplicated into overlap regions, every required neighbor of a boundary cell appears in a valid word without special-case handling during computation.

Thus every access $A_{j+\delta_1, k+\delta_2}$ for $\delta_1,\delta_2 \in {-1,0,1}$ is well-defined under these identifications.

6. Conclusion

The representation uses $n$-bit words carrying $n-2$ effective pixels with a 2-bit overlap, ensuring that all horizontal shifts required by a $3 \times 3$ stencil remain local to adjacent words. The toroidal boundary is handled by explicit row and column duplication so that all neighbor references are always valid.

The update rule is implemented entirely using bitwise logical operations and carry-save reduction applied independently at each bit position. No machine-word addition is used, so there is no cross-lane interference. Each cell evolves independently in parallel, as required.

This yields an efficient toroidal simulation of the $3 \times 3$ cellular automaton using broadword operations with constant-time per word update. ∎