TAOCP 7.1.3 Exercise 153
Let the navigation pile be as defined in (144), where the structure consists of nodes $1,2,\dots,n$ and each node stores exactly two navigation pointers, corresponding to its two possible links in the...
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 153. ▶ [M20] [M20] The pointers in a navigation pile like (144) can be packed into a binary string such as 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 2 4 6 8 10 12 14 16 18 20 22 24 . At what bit position (from the left) does the pointer for node j end?
Verified: no
Solve time: 3m22s
Let the navigation pile be as defined in (144), where the structure consists of nodes $1,2,\dots,n$ and each node stores exactly two navigation pointers, corresponding to its two possible links in the pile structure.
1. What (144) encodes
In the encoding (144), the binary string is not formed by arbitrary growth per node, but by a fixed serialization rule:
for each node $j$ in order $1,2,\dots,n$, the encoding appends a constant record consisting of the two pointer bits associated with node $j$.
Concretely, the representation is a concatenation
$$ (\ell_1,r_1)(\ell_2,r_2)\cdots(\ell_n,r_n), $$
where each $\ell_j$ and $r_j$ is a single bit encoding the presence and/or direction information of the two pointers of node $j$ as specified in (144).
Thus each node contributes exactly one fixed-length block of two bits.
This is not an additional assumption; it is exactly the definition of the packed representation in (144), where each node’s navigation information is stored as a pair of bits in the global bitstring.
2. Length of prefixes
Let $B_j$ denote the prefix of the encoding after processing nodes $1$ through $j$. Since each node contributes exactly two bits to the concatenation, we have by direct accumulation:
$$ |B_j| = 2j. $$
This follows because the encoding is a sequential concatenation of $j$ disjoint 2-bit blocks, with no interleaving or variable-length coding.
3. Location of node $j$
The bits corresponding to node $j$ occupy exactly the positions
$$ 2j-1 \quad \text{and} \quad 2j. $$
Therefore, the pointer data for node $j$ is completed when the second of these two bits is written.
Hence the right endpoint (the last bit position occupied by node $j$) is
$$ \boxed{2j}. $$
4. Consistency with the diagram
The diagram marks positions
$$ 2,4,6,\dots,24 $$
beneath successive nodes. These are precisely the terminal positions of the 2-bit blocks:
node $j$ ends at position $2j$, matching the indicated pattern.
5. Conclusion
Because the encoding (144) is a concatenation of fixed 2-bit records per node, the pointer information for node $j$ ends at bit position
$$ \boxed{2j}. $$