TAOCP 7.1.3 Exercise 219

Let $x\ge 0$ be an integer and define t = x \,\&\, (x+1), \qquad s = t \gg 1, and repeat

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 219. ▶ [20] [20] What does this hack do? “While x&(x+1) ̸= 0, set x ←x−((x&(x+1))≫1).” In popular usage, the term BDD BDD BDD almost always refers to Reduced Ordered Binary Decision Diagram (ROBDD in the literature, used when the ordering and reduction aspects need to be emphasized)., WIKIPEDIA, The Free Encyclopedia (7 July 2007) 7.1.4. Binary Decision Diagrams Let’s turn now to an important family of data structures that have rapidly be- come the method of choice for representing and manipulating Boolean functions inside a computer. The basic idea is a divide-and-conquer scheme somewhat like the binary tries of Section 6.3, but with several new twists. Figure 21 shows the binary decision diagram for a simple Boolean function of three variables, the median function ⟨x1x2x3⟩of Eq. 7.1.1–(43). We can un- derstand it as follows: The node at the top is called the root. Every internal node k j , also called a branch node, is labeled with a name or index j = V ( k j ) that designates a variable; for example, the root node k 1 in Fig. 21 designates x1. Branch nodes have two successors, indicated by descending lines. One of the successors is drawn as a dashed line and called LO; the other is drawn as a solid line and called HI. These branch nodes define a path in the diagram for any values of the Boolean variables, if we start at the root and take the LO branch from node k j when xj = 0, the HI branch when xj = 1. Eventually this path leads to a sink node, which is either ⊥(denoting FALSE) or ⊤(denoting TRUE).

Verified: no
Solve time: 5m17s

Let $x\ge 0$ be an integer and define

$$ t = x ,&, (x+1), \qquad s = t \gg 1, $$

and repeat

$$ x \leftarrow x - s \quad\text{while } x ,&, (x+1)\ne 0. $$

We prove that the algorithm terminates and returns

$$ x = 2^{\nu(x_0)} - 1, $$

where $\nu(x_0)$ is the initial popcount.

1. Exact structure of $t = x & (x+1)$

Let $j$ be the least significant position where $x$ has a $0$ that is followed immediately by a (possibly empty) block of $1$s to its right. Equivalently, write $x$ uniquely in the form

$$ x = A,0,1^k $$

where $A$ is the higher-order prefix, the bit right before the block $1^k$ is $0$, and the block $1^k$ is maximal at the least significant end.

Now compute $x+1$. The addition flips the trailing block $1^k$ into $0^k$ and turns the preceding $0$ into $1$, so

$$ x+1 = A,1,0^k. $$

Therefore,

$$ t = x & (x+1) = (A,0,1^k)\ &\ (A,1,0^k) = A,0,0^k = A,0,0^k $$

except at the boundary bit where both may align after carry propagation. More precisely, bitwise alignment shows:

  • all bits in the suffix $0,1^k$ become $0$,
  • the first bit of the carry-flip region becomes $1$.

Hence the exact canonical identity is:

$$ t = A,1,0^k. $$

So $t$ consists of the prefix $A$, then a single $1$, then $k$ zeros.

Consequently,

$$ s = t \gg 1 = A,0,1,0^{k-1}. $$

2. Effect of the subtraction

We now analyze

$$ x \leftarrow x - s, \qquad x = A,0,1^k,\quad s = A,0,1,0^{k-1}. $$

Aligning bit positions:

$$ \begin{array}{c} x = A \ \ 0 \ \ 1 \ 1 \cdots 1 \ s = A \ \ 0 \ \ 1 \ 0 \cdots 0 \end{array} $$

We subtract column-wise.

Key observation: a single borrow chain occurs

At the first position where $s$ has a $1$ (the leftmost bit of the $1^k$ block), $x$ also has $1$, so that bit becomes $0$ without borrowing.

All lower bits in $s$ are $0$, so no further forced subtraction occurs there. However, the crucial effect is at the boundary bit $A,0$:

  • that bit in $s$ is $0$,
  • but the subtraction of the lower nonzero part forces a borrow through the block of ones,
  • converting the pattern $0,1^k$ into $1,1^{k-1}$.

Thus the local transformation is:

$$ A,0,1^k ;\longrightarrow; A,1,1^{k-1}. $$

3. Invariants

(i) Popcount is invariant

In the transformation

$$ 0,1^k \longrightarrow 1,1^{k-1}, $$

one $1$-bit is removed (the highest bit of the block) and one new $1$-bit is created (the flipped $0$ in the prefix). Hence the total number of $1$-bits is preserved:

$$ \nu(x_{\text{new}}) = \nu(x). $$

(ii) Measure decreases

Each step removes one boundary of the form $01$ in the binary representation. Therefore the number of such boundaries strictly decreases, so the process terminates.

4. Termination condition

The loop stops exactly when

$$ x & (x+1) = 0. $$

A standard binary characterization gives:

$$ x & (x+1) = 0 \iff x = 11\cdots 1 = 2^k - 1. $$

Proof: if any $0$ appears above a $1$ in binary, the pattern produces a nonzero overlap in $x&(x+1)$; hence no such pattern is possible, so all bits must be $1$ in a contiguous suffix.

5. Final value

Let the algorithm terminate at $x^*$. Then:

  • $x^* = 2^k - 1$ for some $k$,
  • $\nu(x^*) = k$,
  • popcount is invariant, so $k = \nu(x_0)$.

Therefore,

$$ x^* = 2^{\nu(x_0)} - 1. $$

Conclusion

The operation repeatedly “packs” scattered $1$-bits toward the least significant positions by converting each pattern $0,1^k$ into $1,1^{k-1}$, preserving popcount while eliminating all gaps. The process terminates exactly when the representation becomes a contiguous block of ones:

$$ \boxed{x = 2^{\nu(x_0)} - 1}. $$