TAOCP 7.1.3 Exercise 31
The proposed procedure maintains $\rho$ as the number of trailing zero bits of $x$ by repeatedly replacing $x \leftarrow x \gg 1$ while $x \mathbin{&} 1 = 0$.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 31. ▶ [20] A mathematician named Dr. L. I. Presume decided to calculate the ruler function with a simple loop as follows: "Set $\rho \leftarrow 0$; then while $x \mathbin{&} 1 = 0$, set $\rho \leftarrow \rho + 1$ and $x \leftarrow x \gg 1$." He reasoned that, when $x$ is a random integer, the average number of right shifts is the average value of $\rho$, which is 1; and the standard deviation is only $\sqrt{2}$, so the loop almost always terminates quickly. Criticize his decision.
Verified: yes
Solve time: 1m11s
Solution
The proposed procedure maintains $\rho$ as the number of trailing zero bits of $x$ by repeatedly replacing $x \leftarrow x \gg 1$ while $x \mathbin{&} 1 = 0$. The stopping condition depends only on the least significant bit of the current value of $x$.
If $x = 0$, then $x \mathbin{&} 1 = 0$ holds and also $x \gg 1 = 0$, so the state $(x,\rho) = (0,\rho)$ is invariant under the loop body. The loop therefore never terminates. This single input already contradicts the claim that the procedure “almost always terminates quickly,” since correctness and termination cannot be probabilistic properties of a deterministic algorithm.
For nonzero $x$, the loop performs exactly $\rho(x)$ iterations, where $\rho(x)$ is the number of trailing zero bits of $x$. If $x$ is modeled as a uniformly random integer with independent bits, then
$\Pr(\rho(x)=k)=2^{-(k+1)}, \qquad k \ge 0,$
so the expected value is $E[\rho]=1$ and the variance is $2$. This distribution has an exponential tail, since
$\Pr(\rho(x)\ge k)=2^{-k}.$
Thus, although large values of $\rho(x)$ are unlikely, they occur with nonzero probability for every $k$, and there is no deterministic bound on the running time over all inputs.
The conclusion that the algorithm is efficient because the mean and standard deviation are small does not control worst-case behavior. A single input with large trailing zero run, or the input $x=0$, forces arbitrarily many iterations or nontermination. Any analysis that replaces worst-case guarantees by probabilistic intuition about “typical” integers fails to justify the correctness or robustness of the method as an algorithmic primitive.
This completes the criticism. ∎