TAOCP 7.1.3 Exercise 36

Let $x = (x_{63}\ldots x_0)_2$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 36. [20] Given $x = (x_{63} \ldots x_1 x_0)2$, suggest efficient ways to calculate the quantities i) $x^R = (x{63}^{\oplus} \ldots x_1^{\oplus} x_0^{\oplus})2$, where $x_k^{\oplus} = x_k \oplus \cdots \oplus x_1 \oplus x_0$ for $0 \le k < 64$; ii) $x^L = (x{63}^{\oplus} \ldots x_1^{\oplus} x_0^{\oplus})_2$, where $x_k^L = x_k \wedge \cdots \wedge x_1 \wedge x_0$ for $0 \le k < 64$.

Verified: yes
Solve time: 1m10s

Solution

Let $x = (x_{63}\ldots x_0)_2$. All operations are performed on 64-bit words with bitwise extension as in (1)–(3).

i) Computation of $x^R$

Define $x^R = (y_{63}\ldots y_0)_2$ with

$y_k = x_k \oplus x_{k-1} \oplus \cdots \oplus x_0.$

Let $y^{(0)} = x$. For $t = 0,1,2,3,4,5$, define

$y^{(t+1)} = y^{(t)} \oplus (y^{(t)} \ll 2^t).$

For each bit position $k$, the effect of the update is

$y^{(t+1)}_k = y^{(t)}k \oplus y^{(t)}{k-2^t}.$

If $k < 2^t$, the shifted term contributes $0$, so $y^{(t+1)}k = y^{(t)}k$. If $k \ge 2^t$, the recurrence accumulates XOR over an interval of length $2^{t+1}$ formed by merging two blocks of length $2^t$. After stage $t$, each $y^{(t)}k$ equals the XOR of the bits $x{k} \oplus x{k-1} \oplus \cdots \oplus x{k-2^t+1}$ whenever the index range is defined, and the induction extends this window doubling at each stage.

After $t = 5$, since $2^6 = 64$, each position $k$ has incorporated all lower bits $0,\ldots,k$, so $y^{(6)} = x^R$. Thus

$x^R = x \oplus (x \ll 1) \oplus (x \ll 2) \oplus (x \ll 4) \oplus (x \ll 8) \oplus (x \ll 16) \oplus (x \ll 32),$

with the successive staged formulation above implementing the same computation in a structured doubling process.

$$ \boxed{ x^R = \text{prefix XOR of } x \text{ computed by successive shifts } 1,2,4,8,16,32 } $$

ii) Computation of $x^L$

Define $x^L = (z_{63}\ldots z_0)_2$ with

$z_k = x_k \wedge x_{k-1} \wedge \cdots \wedge x_0.$

Let $\bar{x}$ denote bitwise complementation as in (14), and define

$u_k = \bar{x}k \vee \bar{x}{k-1} \vee \cdots \vee \bar{x}_0.$

Then by De Morgan’s law in (14),

$z_k = \overline{u_k},$

so $x^L$ is obtained by computing a prefix OR on $\bar{x}$ and complementing the result.

Construct $u^{(0)} = \bar{x}$. For $t = 0,1,2,3,4,5$, define

$u^{(t+1)} = u^{(t)} \mid (u^{(t)} \ll 2^t).$

For each bit position $k$, this update satisfies

$u^{(t+1)}_k = u^{(t)}k \vee u^{(t)}{k-2^t},$

so each stage merges adjacent blocks of size $2^t$ into blocks of size $2^{t+1}$ under bitwise OR. After $t=5$, every position $k$ contains the OR of all bits $\bar{x}_0,\ldots,\bar{x}_k$, hence

$u^{(6)}_k = \bar{x}_0 \vee \cdots \vee \bar{x}_k.$

Complementing bitwise yields

$z_k = \overline{u^{(6)}_k} = x_k \wedge \cdots \wedge x_0,$

so $x^L = \overline{u^{(6)}}$.

Thus

$x^L = \overline{\bar{x} \mid (\bar{x} \ll 1) \mid (\bar{x} \ll 2) \mid (\bar{x} \ll 4) \mid (\bar{x} \ll 8) \mid (\bar{x} \ll 16) \mid (\bar{x} \ll 32)}.$

$$ \boxed{ x^L = \text{bitwise complement of prefix OR of } \bar{x} } $$

This completes the construction. ∎