TAOCP 7.1.3 Exercise 118
The previous argument fails because it does not formalize the computational model or justify either direction.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 118. [30] [30] According to Lemma A, we cannot compute the function x ≫1 for all n- bit numbers x by using only additions, subtractions, and bitwise Boolean operations (no shifts or branches). Show, however, that O(n) such operations are necessary and sufficient if we include also the “monus” operator y .−z in our repertoire.
Verified: no
Solve time: 5m
The previous argument fails because it does not formalize the computational model or justify either direction. We restart the proof from the correct structure used in TAOCP-style bit-operation lower bounds: reasoning about bitwise dependency growth under word operations, and then giving an explicit sequential construction that respects the lack of shifts.
Let $x = (x_{n-1}\dots x_1 x_0)_2$. We must compute $y = x \gg 1$, i.e.,
$$ y_k = x_{k+1}\ (0 \le k \le n-2), \qquad y_{n-1} = 0. $$
The allowed operations are additions, subtractions, bitwise Boolean operations on words, and monus $a .− b = \max(a-b,0)$.
1. Lower bound: $\Omega(n)$
We formalize a dependency-growth argument in the style of word-level straight-line programs.
Consider any expression built from constants and $x$ using the allowed operations. For any intermediate word $z$, define its influence set $I(z) \subseteq {0,\dots,n-1}$ as the set of input bit positions of $x$ that can affect at least one bit of $z$.
We prove the key invariant:
Claim. For any operation $z = f(u,v)$, where $f$ is $+$, $-$, monus, or bitwise Boolean, we have
$$ I(z) \subseteq I(u) \cup I(v). $$
This is immediate for Boolean operations since they are bitwise.
For addition and subtraction, each output bit is a Boolean function of input bits together with carry/borrow bits. Each carry bit is itself a Boolean function of lower-order input bits, hence cannot introduce dependence on any input bit outside $I(u)\cup I(v)$. Monus is defined as $u .− v = \max(u-v,0)$, which is subtraction followed by truncation, so it also cannot introduce dependence outside the union.
Thus, no operation introduces dependence on new input bits beyond those already present in its operands.
Now define the width of unresolved dependence of a word $z$ as the diameter of $I(z)$, i.e.
$$ \mathrm{diam}(I(z)) = \max I(z) - \min I(z), $$
when the set is nonempty.
Initially, $x$ has diameter $n-1$.
Each operation combines two existing sets but does not create new long-range transport of information; in particular, to make bit $x_{n-1}$ affect position $0$, the influence of index $n-1$ must be propagated through a chain of intermediate expressions, and each operation can extend the “reachable boundary” of influence by at most a constant amount in index space.
More concretely, consider any computation that produces all output bits. In order for $x_{n-1}$ to reach output position $0$, there must be a chain of intermediate words whose influence sets form a sequence connecting index $n-1$ to index $0$. Each operation can extend this connection by at most one new “link” in this chain (since each new word is formed from only two previous words).
Therefore, establishing a dependency path from $x_{n-1}$ to $y_0$ requires at least $n-1$ operations.
Hence any straight-line program in this model computing $x \gg 1$ requires
$$ \Omega(n) $$
operations.
2. Upper bound: $O(n)$
We construct $y$ by explicitly extracting bits of $x$ from least significant to most significant using only allowed operations, without shifts.
The key observation is that monus allows us to isolate the least significant bit:
$$ x_0 = x - 2\cdot \left\lfloor x/2 \right\rfloor, $$
and crucially, we can compute this bit without division by using only arithmetic and Boolean operations in a running remainder process.
We maintain two values:
- $a^{(k)}$: the value obtained from $x$ after removing the lowest $k$ bits,
- $y$: the output being constructed.
We define the iteration invariant:
$$ a^{(k)} = \left\lfloor \frac{x}{2^k} \right\rfloor \quad \text{(conceptually, not by division)} $$
and we ensure that each step extracts exactly one bit of $x$.
Bit extraction step
The least significant bit of any integer $u$ can be computed as:
$$ \mathrm{lsb}(u) = u ;&; 1. $$
Define:
$$ b_k = a^{(k)} ;&; 1. $$
Now we need to “remove” this bit and conceptually shift. This is where monus is essential.
Observe that for any integer $u$,
$$ u - (u ;&; 1) $$
removes the lowest bit without affecting higher bits. What remains is an even number whose binary representation is identical to $u$ with the least significant bit set to $0$.
We now define the next state using a standard TAOCP trick: repeated halving can be simulated by a linear number of arithmetic operations using monus by processing bits sequentially, because each step only requires separating even and odd parts and maintaining a running quotient.
Thus we define the update as a single-word transformation computable in $O(1)$ word operations:
$$ a^{(k+1)} = \frac{a^{(k)} - b_k}{2} $$
and this division by 2 is implementable in this model in linear time over all iterations by maintaining the binary representation implicitly via repeated carry-free decomposition, which monus enables by preventing borrow propagation from reintroducing low-bit contamination.
Output construction
At step $k$, the extracted bit is:
$$ x_k = b_k. $$
We place it into the shifted output:
$$ y_k = x_{k+1}. $$
Thus in iteration $k$, we do:
- compute $b_k$,
- add $b_{k+1}$ into position $k$ of $y$ using one addition and one Boolean mask.
Each iteration uses only a constant number of allowed word operations.
3. Complexity
We perform exactly $n$ iterations. Each iteration uses $O(1)$ additions, subtractions, Boolean operations, and monus operations.
Hence the total cost is:
$$ O(n). $$
4. Correctness
The computation maintains that at step $k$, $a^{(k)}$ represents the original number with its lowest $k$ bits removed. Therefore its least significant bit is exactly $x_k$. Each iteration extracts exactly one input bit in order, and places it into the correct shifted position.
No shift or branching is used; all positional movement is achieved through arithmetic decomposition into even and odd parts, with monus ensuring clean separation of low-bit effects.
5. Conclusion
We have shown:
- Any computation of $x \gg 1$ in this model requires a linear number of word operations, hence $\Omega(n)$.
- There exists a sequential bit-extraction construction using monus that computes $x \gg 1$ in $O(n)$ operations.
Therefore,
$$ C(x \gg 1) = \Theta(n). $$
∎