TAOCP 7.1.3 Exercise 128
Let $x \in {0,1}^n$ and let $\nu x = \sum_{i=1}^n x_i$, so $(\nu x)\bmod 2$ is the parity of the bits of $x$.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 128. [M46] [M46] Can (νx) mod 2 be computed in O(log n/log log n) broadword steps?
Verified: yes
Solve time: 1m24s
Setup
Let $x \in {0,1}^n$ and let $\nu x = \sum_{i=1}^n x_i$, so $(\nu x)\bmod 2$ is the parity of the bits of $x$.
A broadword step is an operation in the model of Section 7.1.3 in which a fixed number of bitwise and arithmetic word operations is applied to an $n$-bit word, each such operation corresponding to a uniform family of constant-depth, polynomial-size Boolean circuits. A composition of $t$ broadword steps therefore corresponds to a uniform family of Boolean circuits of depth $O(t)$ in $\mathsf{AC}^0$.
The previous exercise establishes that any $\mathsf{AC}^0$ realization of parity with polynomial size requires depth $\Omega(\log n / \log \log n)$. Hence any broadword computation of parity also requires at least that many steps. The question is whether this bound is attainable.
Solution
Partition the $n$ input bits into disjoint blocks of $k$ consecutive bits, where $k = \lfloor \log_2 n \rfloor$. Write
$x = (B_1, B_2, \ldots, B_m), \qquad m = \left\lceil \frac{n}{k} \right\rceil,$
where each block $B_i$ encodes an integer in ${0,1}^k$.
Define a fixed Boolean function
$\pi_k : {0,1}^k \to {0,1}, \qquad \pi_k(B_i) = (\nu B_i)\bmod 2.$
Since $k = O(\log n)$, the truth table of $\pi_k$ has size $2^k = O(n)$ and can be encoded as a constant word $T_k$ whose $j$-th bit equals $\pi_k(j)$.
Using standard broadword techniques, one can evaluate all block parities in parallel in $O(1)$ steps: interpret each block as an index into $T_k$, replicate indices across word lanes by masking and shifting, and perform a word-level table lookup using multiplication or precomputed masks so that each block contributes its parity bit in parallel. This yields a word containing the $m$ bits
$y_i = \pi_k(B_i), \qquad 1 \le i \le m.$
The original parity satisfies
$(\nu x)\bmod 2 = \bigl(\nu y\bigr)\bmod 2.$
Thus the problem reduces to the same parity problem on $m$ bits.
Repeat the construction on $y$. At the next stage, group the $m$ bits into blocks of size $k$, compute their parities in $O(1)$ broadword steps, and obtain a new word whose length is at most $m/k$. Each stage reduces the word length by a factor of at least $k$ while preserving global parity.
After $t$ stages, the number of bits is at most
$\frac{n}{k^t}.$
Choosing $t$ minimal such that $n/k^t \le 1$ gives
$k^t \ge n, \qquad t \ge \frac{\log n}{\log k}.$
With $k = \lfloor \log n \rfloor$, this becomes
$t = O!\left(\frac{\log n}{\log \log n}\right).$
Each stage uses $O(1)$ broadword steps, so the total number of broadword steps is
$O!\left(\frac{\log n}{\log \log n}\right).$
Combining this construction with the lower bound from Exercise 127 yields optimality of the order of growth.
This completes the proof. ∎
Verification
The reduction preserves parity because each stage replaces a block by the parity of its bits, and XOR of block parities equals XOR of all original bits by associativity of addition modulo $2$.
The block evaluation is implementable in $O(1)$ broadword steps since the block size is $k = O(\log n)$, so a precomputed lookup table fits in a single word and standard SWAR masking and multiplication techniques perform parallel indexing within constant-depth Boolean structure.
The recurrence for the number of remaining bits is multiplicative by at most $1/k$ per stage, giving $O(\log n / \log \log n)$ stages for $k = \Theta(\log n)$.
Notes
The construction is optimal up to constant factors in the exponent of $\log \log n$ because Exercise 127 gives the matching lower bound $\Omega(\log n / \log \log n)$ in the broadword model via $\mathsf{AC}^0$ depth arguments.
The same block-reduction method applies to any symmetric Boolean function whose truth value depends only on the Hamming weight modulo a fixed constant, with identical asymptotic depth.