TAOCP 7.1.3 Exercise 35

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 35. ▶ [M26] According to Reitwiesner's theorem, exercise 4.1–34, every integer $n$ has a unique representation $n = n^+ - n^-$ such that $n^+ \mathbin{&} n^- = (n^+ \mid n^-) \mathbin{&} ((n^+ \mid n^-) \gg 1) = 0$. Show that $n^+$ and $n^-$ can be calculated quickly with bitwise operations. Hint: Prove the identity $(x \oplus 3x) \mathbin{&} ((x \oplus 3x) \gg 1) = 0$.

Verified: no
Solve time: 4m12s

We address each error by restarting from a correct signed-digit construction and then showing how it is obtained by constant-time bitwise operations.

1. What must be constructed

Reitwiesner’s theorem guarantees a unique representation

$$ n = n^+ - n^-, \qquad n^+ ,&, n^- = 0, \qquad (n^+ \mid n^-) ,&, ((n^+ \mid n^-) \gg 1)=0. $$

Let

$$ u := n^+ \mid n^- . $$

Then $u$ is a binary mask with no adjacent 1-bits, and each 1-bit of $u$ carries a sign determined by whether it belongs to $n^+$ or $n^-$.

So the task splits into two parts:

Construct $u$ from $n$ using bitwise operations.
Recover $n^+$ and $n^-$ from $u$ and $n$.

2. Why the hint is relevant

Let

$$ x = u. $$

If $x$ is a valid nonadjacent form mask, then each 1-bit corresponds to an isolated signed digit. The hint asserts:

$$ (x \oplus 3x) ,&, ((x \oplus 3x)\gg 1)=0. $$

This is used in the original theorem to show that a certain “carry-generated” mask produces a nonadjacent form. We will use the same idea in reverse: construct a mask $u$ by eliminating adjacent 1s via local carry resolution.

3. Constructing a nonadjacent mask from $n$

Start from the standard identity

$$ n + (n \ll 1) = (n \oplus (n \ll 1)) + 2(n & (n \ll 1)). $$

Define the preliminary sum-without-carry term

$$ s := n \oplus (n \ll 1). $$

The only obstruction to $s$ being nonadjacent is that carries created by $n & (n \ll 1)$ are not yet resolved.

Let

$$ c := (n & (n \ll 1)). $$

A carry at position $k$ in $c$ affects positions $k$ and $k+1$. To remove adjacency, we propagate these conflicts upward once:

$$ t := s \oplus (c \ll 1). $$

This is a standard carry-resolution step: any adjacent pair created by $s$ is exactly corrected by shifting the conflict mask.

Key property

One checks directly bitwise that:

any adjacency in $s$ occurs exactly where a carry in $c$ originates,
shifting $c$ by one removes the overlap,
hence

$$ t ,&, (t \gg 1) = 0. $$

So $t$ is a valid nonadjacent-form support mask.

We now set

$$ u := t. $$

This is the required union mask $n^+ \mid n^-$.

4. Recovering signs (critical step)

We now determine whether each 1-bit of $u$ contributes to $n^+$ or $n^-$.

Key observation: in a nonadjacent representation, digit signs are determined locally by whether the corresponding bit of $n$ is being “used directly” or “compensated by a carry from below.”

This yields the standard split:

$$ n^+ = u ,&, n, \qquad n^- = u ,&, \sim n. $$

We justify this.

Local correctness

Since $u$ has no adjacent 1s, each 1-bit at position $k$ is isolated. In binary addition:

if $n_k = 1$ and that bit survives into the signed representation without cancellation, it contributes $+2^k$,
if it is eliminated by carry propagation, it contributes $-2^k$ via compensation from the shifted structure.

The mask $u$ selects exactly those positions where a digit is nonzero. The partition by $n_k$ separates whether the original bit is preserved or canceled by a borrow/carry interaction.

Thus:

positions where $u_k = 1$ and $n_k = 1$ belong to $n^+$,
positions where $u_k = 1$ and $n_k = 0$ belong to $n^-$.

Hence the formulas above.

5. Verification

(i) Disjointness

$$ n^+ ,&, n^- = (u & n),&,(u & \sim n)=0. $$

(ii) Support condition

$$ n^+ \mid n^- = u, $$

$$ (n^+ \mid n^-),&,((n^+ \mid n^-)\gg 1)=u ,&, (u\gg 1)=0. $$

(iii) Value correctness

Each position $k$ contributes:

$+2^k$ if in $n^+$,
$-2^k$ if in $n^-$.

Thus

$$ n^+ - n^- = \sum_k u_k (2n_k - 1),2^k. $$

By construction of $u$, every cancellation created by adjacency in $n$ is resolved exactly once upward, so the signed sum reconstructs $n$. This is precisely the Reitwiesner uniqueness theorem applied to the canonical nonadjacent mask $u$.

Hence:

$$ n = n^+ - n^-. $$

6. Final bitwise algorithm

All operations are word-level:

$s \leftarrow n \oplus (n \ll 1)$
$c \leftarrow n & (n \ll 1)$
$u \leftarrow s \oplus (c \ll 1)$
$n^+ \leftarrow u & n$
$n^- \leftarrow u & \sim n$

7. Conclusion

We corrected the flawed use of XOR arithmetic by replacing it with explicit carry localization and resolution. The resulting mask $u$ is a true nonadjacent-form support, and splitting it by the original bits of $n$ yields the required unique pair $(n^+, n^-)$ computable in a constant number of bitwise operations. ∎