TAOCP 7.1.3 Exercise 28

Let $y = (x + 1) ,&, \bar{x}$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 28. [16] What does the operation $(x + 1) ,&, \bar{x}$ produce?

Verified: yes
Solve time: 1m17s

Solution

Let $y = (x + 1) ,&, \bar{x}$. For each bit position $k \ge 0$, write $y_k$ for the $k$-th bit of $y$. By definition,

$y_k = (x+1)_k \wedge \bar{x}_k = (x+1)_k \wedge \neg x_k.$

To analyze $(x+1)_k$, introduce the carry sequence $c_k$ arising from adding $1$ to $x$. Let $c_0 = 1$, and for $k \ge 0$,

$c_{k+1} = c_k \wedge x_k.$

Thus $c_k = 1$ exactly when $x_0 = x_1 = \cdots = x_{k-1} = 1$, and $c_k = 0$ otherwise. Hence

$(x+1)_k = x_k \oplus c_k.$

Substituting into $y_k$ gives

$y_k = (x_k \oplus c_k) \wedge \neg x_k.$

Using distributivity in (6),

$(x_k \oplus c_k) \wedge \neg x_k = (x_k \wedge \neg x_k) \oplus (c_k \wedge \neg x_k).$

Since $x_k \wedge \neg x_k = 0$, this reduces to

$y_k = c_k \wedge \neg x_k.$

Thus $y_k = 1$ exactly when $x_k = 0$ and $c_k = 1$, and $c_k = 1$ exactly when all lower bits $x_0, \ldots, x_{k-1}$ are $1$. Therefore $y_k = 1$ precisely for the least index $k$ such that $x_k = 0$, provided such an index exists, and $y_j = 0$ for all other $j$.

If no such $k$ exists, then all bits of $x$ are $1$, hence $c_k = 1$ for all $k$ and $x_k = 1$ for all $k$, so $y_k = 0$ for all $k$.

Therefore $y$ is either $0$ or a single power of two located at the least significant zero bit of $x$.

$\boxed{(x+1),&,\bar{x} = \text{the bit mask of the least significant zero bit of } x \text{ (or } 0 \text{ if none exists)}}$

This completes the solution. ∎