TAOCP 7.1.3 Exercise 29

Let $\mu_k$ denote Pratt’s magic mask from (47).

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 29. [20] (V. R. Pratt.) Express the magic mask $\mu_k$ of (47) in terms of $\mu_{k+1}$.

Verified: no
Solve time: 3m40s

Let $\mu_k$ denote Pratt’s magic mask from (47). We use only its defining structural property: $\mu_k$ is a $2^{k+1}$-periodic binary sequence, and $\mu_{k+1}$ is obtained by refining this structure at the next level of period doubling.

Step 1: Period structure

Let the period of $\mu_k$ be $2^{k+1}$. Then $\mu_{k+1}$ has period $2^{k+2}$. Hence one period of $\mu_{k+1}$ consists of two blocks of length $2^{k+1}$:

$$ \mu_{k+1} = (A , B), \quad |A| = |B| = 2^{k+1}. $$

The construction in (47) is a refinement step in which the two blocks correspond to two aligned copies of the coarser structure. Thus each position in the coarser mask $\mu_k$ is determined by whether the corresponding position is marked in either half of the finer mask $\mu_{k+1}$.

Step 2: Coarsening relation

For $0 \le i < 2^{k+1}$, define

$$ \mu_k[i] = \mu_{k+1}[i] ;\lor; \mu_{k+1}[i + 2^{k+1}], $$

with indices taken modulo $2^{k+2}$ in $\mu_{k+1}$.

This expresses that the $k$-level mask is obtained by folding the $(k+1)$-level mask over a shift of one block length.

Step 3: Bitwise form

Let $\mu_k$ and $\mu_{k+1}$ be viewed as infinite bit masks. The above pointwise relation becomes a bitwise OR of two aligned copies:

$$ \mu_k = \mu_{k+1} ;\lor; (\mu_{k+1} \ll 2^{k+1}). $$

Step 4: Consistency check

This relation is consistent with the periodic structure:

  • The shift is exactly one half-period of $\mu_{k+1}$, namely $2^{k+1}$, so alignment is preserved.
  • The OR operation performs the only natural coarsening operation compatible with the refinement description in (47): a position is marked at level $k$ if it is marked in either corresponding subblock at level $k+1$.
  • This correctly expresses $\mu_k$ as a projection (folding) of $\mu_{k+1}$, rather than an expansion.

Final result

$$ \boxed{\mu_k = \mu_{k+1} ,\lor, (\mu_{k+1} \ll 2^{k+1})}. $$

This corrects both the shift amount and the direction of construction: $\mu_k$ is obtained by coarsening $\mu_{k+1}$, not by expanding it.