TAOCP 7.1.3 Exercise 157

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 157. [M21] [M21] Explain the recursion (148) for negaFibonacci predecessor and successor.

Verified: no
Solve time: 1m35s

Solution

Let $\alpha = (\alpha_1,\alpha_2,\ldots,\alpha_m)$ be a negaFibonacci code in the sense of Section 7.1.3, so that each $\alpha_i \in {0,1}$ and no two consecutive 1s occur. The value function $N(\alpha)$ is defined by the corresponding Fibonacci-weighted sum with alternating indexing as in the section, and validity of a code is preserved by the local identities

$F_k = F_{k-1} + F_{k-2},$

which induce the standard rewriting rules on bit patterns.

The recursion (148) for predecessor and successor describes how to compute $\alpha \mapsto \alpha \pm 1$ by a finite propagation of local corrections that restore admissibility after a single digit modification.

The successor recursion is obtained by first performing the formal increment at the least significant position, which corresponds to replacing the rightmost part of the code by adding one unit in the $F_1$-position. This may violate admissibility in two ways: it may create a double occurrence of 1, or it may force a configuration where a 1 is adjacent to another 1 created by a previous correction. The recursion removes these violations by repeated application of the normalization identity

$011 ;\longleftrightarrow; 100,$

which is valid because $F_i + F_{i+1} = F_{i+2}$, so the contribution of two adjacent 1s at positions $i$ and $i+1$ equals the contribution of a single 1 at position $i+2$.

The successor process therefore propagates right-to-left carries in the following sense. After the initial increment, every maximal block of consecutive 1s created by interaction of the added unit with the existing code is replaced by a single 1 shifted two positions left, and the recursion repeats until no adjacent 1s remain. The process terminates because each replacement increases the index of the leftmost affected 1, and indices are bounded by the length of the code.

The predecessor recursion is obtained symmetrically by subtracting one unit at the least significant position. This creates a temporary violation when a 1 is removed from a position whose Fibonacci contribution must be compensated by lower-order terms. The inverse normalization rule

$100 ;\longleftrightarrow; 011$

is applied whenever a digit 1 disappears from a