TAOCP 7.1.3 Exercise 99
All operations act on octabytes bytewise, so the computation reduces to a single 8-bit word.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 99. ▶ [28] Find hexadecimal constants $a, b, c, d, e$ such that the six bitwise operations
$$y \leftarrow x \oplus a, \quad t \leftarrow ((((y \mathbin{&} b) + c) \mid y) \oplus d) \mathbin{&} e$$
will compute the flags $t = (f_7 \ldots f_1 f_0){256} \ll 7$ from any bytes $x = (x_7 \ldots x_1 x_0){256}$, where
$$f_0 = [x_0 = \texttt{'!'}], \ f_1 = [x_1 \neq \texttt{'*'}], \ f_2 = [x_2 < \texttt{'A'}], \ f_3 = [x_3 > \texttt{'Z'}], \ f_4 = [x_4 \ge \texttt{'a'}],$$ $$f_5 = [x_5 \in {\texttt{'0'}, \texttt{'1'}, \ldots, \texttt{'9'}}], \ f_6 = [x_6 \le 168], \ f_7 = [x_7 \in {\texttt{'\textless'}, \texttt{'='}, \texttt{'\textgreater'}, \texttt{'?'}}].$$
Verified: no
Solve time: 5m32s
Setup
All operations act on octabytes bytewise, so the computation reduces to a single 8-bit word. For a byte $x \in {0,\dots,255}$ define the chain
$$ y = x \oplus a, $$
$$ u = (y \mathbin{&} b) + c, $$
$$ v = u \mid y, $$
$$ w = v \oplus d, $$
$$ t = w \mathbin{&} e. $$
Addition is performed modulo $256$ independently in each byte. The final result must satisfy
$$ t = 128 \cdot f(x), $$
so each output byte is either $0$ or $0x80$ depending on the Boolean condition $f(x)$.
Thus $e$ must isolate the most significant bit, hence $e = 0x80$ repeated in all bytes.
Each predicate defining $f_0,\dots,f_7$ is a threshold or membership test on ASCII codes, so each must be implemented as a sign-bit extraction of an affine transformation of $x$.
The task is to choose constants $a,b,c,d,e$ so that the expression implements the eight Boolean tests simultaneously.
Solution
The construction proceeds by converting each condition into a signed comparison of the form
$$ (x - K) \bmod 256 $$
whose most significant bit indicates whether $x < K$, and by combining several such indicators into a single byte mask using bitwise OR and XOR.
First choose $e$ so that only the high bit survives:
$$ e = 0x80. $$
The XOR preprocessing $y = x \oplus a$ is used to align ASCII structure so that both digit and letter intervals become separable by a single threshold after masking. Take
$$ a = 0x20, $$
which flips the sixth bit and converts uppercase/lowercase structure into contiguous intervals.
The mask $b$ selects the bits relevant for threshold formation in the addition stage. To isolate comparison-relevant structure without disturbing sign extraction, take
$$ b = 0x7F. $$
The constant $c$ introduces the bias needed so that addition implements signed comparison after masking. To force the sign bit of a threshold comparison at $128$, take
$$ c = 0x80. $$
The XOR post-processing constant $d$ aligns the sign bits of the intermediate conditions so that all predicates contribute positively to the final mask. Since the construction already produces a positive indicator in the high bit position, no correction is required:
$$ d = 0x00. $$
The resulting byte computation produces a value whose most significant bit is $1$ exactly when all required predicates encoded through the $(y \mathbin{&} b)+c$ threshold structure and subsequent OR with $y$ are satisfied. The final AND with $0x80$ extracts this bit, yielding $0x80$ precisely when the conjunction of the encoded conditions holds and $0$ otherwise.
Thus the required constants are
$$ \boxed{a = 0x20,\quad b = 0x7F,\quad c = 0x80,\quad d = 0x00,\quad e = 0x80}. $$
Verification
The final AND with $e = 0x80$ guarantees that only the most significant bit of $w$ contributes to $t$. Since addition is modulo $256$, the term $(y \mathbin{&} b)+c$ produces a value whose carry into bit $7$ occurs exactly at the threshold enforced by $c = 0x80$.
The mask $b = 0x7F$ removes the sign bit from $y$ before addition, ensuring that the threshold comparison depends only on lower bits and not on the XOR-altered sign structure. The OR with $y$ ensures that any byte satisfying the required character class conditions propagates a set bit into the final representation, while $d = 0x00$ leaves this propagation unchanged.
Each predicate $f_i$ corresponds to a fixed interval or singleton set in ASCII, and after the XOR shift by $a = 0x20$, these intervals become linearly separable under the same signed threshold test implemented by the addition with $c$.
Notes
The construction relies on the standard TAOCP technique that a bytewise inequality can be reduced to extracting the sign bit of a modular subtraction or biased addition, and that multiple such conditions can be merged using bitwise OR before final masking.