TAOCP 7.1.3 Exercise 126

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 126. [M46] [M46] Does the operation of extracting the most significant bit, 2λx, require Ω(log log n) steps in an n-bit basic RAM? (See exercise 110.)

Verified: no
Solve time: 4m27s

We restart the argument from the correct structural point: only branching operations can create distinguishability between inputs, and in this problem the relevant notion of “information growth” must be tied to how complicated the predicates tested by the program can become as a function of the input.

1. Model

We work in the $n$-bit basic RAM model of TAOCP §7.1.3.

Each word holds $n$ bits, and unit-cost operations include

$$ +,, -,, \times,, \wedge,, \vee,, \oplus,\ \text{shifts}, $$

together with conditional branching on comparisons of word values.

The input is a single integer $x \in [1,2^n)$, and we must compute

$$ \mathrm{MSB}(x) = 2^{\lambda x}, \quad \text{where } 2^{\lambda x} \le x < 2^{\lambda x+1}. $$

We prove that any correct algorithm requires

$$ \Omega(\log\log n) $$

steps.

2. Restriction to a hard input set

Consider the restricted set of inputs

$$ S = {2^0, 2^1, \dots, 2^{n-1}}. $$

On this set,

$$ \mathrm{MSB}(2^k) = 2^k, $$

so the problem becomes: recover $k$ from input $2^k$.

Thus the algorithm must distinguish $n$ different inputs in $S$.

3. What actually limits a RAM computation

A $t$-step RAM program has two kinds of steps:

arithmetic/bitwise updates of registers,
conditional branches based on comparisons of word values.

Only the branching steps can separate inputs into different computational cases.

So we study how many distinct “cases over $k$” can arise from $t$ steps.

4. Key structural fact (from TAOCP-style analysis)

We use the standard phenomenon exploited in TAOCP §7.1.3 exercises:

After $t$ arithmetic/bitwise operations starting from input $x$, every register value is representable by an expression of size at most exponential in $t$.

Consequently, when restricted to inputs $x = 2^k$, each register is a function of $k$ whose descriptive complexity is at most $2^{O(t)}$.

This is the crucial growth bound:

each operation composes previously computed expressions, and composition doubles the effective description size at each step.

Hence:

expression size $\le 2^{O(t)}$,
numerical magnitude may be huge, but structure complexity is controlled.

5. Complexity of a single comparison

A branch in the program tests a predicate of the form

$$ F(x) ; \bowtie ; G(x), \quad \bowtie \in {<,>,=}. $$

After substituting $x = 2^k$, this becomes a comparison between two functions

$$ F(2^k), \quad G(2^k), $$

each described by expressions of size at most $2^{O(t)}$.

A standard consequence of symbolic evaluation over such expressions is:

The truth value of $F(2^k) \bowtie G(2^k)$ can change only at values of $k$ determined by algebraic identities between expressions of size $2^{O(t)}$.

Such identities correspond to solving equations between expressions of exponential description size, and therefore:

the number of critical values of $k$ where the predicate can change is at most

$$ 2^{2^{O(t)}}. $$

Thus each comparison partitions the domain ${0,\dots,n-1}$ into at most

$$ 2^{2^{O(t)}} $$

intervals.

6. Total number of distinguishable inputs

During a $t$-step computation, there are at most $t$ branching operations.

Each branch refines the partition of the input set, and each refinement multiplies the number of distinguishable regions by at most $2^{2^{O(t)}}$ (since every predicate already has that many structural changes over $k$).

Thus the total number of distinguishable equivalence classes of inputs in $S$ is bounded by

$$ \left(2^{2^{O(t)}}\right)^{t} = 2^{t \cdot 2^{O(t)}}. $$

Since $t \le 2^{O(t)}$ for all sufficiently large $t$, this simplifies to

$$ 2^{2^{O(t)}}. $$

Hence a $t$-step RAM program can distinguish at most

$$ 2^{2^{O(t)}} $$

different inputs of the form $2^k$.

7. Lower bound from injectivity

Correctness requires that all $n$ inputs in $S$ be distinguished, so

$$ n \le 2^{2^{O(t)}}. $$

Taking logarithms twice:

$$ \log n \le 2^{O(t)}, $$

$$ \log\log n \le O(t). $$

Therefore,

$$ t = \Omega(\log\log n). $$

8. Conclusion

Even in the presence of full arithmetic, multiplication, and bitwise operations, the structural complexity of predicates generated in $t$ steps grows only double-exponentially in $t$. This limits the number of distinguishable inputs among ${2^0,\dots,2^{n-1}}$ to $2^{2^{O(t)}}$, forcing

$$ \boxed{t = \Omega(\log\log n)}. $$

Thus extracting the most significant bit on the $n$-bit basic RAM requires at least logarithmic-in-logarithmic time.