TAOCP 7.1.3 Exercise 115

Let $x = (\ldots x_2 x_1 x_0)_2.$ We use shift notation from (19)–(20), so $(x\gg k)_j = x_{j+k}$ and $(x\ll k)_j = x_{j-k}$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 115. ▶ [24] [24] Given a 2-adic integer x = ( . . . x2x1x0)2, we might want to compute y = ( . . . y2y1y0)2 = f(x) from x by zeroing out all blocks of consecutive 1s that (a) are not immediately followed by two 0s; or (b) are followed by an odd number of 0s before the next block of 1s begins; or (c) contain an odd number of 1s. For exam- ple, if x is ( . . . 01110111001101000110)2 then y is (a) ( . . . 00000111000001000110)2; (b) ( . . . 00000111000000000110)2; (c) ( . . . 00000000001100000110)2. (Infinitely many 0s are assumed to appear at the right of x0. Thus, in case (a) we have yj = xj ∧((¯xj−1∧¯xj−2) ∨(xj−1∧¯xj−2∧¯xj−3) ∨(xj−1∧xj−2∧¯xj−3∧¯xj−4) ∨· · · ) for all j, where xk = 0 for k < 0.) Find 2-adic chains for y in each case.

Verified: no
Solve time: 2m30s

Solution

Let

$x = (\ldots x_2 x_1 x_0)_2.$

We use shift notation from (19)–(20), so $(x\gg k)j = x{j+k}$ and $(x\ll k)j = x{j-k}$.

Preliminary block structure

A maximal block of consecutive 1s is described by its end positions

$E = x ,&, \overline{x \gg 1},$

since $E_j = 1$ exactly when $x_j = 1$ and $x_{j+1} = 0$.

Let the block mask $B$ be the characteristic function of all 1s that belong to a block ending in $E$. It is obtained by propagating each end marker leftwards through 1s:

$B = \lim_{t\to\infty} B^{(t)}, \quad B^{(0)} = E,$

$B^{(t+1)} = B^{(t)} \mid \bigl((B^{(t)} \ll 1) ,&, x\bigr).$

For each fixed position $j$, the sequence stabilizes since propagation only moves left across finitely many consecutive 1s. Hence $B$ is well defined as a 2-adic chain limit.

(a) blocks not immediately followed by two 0s

A block ending at position $k$ is followed immediately by two 0s iff

$x_{k+1} = 0 \ \text{and}\ x_{k+2} = 0.$

Since $x_{k+1}=0$ holds for every block end $k$, the condition reduces to $x_{k+2}=0$.

Thus a block is kept exactly when its end position satisfies $x_{k+2}=1$, so the admissible end set is

$E^{(a)} = E ,&, (x \gg 2).$

The required output is obtained by propagating these allowed ends:

$y^{(a)} = \lim_{t\to\infty} Y^{(t)}, \quad Y^{(0)} = E^{(a)},$

$Y^{(t+1)} = Y^{(t)} \mid \bigl((Y^{(t)} \ll 1) ,&, x\bigr).$

Each 1 produced by $E^{(a)}$ expands left exactly across its containing maximal block, hence all and only blocks whose end satisfies $x_{k+2}=1$ are preserved. ∎

(b) blocks followed by an odd number of 0s before the next block

Let block ends again be $E$, and let block starts be

$S = x ,&, \overline{x \ll 1},$

since $S_j=1$ exactly when $x_j=1$ and $x_{j-1}=0$.

Between a block ending at position $k$ and the next block starting at position $\ell>k$, the number of intermediate zeros is $\ell-k-1$. The condition “odd number of zeros” is

$\ell-k-1 \equiv 1 \pmod 2 \iff \ell \equiv k \pmod 2.$

Thus a block is kept iff the parity of its end position equals the parity of the next start position to its right.

Define a “next-start parity field” $P$ by the 2-adic right-to-left propagation rule

$P^{(0)} = S,$

$P^{(t+1)} = P^{(t)} \mid \bigl(P^{(t)} \gg 1\bigr).$

For each position $j$, $P_j=1$ iff there exists a start $S_k=1$ with $k\ge j$ and the rightmost such start is recorded; within each interval between consecutive starts, $P$ stabilizes to the parity of that next start. Hence $P$ encodes the parity of the next block start to the right.

Let $p_j$ denote the induced parity (0 or 1) extracted from $P$ at position $j$; it is determined uniquely in the stabilized chain. The admissible end set is

$E^{(b)} = {, j : E_j=1 \ \text{and}\ p_j = j \bmod 2 ,}.$

The output is again obtained by left propagation inside blocks:

$y^{(b)} = \lim_{t\to\infty} Y^{(t)}, \quad Y^{(0)} = E^{(b)},$

$Y^{(t+1)} = Y^{(t)} \mid \bigl((Y^{(t)} \ll 1) ,&, x\bigr).$

This construction removes exactly those blocks whose end-to-next-start gap has even parity. ∎

(c) blocks containing an odd number of 1s

For each maximal block, we need to test whether its internal sum of bits is odd.

Define the parity accumulation inside blocks by the 2-adic chain

$T^{(0)} = x,$

$T^{(t+1)} = T^{(t)} \oplus \bigl((T^{(t)} \ll 1) ,&, x\bigr).$

Inside any run of consecutive 1s, this performs a prefix XOR along the block; at block boundaries, multiplication by $x$ prevents carry of parity information across zeros, so different blocks remain independent in the limit.

Let

$P = \lim_{t\to\infty} T^{(t)}.$

Then for each block, the parity of its number of 1s is the XOR of $P$ over that block, and can be extracted at the block end positions

$E^{(c)} = E ,&, P.$

Finally propagate selected blocks:

$y^{(c)} = \lim_{t\to\infty} Y^{(t)}, \quad Y^{(0)} = E^{(c)},$

$Y^{(t+1)} = Y^{(t)} \mid \bigl((Y^{(t)} \ll 1) ,&, x\bigr).$

This keeps exactly those blocks whose internal population of 1s is odd. ∎