TAOCP 7.1.3 Exercise 95
Let $\mu = (11111111)_{256}$, the word whose every byte equals $255$, so $\mu$ serves as a mask selecting all byte positions.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 95. [22] [22] What's a bitwise way to tell if all bytes of $x = (x_7 \ldots x_1 x_0)_{256}$ are distinct?
Verified: no
Solve time: 4m32s
Solution
Let $\mu = (11111111)_{256}$, the word whose every byte equals $255$, so $\mu$ serves as a mask selecting all byte positions.
For each shift $k$ with $1 \le k \le 7$, compare every byte of $x$ with the byte $k$ positions to its right. Using (3), bytewise equality is detected by XOR: the $j$th byte of $x \oplus (x \gg 8k)$ equals $x_j \oplus x_{j-k}$, which is $0$ exactly when $x_j = x_{j-k}$.
Thus define
$t_k = \overline{x \oplus (x \gg 8k)} ,&, \mu.$
The $j$th byte of $t_k$ equals $255$ precisely when $j \ge k$ and $x_j = x_{j-k}$, and equals $0$ otherwise.
Now combine all comparisons:
$t = t_1 \mid t_2 \mid \cdots \mid t_7.$
The $j$th byte of $t$ is nonzero exactly when there exists $k \in {1,\ldots,7}$ such that $x_j = x_{j-k}$, which is equivalent to the existence of indices $i \ne j$ with $x_i = x_j$.
Hence $t = 0$ if and only if no such equality occurs, meaning all bytes of $x$ are pairwise distinct.
Therefore a bitwise test for distinctness is
$t = \bigvee_{k=1}^{7} \left(\overline{x \oplus (x \gg 8k)} ,&, \mu\right), \qquad \text{all bytes distinct} \iff t = 0.$
This completes the solution. ∎