TAOCP 7.1.3 Exercise 22

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 22. [21] [21] Implement Gosper's hack efficiently with MMIX code, assuming that $x < 2^{64}$, without using division.

Verified: yes
Solve time: 2m20s

The error is the use of arithmetic addition in the final recombination step. In Gosper’s hack the correct operation is a bitwise disjunction, and this must be reflected at the machine level. No property of disjointness is assumed or required.

We reconstruct the derivation from the standard identity.

Let $x < 2^{64}$, $x \neq 0$, and define

$$ u = x ,&, (-x), \qquad v = x + u, \qquad t = v \oplus x. $$

Here $u = 2^k$, where $k$ is the index of the least significant 1-bit of $x$. The value $v = x + u$ clears the trailing block of 1-bits up to position $k$ and sets bit $k$ to 1. The XOR term isolates the changed suffix.

The standard Gosper identity is

$$ \text{next}(x) = v ;;|;; \left(\frac{t}{u} \gg 2\right). $$

Since $u = 2^k$, division by $u$ is a right shift by $k$, hence

$$ \frac{t}{u} \gg 2 = t \gg (k+2). $$

So the target value is

$$ y = v ;|; (t \gg (k+2)). $$

No assumption about disjoint bit patterns is required, because bitwise OR is the correct reconstruction operation by definition of the hack.

Computing the shift without division

We compute $k$ from $u$ by repeated halving:

$$ w = u,\quad k = 0, $$

and while $w \neq 1$,

$$ w \leftarrow w \gg 1,\quad k \leftarrow k + 1. $$

This yields $u = 2^k$ exactly.

Correct MMIX implementation

Assume input in rX, output in rY.

        AND     u, rX, -rX        % u = x & (-x)
        ADD     v, rX, u          % v = x + u
        XOR     t, v, rX          % t = v xor x

        SET     w, u              % w = u
        SET     k, 0              % k = 0

1H      CMP     z, w, 1
        BZ      z, 2F             % if w == 1, done
        SRU     w, w, 1           % w >>= 1
        INCL    k, 1              % k++
        JMP     1B

2H      ADD     s, k, 2           % s = k + 2
        SRU     t, t, s           % t >>= (k + 2)
        OR      rY, v, t          % y = v | t

Correctness

The loop computes $k$ such that $u = 2^k$, hence the final shift produces $t \gg (k+2)$, which equals $(t/u) \gg 2$. The MMIX instruction OR correctly implements the final combination step of Gosper’s hack, independent of any assumptions about bit overlap. The algorithm uses only shifts, logical operations, addition, and comparison, and therefore avoids division entirely.

This yields a correct and complete MMIX implementation of Gosper’s hack. ∎