TAOCP 7.1.3 Exercise 38
The error in the previous solution is that it reconstructs a generic “parallel prefix” algorithm and then assigns instruction counts without grounding them in the actual MMIX operations used in proced...
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 38. [17] How long does the leftmost-bit-extraction procedure (57) take when implemented on MMIX?
Verified: no
Solve time: 4m15s
The error in the previous solution is that it reconstructs a generic “parallel prefix” algorithm and then assigns instruction counts without grounding them in the actual MMIX operations used in procedure (57). The corrected argument must instead follow the structure of Knuth’s implementation and then count MMIX instructions directly from that structure.
Structure of procedure (57)
Procedure (57) computes the leftmost 1-bit of a nonnegative word $x$ by first expanding the leading 1-bit into a contiguous block of 1s, and then isolating its highest position.
The standard formulation used in TAOCP is:
- Propagation step (prefix filling):
$$ y \leftarrow x $$
$$ y \leftarrow y ; \mathbin{\mathrm{or}} ; (y \gg 1) $$
$$ y \leftarrow y ; \mathbin{\mathrm{or}} ; (y \gg 2) $$
$$ y \leftarrow y ; \mathbin{\mathrm{or}} ; (y \gg 4) $$
$$ y \leftarrow y ; \mathbin{\mathrm{or}} ; (y \gg 8) $$
$$ y \leftarrow y ; \mathbin{\mathrm{or}} ; (y \gg 16) $$
$$ y \leftarrow y ; \mathbin{\mathrm{or}} ; (y \gg 32) $$
After these 6 stages (for 64-bit words), all bits below the highest 1-bit of $x$ are set to 1.
- Isolation step:
$$ x^{\ast} = y ;&; \neg (y \gg 1) $$
This leaves only the most significant 1-bit.
MMIX implementation details
We now translate each operation into MMIX instructions.
1. Shift and OR stages
On MMIX:
- Right shift by constant $k$: one instruction (
SRU) - Bitwise OR: one instruction (
OR)
Each propagation stage therefore uses exactly:
$$ 1 \text{ SRU} + 1 \text{ OR} = 2 \text{ instructions}. $$
There are 6 stages (for shifts by $1,2,4,8,16,32$), so the total cost of the propagation phase is:
$$ 6 \times 2 = 12 \text{ instructions}. $$
No additional instructions are required for moves if we reuse registers destructively, as is standard in MMIX coding style.
2. Final isolation step
We compute:
$$ t \leftarrow y \gg 1 $$
This requires:
- 1 instruction (
SRU)
Then compute:
$$ y \leftarrow y ;&; \neg t $$
MMIX provides the instruction ANDN, which computes:
$$ \mathrm{ANDN}(a,b) = a ;&; \neg b $$
Thus:
- 1 instruction (
ANDN)
No explicit NOT instruction is needed, and no constant $-1$ needs to be materialized.
Hence the isolation step costs:
$$ 2 \text{ instructions}. $$
Total running time
Adding both phases:
- Propagation: $12$ instructions
- Final extraction: $2$ instructions
$$ 12 + 2 = 14 \text{ MMIX instructions}. $$
Conclusion
Procedure (57) executes a fixed sequence of MMIX instructions independent of the input word. Its cost on a 64-bit MMIX is exactly:
$$ \boxed{14 \text{ instructions}} $$
Therefore the running time is $\Theta(1)$, with a precise instruction count of 14 for the standard MMIX implementation of the leftmost-bit extraction routine.