TAOCP 7.1.3 Exercise 81
Let $\chi$ be a fixed set of nonnegative integers closed under the relation $x \subseteq \chi$, meaning every 1-bit position of $x$ corresponds to an element of $\chi$.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 81. [21] Find a formula for "scattered difference," to go with the "scattered sum" $(86)$.
Verified: no
Solve time: 4m55s
Solution
Let $\chi$ be a fixed set of nonnegative integers closed under the relation $x \subseteq \chi$, meaning every 1-bit position of $x$ corresponds to an element of $\chi$. The relation $x \subseteq y$ is defined in Section 7.1.3 by
$$ x \subseteq y \iff (x ,&, \bar{y}) = 0. $$
Hence $x \subseteq \chi$ means every 1-bit of $x$ is allowed by $\chi$.
We assume $x \ne 0$ and seek the largest integer $x_- < x$ such that $x_- \subseteq \chi$. The order is the usual integer order, not subset inclusion.
Let $p$ be the position of the least significant 1-bit of $x$. Then $x$ has the form
$$ x = a \cdot 2^{p+1} + 2^p, $$
where $a$ contains all higher bits of $x$.
Any integer $y < x$ satisfies $y \le x - 1$. The condition $y < x$ forces a change in the bit pattern at or below position $p$. The subtraction $x - 1$ flips the lowest 1-bit of $x$ to 0 and turns all lower bits into 1. Thus
$$ x - 1 = a \cdot 2^{p+1} + (2^p - 1). $$
The number $x - 1$ may violate $x_- \subseteq \chi$ because some bits below position $p$ might not be allowed by $\chi$. Let
$$ L = (2^p - 1) ,&, \chi. $$
This extracts from the low block $0,1,\dots,p-1$ exactly those bits permitted by $\chi$.
To ensure maximality under $x_- < x$, the higher part $a \cdot 2^{p+1}$ must remain unchanged, since any reduction there would produce a strictly smaller integer without affecting feasibility of maximizing lower bits.
Therefore the largest admissible candidate is obtained by keeping all bits of $x$ above $p$, and replacing the lower $p$ bits by the largest subset of $\chi$ supported there:
$$ x_- = (x ,&, \bar{(2^p - 1)}) ;\mid; \bigl((2^p - 1) ,&, \chi\bigr). $$
This expression is equivalent to:
- zeroing the lowest $p$ bits of $x$,
- then filling those positions with the maximal allowed bits from $\chi$.
Since $p$ is the position of the least significant 1-bit of $x$, it satisfies
$$ 2^p = x ,&, (-x) $$
by the standard identity in Section 7.1.3.
Hence the formula can be written without explicit bit search:
$$ x_- = (x ,&, \bar{(x ,&, (-x))}) ;\mid; \bigl(\chi ,&, ((x ,&, (-x)) - 1)\bigr). $$
The first term removes the lowest 1-bit of $x$ and all lower bits; the second term fills the freed positions with the maximal allowed configuration in $\chi$.
Maximality follows because any larger candidate would either exceed $x$ by altering bits above $p$, or would violate $x_- \subseteq \chi$ by introducing forbidden bits below $p$. Any smaller modification within the low block contradicts maximality of $\chi ,&, ((2^p - 1))$ in that range.
Thus the required integer is obtained by clearing the least significant 1-bit of $x$ and replacing all lower bits by the bitwise intersection with $\chi$.
$$ \boxed{ x_- = (x ,&, \bar{(x ,&, (-x))}) ;\mid; \bigl(\chi ,&, ((x ,&, (-x)) - 1)\bigr) } $$
This completes the construction of the largest $x_- < x$ satisfying $x_- \subseteq \chi$. ∎