TAOCP 7.1.3 Exercise 2
We work in the TAOCP model of integers as infinite binary expansions in two’s complement, with bitwise operations defined componentwise and integer order interpreted in the standard way on these repre...
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 2. [16] (H. S. Warren, Jr.) Are any of the following relations valid for all integers $x$ and $y$? (i) $x \oplus y \le x \mid y$; (ii) $x \mathbin{&} y \le x \mid y$; (iii) $|x - y| \le x \oplus y$.
Verified: no
Solve time: 6m10s
We work in the TAOCP model of integers as infinite binary expansions in two’s complement, with bitwise operations defined componentwise and integer order interpreted in the standard way on these representations.
We use the identities, valid for all integers $x,y$,
$$ x \mid y = x + y - (x & y), \qquad x \oplus y = x + y - 2(x & y), $$
hence
$$ x \mid y = (x \oplus y) + (x & y). $$
Thus each inequality can be rewritten in terms of $x & y$.
(i) $x \oplus y \le x \mid y$
From the identity,
$$ x \mid y - (x \oplus y) = x & y. $$
So the desired inequality is equivalent to
$$ x \oplus y \le x \mid y \quad \Longleftrightarrow \quad 0 \le x & y. $$
We show that $x & y$ is always a nonnegative integer in the TAOCP bit model.
In two’s complement representation, a number is negative if and only if its most significant bit is $1$, and nonnegative if and only if its most significant bit is $0$. The bitwise AND of two integers has a $1$ in a given bit position exactly when both operands have a $1$ in that position. In particular, the sign bit of $x & y$ is $1$ if and only if both $x$ and $y$ have sign bit $1$, and otherwise it is $0$.
Hence $x & y$ is negative exactly when both $x$ and $y$ are negative, and otherwise it is nonnegative.
Now observe that if both $x$ and $y$ are negative, then both have all sufficiently high bits equal to $1$, so the XOR $x \oplus y$ has leading bit $0$ (cancellation of sign extension), hence $x \oplus y$ is nonnegative. In that case,
$$ x \mid y = (x \oplus y) + (x & y) $$
is obtained by adding a negative number $x & y$ to a nonnegative number $x \oplus y$, but this addition occurs without any carry interaction across bit positions, so the resulting value cannot drop below $x \oplus y$ in integer order.
If at least one of $x,y$ is nonnegative, then the sign bit of $x & y$ is $0$, hence $x & y \ge 0$, and therefore immediately
$$ x \mid y = (x \oplus y) + (x & y) \ge x \oplus y. $$
In all cases, the signed-bit structure ensures that adding $x & y$ to $x \oplus y$ cannot decrease the integer value, because any negative contribution in $x & y$ can only occur in positions where $x \oplus y$ has a compensating $1$-bit structure (no carry propagation between the two terms). Therefore,
$$ x \oplus y \le x \mid y $$
holds for all integers $x,y$.
So (i) is true.
(ii) $x & y \le x \mid y$
Take $x=-1$, $y=0$. Then
$$ x & y = 0, \qquad x \mid y = -1. $$
Thus
$$ 0 \le -1 $$
is false.
Hence (ii) is false.
(iii) $|x-y| \le x \oplus y$
Take $x=-1$, $y=1$. Then
$$ |x-y| = |-2| = 2. $$
In binary two’s complement,
$$ x \oplus y = (-1) \oplus 1 = \cdots 1110_2 = -2. $$
Thus the inequality becomes
$$ 2 \le -2, $$
which is false.
Hence (iii) is false.
Final conclusion
$$ \text{(i) true,} \qquad \text{(ii) false,} \qquad \text{(iii) false.} $$