TAOCP 7.1.3 Exercise 39

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 39. ▶ [20] Formula (43) shows how to remove the rightmost run of 1 bits from a given number $x$. How would you remove the leftmost run of 1 bits?

Verified: no
Solve time: 1m11s

Solution

Let $x = (x_{w-1}\ldots x_1 x_0)_2$ be a word of fixed width $w$. Define the bit-reversal operation $R$ by

$$ R(x) = (x_0 x_1 \ldots x_{w-1})_2. $$

A rightmost run of 1s in $y$ is a maximal block of consecutive 1-bits ending at bit position $0$ or immediately preceded by a 0-bit. Formula (43) removes this run by

$$ y \leftarrow y ,&, (y+1), $$

since adding $1$ flips the trailing block of 1s to 0s and introduces a 1 at the first 0-position above it, and the bitwise AND removes exactly that introduced structure while clearing the trailing run.

To remove the leftmost run of 1s of $x$, apply this operation in reversed bit order. The leftmost run of $1$-bits of $x$ becomes the rightmost run of $1$-bits of $R(x)$, since reversal exchanges most significant and least significant positions and preserves adjacency of bits.

Apply formula (43) to $R(x)$:

$$ R(x) \leftarrow R(x) ,&, (R(x)+1). $$

Let the resulting value be $y$. Reversing back yields the desired number:

$$ x' = R(y) = R\bigl(R(x) ,&, (R(x)+1)\bigr). $$

This transformation removes exactly the maximal block of consecutive 1-bits starting at the most significant 1-bit of $x$, since reversal maps that block bijectively to the trailing run of 1s of $R(x)$, and the operation $z \mapsto z ,&, (z+1)$ removes precisely that trailing run while leaving all other bits unchanged. This completes the construction.

$$ \boxed{x' = R\bigl(R(x) ,&, (R(x)+1)\bigr)} $$