TAOCP 7.1.3 Exercise 43

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 43. ▶ [20] How sparse should $x$ be, to make (64) faster than (62) on MMIX?

Verified: no
Solve time: 2m42s

Solution

Let $w$ denote the word length of MMIX. Let $\nu x$ denote the number of 1-bits of $x$, as in (definition preceding Exercise 41). The two methods referred to in the exercise compute $\nu x$ by different loop structures.

Method (62) scans all bit positions of a word. Each iteration inspects one fixed bit position and performs a constant amount of Boolean work using shifts and masks from (19)–(21). Since exactly $w$ bit positions exist, the loop executes exactly $w$ iterations, so its cost is proportional to $w$.

Method (64) removes one 1-bit per iteration using the identity $x \leftarrow x ,&, (x-1)$ from Section 7.1.3 or an equivalent rightmost-1-bit extraction derived from (9)–(11). Each iteration strictly decreases $\nu x$ by $1$, since the least significant 1-bit of $x$ is cleared and no other 1-bit changes. Therefore the loop executes exactly $\nu x$ iterations until termination. Each iteration performs a constant number of MMIX operations, so the total cost is proportional to $\nu x$.

The comparison reduces to comparing $\Theta(w)$ and $\Theta(\nu x)$. Method (64) is faster exactly when

$$ \nu x < w $$

up to constant-factor overheads of the respective implementations. Since always $\nu x \le w$, equality occurs when all bits of the word are 1, and strict inequality occurs precisely when at least one bit position contains 0.

Let $s = \nu x$ be the sparsity of $x$. The crossover point occurs when $s$ is of the same order as $w$, since then both methods perform $\Theta(w)$ work. If $s = o(w)$, then method (64) performs strictly fewer primitive operations asymptotically than method (62), since its runtime is $\Theta(s)$ versus $\Theta(w)$. If $s = \Theta(w)$, the methods have the same asymptotic cost. If $s = \omega(w)$, the bound $\nu x \le w$ prevents this case, so no faster regime arises.

Thus the threshold for improvement is determined entirely by sparsity of the bit representation: method (64) is asymptotically faster precisely when $x$ has significantly fewer 1-bits than the word size, that is, when $\nu x = o(w)$.

$$ \boxed{\text{Method (64) is faster iff } \nu x = o(w)} $$