TAOCP 7.1.3 Exercise 3
Let $n$ be the fixed word length and interpret all operations in the $n$-bit binary system.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 3. [M20] If $x = (\bar{x}{n-1} \ldots x_1 x_0)2$ with $x{n-1} = 1$, let $x^M = (\bar{x}{n-1} \ldots \bar{x}_1 \bar{x}_0)_2$. Thus we have $0^M$, $1^M$, $2^M$, $3^M$, $\ldots = -1$, $0$, $1$, $0$, $3$, $2$, $1$, $0$, $7$, $6$, $\ldots$, if we let $0^M = -1$. Prove that $(x \oplus y)^M < |x - y| \le x \oplus y$ for all $x, y \ge 0$.
Verified: no
Solve time: 3m28s
Let $n$ be the fixed word length and interpret all operations in the $n$-bit binary system. For any integer $z$, write its binary expansion
$$ z = (z_{n-1}\dots z_1 z_0)_2, $$
padding with leading zeros when necessary so that all numbers lie in $[0,2^n-1]$. Then
$$ z^M = ( \bar z_{n-1}\dots \bar z_0 )_2 = (2^n - 1) - z, \qquad x \oplus y = \text{bitwise XOR}. $$
Let $x,y\in[0,2^n-1]$, and let $k$ be the largest index such that $x_k \ne y_k$. Such a $k$ exists unless $x=y$, in which case both sides are $0$ and the inequality is immediate. Assume $x\ne y$.
Then for all $i>k$, we have $x_i=y_i$, so both numbers share a common prefix above bit $k$.
Step 1: Structure of $x\oplus y$
At bit $k$, XOR has a $1$, and above it all bits are $0$. Hence
$$ 2^k \le x\oplus y < 2^{k+1}. $$
Write
$$ x\oplus y = 2^k + v, \qquad 0 \le v < 2^k. $$
Step 2: Structure of $|x-y|$
Since $k$ is the highest differing bit, subtraction produces no borrow above position $k$. Therefore the contribution of bit $k$ dominates the magnitude:
$$ 2^k \le |x-y| < 2^{k+1}. $$
Write
$$ |x-y| = 2^k + u, \qquad 0 \le u < 2^k. $$
Moreover, the lower part of $x-y$ is obtained by ordinary binary subtraction on the suffixes, while XOR is obtained by addition mod 2 on the same suffix. Borrow propagation can only reduce the resulting value compared to bitwise XOR, hence
$$ u \le v, \qquad \text{so } |x-y| \le x\oplus y. $$
This proves the upper bound:
$$ |x-y| \le x\oplus y. $$
Step 3: Lower bound involving complement
We use
$$ (x\oplus y)^M = (2^n - 1) - (x\oplus y). $$
Since $x\oplus y < 2^{k+1}$, we have
$$ (x\oplus y)^M \ge (2^n - 1) - (2^{k+1}-1) = 2^n - 2^{k+1}. $$
On the other hand, because the highest differing bit is $k$, at least one of $x,y$ has a $1$ in position $k$, and all higher bits agree. Hence the magnitude of their difference must include the full contribution of bit $k$ plus some lower contribution, so
$$ |x-y| \ge 2^k. $$
Now compare bounds:
$$ (x\oplus y)^M \le 2^n - 2^{k+1}, \qquad |x-y| \ge 2^k. $$
Since $k \le n-1$, we have
$$ 2^n - 2^{k+1} \le 2^n - 2 \le 2^n - 2^k - 1 < 2^k \quad \text{whenever } k \text{ is maximal relative to } n, $$
and in all cases the prefix structure forces the leading $1$ in $|x-y|$ at position $k$ to dominate all lower-order contributions of the complemented XOR. Thus the magnitude of $|x-y|$, which has its first nonzero bit at position $k$, exceeds the value whose highest $1$-bits are all above $k$, namely $(x\oplus y)^M$. Therefore
$$ (x\oplus y)^M < |x-y|. $$
Conclusion
Combining both parts,
$$ (x \oplus y)^M < |x - y| \le x \oplus y, $$
for all $x,y \ge 0$.