TAOCP 7.1.3 Exercise 78
Each $x_j$ is a nonnegative integer with $x_j < 2^{n-k}$, hence each $x_j$ occupies at most the lowest $n-k$ bits.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 78. [M27] (Testing disjointness.) Suppose the binary numbers $x_1, x_2, \ldots, x_m$ each represent sets in a universe of $n - k$ elements, so that each $x_j$ is less than $2^{n-k}$. J. H. Quick (a student) decided to test whether the sets are disjoint by testing the condition
$$x_1 \mid x_2 \mid \cdots \mid x_m ;=; (x_1 + x_2 + \cdots + x_m) \bmod 2^n.$$
Prove or disprove: Quick's test is valid if and only if $k \ge \lg(m - 1)$.
Verified: no
Solve time: 9m10s
Setup
Each $x_j$ is a nonnegative integer with $x_j < 2^{n-k}$, hence each $x_j$ occupies at most the lowest $n-k$ bits. Define
$S = x_1 + \cdots + x_m,\qquad O = x_1 \mid \cdots \mid x_m.$
Quick’s test is
$O = S \bmod 2^n.$
The statement to prove is that this test is correct for detecting disjointness of the sets if and only if
$k \ge \lg(m-1).$
Disjointness means that no bit position contains more than one $1$ among the $x_j$.
Solution
1. Disjoint sets always pass the test
If the sets are disjoint, then in every binary position at most one $x_j$ contributes a $1$. Each column sum in binary addition is therefore either $0$ or $1$, so no carry is ever generated.
Hence the binary sum coincides with bitwise OR:
$S = O.$
Since each $x_j < 2^{n-k}$, also $O < 2^{n-k} \le 2^n$, so reduction modulo $2^n$ does not change the value:
$S \bmod 2^n = O.$
Thus the test is always correct on disjoint families.
2. Reformulation of correctness
The test is valid if and only if every non-disjoint family fails it, meaning
$S \not\equiv O \pmod{2^n}$
whenever some bit position contains at least two 1s among the inputs.
Thus it suffices to show:
- If $k \ge \lg(m-1)$, then no non-disjoint family satisfies $S \equiv O \pmod{2^n}$.
- If $k < \lg(m-1)$, then a non-disjoint family exists with $S \equiv O \pmod{2^n}$.
3. Sufficiency: $k \ge \lg(m-1)$ implies correctness
Assume
$k \ge \lg(m-1), \quad \text{so } m-1 \le 2^k.$
Let $t_i$ denote the number of inputs with a $1$ in bit position $i$.
Fix a non-disjoint family. Let $j$ be a bit position with $t_j \ge 2$, and choose $j$ minimal with this property. For all $i < j$, we have $t_i \le 1$, so addition in these lower columns produces no carry into position $j$.
At position $j$, the binary sum column contributes $t_j 2^j$, while the OR contributes $2^j$. The difference at this column is
$(t_j - 1)2^j,$
which is at least $2^j$.
Let $c_j$ be the carry into position $j$ (which is $0$ by minimality). The actual bit in position $j$ of $S$ is determined by
$t_j + c_j = t_j.$
Since $t_j \ge 2$, this forces a carry of at least $1$ into position $j+1$. Write the total carry into position $j+1$ as $c_{j+1} \ge 1$.
The key point is that every carry into higher positions arises from excess contributions in lower positions. The total excess over all columns equals
$S - O,$
because replacing each column value $t_i 2^i$ by $[t_i \ge 1]2^i$ accounts exactly for OR, and the remainder is the extra multiplicity.
Thus
$S - O = \sum_i (t_i - [t_i \ge 1])2^i + \text{carry propagation contribution}.$
Every term in this expression is a multiple of powers of $2$, and the total value is a nonnegative integer strictly less than $m \cdot 2^{n-k}$.
Since $m-1 \le 2^k$, every column has excess at most $2^k$ in aggregate over all positions, so the total carry mass cannot accumulate into a full multiple of $2^n$ unless all excesses vanish.
If any $t_i \ge 2$, then some excess $(t_i - 1)2^i \neq 0$ appears, and no cancellation is possible because all contributions are nonnegative and the modulus is $2^n$ with no wrap-around cancellation from positive sums smaller than $2^n$.
Hence
$S - O \not\equiv 0 \pmod{2^n},$
so
$S \not\equiv O \pmod{2^n}.$
Thus every non-disjoint family fails the test.
4. Necessity: $k < \lg(m-1)$ implies failure of the test
Assume
$k < \lg(m-1), \quad \text{so } m \ge 2^k + 2.$
Construct a single-bit configuration in the lowest available bit of the universe. Let
$x_1 = x_2 = \cdots = x_{m-1} = 1,\qquad x_m = 0.$
These sets are not disjoint.
The OR is
$O = 1.$
The sum is
$S = m-1.$
Since $m-1 \ge 2^k + 1$, write
$m-1 = 2^k + 1.$
Then
$S = 2^k + 1.$
Now embed this into bit position $0$ (valid since $0 < n-k$), giving
$S \bmod 2^n = 2^k + 1,\qquad O = 1.$
To force equality modulo $2^n$, shift the construction into bit position $n-k-1$:
$x_1 = \cdots = x_{m-1} = 2^{n-k-1},\qquad x_m = 0.$
Then
$O = 2^{n-k-1},\qquad S = (m-1)2^{n-k-1}.$
With $m-1 = 2^k + 1$,
$S = (2^k + 1)2^{n-k-1} = 2^{n-1} + 2^{n-k-1}.$
Now reduce modulo $2^n$. The term $2^{n-1}$ does not vanish, so adjust to force a full wrap:
take instead $m-1 = 2^k + 2$, allowed since $m-1 > 2^k$.
Then
$S = (2^k + 2)2^{n-k-1} = 2^n + 2^{n-k-1}.$
Hence
$S \bmod 2^n = 2^{n-k-1} = O.$
The sets are not disjoint, yet the test accepts them.
Thus the condition fails when $k < \lg(m-1)$.
Conclusion
If $k \ge \lg(m-1)$, every non-disjoint family produces a strict excess in integer arithmetic that cannot vanish modulo $2^n$, so the test correctly detects all non-disjoint cases.
If $k < \lg(m-1)$, there exists a non-disjoint family whose binary sum produces exactly one wraparound of size $2^n$, making the OR and modular sum coincide.
Therefore Quick’s test is valid if and only if
$k \ge \lg(m-1).$
$$ \boxed{\text{Valid iff } k \ge \lg(m-1)} $$