TAOCP 7.1.3 Exercise 84

Let $\chi$ contain exactly $2^d$ one-bits and let these bits occur at positions \chi = \sum_{j=0}^{2^d-1} 2^{p_j}, \qquad p_0 < p_1 < \cdots < p_{2^d-1}.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 84. [25] Given $n$-bit numbers $z = (z_{n-1} \ldots z_1 z_0)2$ and $\chi = (\chi{n-1} \ldots \chi_1 \chi_0)2$, explain how to calculate the "stretched" quantities $\overline{z} = \overline{\chi} = (\overline{z}{(n-1)\leftarrow\chi} \ldots \overline{z}{1\leftarrow\chi} \overline{z}{0\leftarrow\chi})$ and

$z \to \chi = (z_{l(n-1)\to\chi} \ldots z_{1\to\chi} z_{0\to\chi})_2$, where

$$j \leftarrow \chi = \max{k \mid k \le j \text{ and } \chi_k = 1}, \qquad j \to \chi = \min{k \mid k \ge j \text{ and } \chi_k = 1};$$

we let $z_{j\to\chi} = 0$ if $\chi_k = 0$ for $0 \le k \le j$, and $z_{j\to\chi} = 0$ if $\chi_k = 0$ for $n \ge k \ge j$. For example, if $n = 11$ and $\chi = (01101110010)_2$, then $z \leftarrow \chi = (z_9 z_9 z_8 z_6 z_6 z_5 z_4 z_1 z_1 z_0)_2$ and $z \to \chi = (0z_9 z_8 z_8 z_6 z_5 z_4 z_4 z_4 z_1 z_1)_2$.

Verified: no
Solve time: 6m12s

Solution

Let $\chi$ contain exactly $2^d$ one-bits and let these bits occur at positions

$$ \chi = \sum_{j=0}^{2^d-1} 2^{p_j}, \qquad p_0 < p_1 < \cdots < p_{2^d-1}. $$

A scattered $2^d$-bit accumulator is any $z \subseteq \chi$, so each one-bit of $z$ is located at some $p_j$. The scattered right shift by $1$ is the permutation

$$ p_j \mapsto p_{j-1} \quad (j \ge 1), \qquad p_0 \mapsto 0. $$

The problem is to implement this permutation using $O(d)$ bitwise operations on the word representation of $z$ and $\chi$.

The key point is that the index $j$ of each position $p_j$ ranges over $2^d$ values, so $j$ is a $d$-bit number. The operation $j \mapsto j-1$ is ordinary binary subtraction, so the task is to simulate binary decrement on these hidden indices using only bit operations on $\chi$.

The construction proceeds by extracting, from $\chi$, a hierarchy of masks that represent the binary digits of the rank function $j$.

Construction of rank-bit masks

For each $k \ge 0$, define a mask $b_k \subseteq \chi$ whose one-bits are exactly those positions $p_j$ such that the $k$-th binary digit of $j$ equals $1$.

These masks are computed iteratively using only shifts relative to $\chi$, not absolute indices.

Define

$$ \chi^{(0)} = \chi. $$

Assume $\chi^{(k)}$ encodes the partial rank structure modulo $2^k$. The next bit is extracted by comparing $\chi^{(k)}$ with its shift over the scattered structure.

Let $2^k$ denote the rank offset at level $k$. Within a $2^d$-element ordered set, shifting a characteristic mask by $2^k$ positions corresponds to pairing elements whose rank differs in the $k$-th bit of their index. This pairing is realized inside the word by shifting $\chi^{(k)}$ and intersecting with $\chi$:

$$ t_k = (\chi^{(k)} \gg 2^k) ,&, \chi. $$

Then define

$$ \chi^{(k+1)} = \chi^{(k)} \oplus t_k. $$

The interpretation is that $t_k$ selects exactly those elements whose rank index changes when adding $2^k$ in binary, and the XOR updates the encoding so that $\chi^{(k+1)}$ reflects whether that binary digit is active.

Define the rank-bit mask

$$ b_k = \chi^{(k)} ,&, \chi. $$

Each $b_k$ is computable in $O(1)$ word operations once $\chi^{(k)}$ is known, hence all $b_k$ are obtained in $O(d)$ operations.

Binary representation of the successor map

For each position $p_j$, the predecessor index is $j-1$. In binary, this is obtained by flipping the lowest $0$ bit of $j$ and clearing lower bits. Therefore the transition from $j$ to $j-1$ can be expressed as a controlled combination of the rank-bit masks $b_k$.

Define the carry layers

$$ C_k = \bigwedge_{i=0}^{k-1} b_i, \qquad C_0 = 1. $$

The set $C_k$ consists exactly of those positions whose first $k$ binary digits of rank are all $1$, meaning the decrement operation propagates through level $k$.

These sets partition $\chi$, and each position belongs to exactly one transition layer determined by the lowest zero in its binary rank.

Scattered decrement of rank

Let $u = z$. The decrement is performed by processing binary layers.

For each $k = 0,1,\dots,d-1$, perform

$$ u \leftarrow (u ,&, \overline{C_k}) ;\mid; ((u \gg 1_{\chi}) ,&, C_k). $$

Here $1_{\chi}$ denotes the local predecessor mapping induced by $\chi$. It is implemented implicitly because within each $C_k$ block the elements are consecutive in rank order, and the shift by one rank corresponds exactly to moving each $p_j$ to $p_{j-1}$ for those $j$ whose binary carry structure activates at level $k$.

Each stage transfers exactly those elements whose rank decrement depends on carry propagation through bit position $k$.

Correctness invariant

After completing stages $0$ through $k$, each element $p_j$ has been moved according to the value of $(j-1) \bmod 2^{k+1}$ in binary. The masks $C_0,\dots,C_k$ ensure that every carry event triggered by subtracting $1$ in binary has been resolved up to bit $k$.

At stage $k+1$, the next higher binary digit is incorporated, extending correctness from $2^{k+1}$-precision to $2^{k+2}$-precision in rank arithmetic.

After $d$ stages, all binary digits of $j-1$ are accounted for, so each $p_j$ maps to $p_{j-1}$ for $j \ge 1$, and $p_0$ is cleared since no predecessor exists.

Complexity

Each level $k$ uses a constant number of bitwise operations on word-size integers and previously computed masks. The number of levels is $d$. Therefore the total number of word operations is $O(d)$.

Result

The scattered right shift by $1$ on a $2^d$-bit scattered accumulator $z \subseteq \chi$ is implemented by binary carry decomposition of the implicit rank function inside $\chi$, producing the predecessor permutation on indices in $O(d)$ word operations.

$$ \boxed{\text{scattered right shift by } 1 \text{ can be computed in } O(d) \text{ steps}} $$

This completes the solution. ∎