TAOCP 7.1.3 Exercise 20

Let $x>0$ and define $u = x \,\&\, (-x), \qquad v = x + u.$ Let $k$ be the unique index such that $u = 2^k$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 20. ▶ [21] [21] (Gosper's hack.) The following seven operations produce a useful function $y$ of $x$, when $x$ is a positive integer. Explain what this function is and why it is useful.

$$u \leftarrow x ,&, -x; \qquad v \leftarrow x + u; \qquad y \leftarrow v + (((v \oplus x)/u) \gg 2).$$

Verified: yes
Solve time: 2m29s

Solution

Let $x>0$ and define

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

Let $k$ be the unique index such that $u = 2^k$. Then the $k$-th bit of $x$ equals $1$ and all bits below $k$ equal $0$.

Let $t \ge 1$ be the number of consecutive $1$-bits of $x$ starting at position $k$, so that the bits of $x$ on positions $k,k+1,\dots,k+t-1$ are all $1$, and the bit at position $k+t$ equals $0$.

Write $x$ in the form

$x = A ,0, \underbrace{1\cdots 1}_{t\ \text{bits}}, 0\cdots 0,$

where the block of $t$ ones begins at position $k$ and $A$ denotes higher bits.

Since $u=2^k$, adding $u$ to $x$ produces a carry through exactly this block of $t$ ones. Hence

$v = x + u = (A+1),0,\underbrace{0\cdots 0}_{t\ \text{bits}},0\cdots 0.$

Thus $x$ and $v$ differ exactly on the bit interval $[k,k+t]$. Therefore

$v \oplus x = \bigl(2^{t+1}-1\bigr),2^k.$

Dividing by $u=2^k$ gives

$(v \oplus x)/u = 2^{t+1}-1.$

Writing $2^{t+1}-1$ in binary yields a block of $t+1$ ones. Shifting right by $2$ gives

$((v \oplus x)/u) \gg 2 = 2^{t-1}-1,$

which is a block of $t-1$ ones in the least significant positions.

Define

$y = v + ((v \oplus x)/u \gg 2).$

The binary representation of $v$ has a single $1$ at position $k+t$ and zeros in all positions $<k+t$. The binary representation of $((v \oplus x)/u \gg 2)$ occupies only positions $0$ through $t-2$, hence lies strictly below position $k$. Therefore no carry propagates into or above position $k$ when forming $y$.

The low-order block of $y$ equals the sum of two disjoint blocks: zeros from $v$ and the block $2^{t-1}-1$, which produces a block of $t-1$ consecutive ones. The bit at position $k+t$ remains $1$, and the bit at position $k+t-1$ becomes $0$.

Thus $y$ has the same number of $1$-bits as $x$, with the rightmost change moving a $1$ from position $k$ to position $k+t$, and redistributing the remaining $t-1$ ones immediately below it.

This transformation replaces the rightmost block of the form $01\cdots 1$ in $x$ by $10\cdots 011\cdots 1$ in the minimal lexicographic increase among bitstrings with the same number of ones, hence $y$ is the next larger integer with the same number of $1$-bits as $x$.

Therefore

$\boxed{y \text{ is the next higher integer with the same Hamming weight as } x.}$

This completes the proof. ∎