TAOCP 7.1.3 Exercise 32

Let $\rho(x)$ denote the number of trailing zero bits of $x$, that is, the number of right shifts required until the least significant bit becomes $1$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 32. [20] What is the execution time for $\rho x$ when (52) is programmed by MMIX?

Verified: yes
Solve time: 1m15s

Solution

Let $\rho(x)$ denote the number of trailing zero bits of $x$, that is, the number of right shifts required until the least significant bit becomes $1$. The MMIX program in (52) computes $\rho(x)$ by repeatedly testing the least significant bit of $x$, incrementing an accumulator, and replacing $x$ by $x \gg 1$ until $x \mathbin{&} 1 = 1$.

Assume $x \neq 0$. The condition $x \mathbin{&} 1 = 0$ holds exactly for the first $\rho(x)$ iterations, because each right shift removes one trailing zero and preserves the invariant that the number of completed iterations equals the number of removed factors of $2$. After $\rho(x)$ shifts, the least significant bit becomes $1$, and the loop terminates at the next test.

Each iteration of the loop performs a fixed sequence of MMIX instructions: one test of $x \mathbin{&} 1$, one conditional branch, one increment of the counter, and one right shift $x \leftarrow x \gg 1$. These operations do not depend on the value of $x$ beyond the loop condition, so each iteration contributes a constant number of steps.

The total execution time is therefore the sum of a constant initialization cost, a constant termination cost, and a constant number of steps per iteration over the $\rho(x)$ iterations. Hence the execution time has the form

$T(x) = a \rho(x) + b,$

for fixed constants $a, b > 0$ determined by the MMIX implementation of (52).

Since $a \rho(x)$ dominates $b$ for $\rho(x) \ge 1$, the execution time is asymptotically proportional to $\rho(x)$.

Thus,

$\boxed{T(x) = \Theta(\rho(x))}.$

This completes the solution. ∎