= Hierarchical leading-zero counter
For a block of $2^k$ <bits>, encode its <count leading zeros> result as a zero flag $z$ followed by $k$ low count <bits> $r$. An all-zero block has $(z,r)=(1,0)$; otherwise $z=0$. Two half-block encoders supply flags $z_H,z_L$ and low counts $h,\ell$. Combine them using $z=z_H\land z_L$, $r_{k-1}=z_H\land\neg z_L$, and $r_i=\operatorname{mux}(z_H,h_i,\ell_i)$ for $i<k-1$. A one-<bit> leaf has $z=\neg x$ and no low count <bits>. Checking whether the upper half is nonzero, only the lower half is nonzero, or both halves are zero proves the formula.
All count <bits> are selected in parallel, so $D(n)=D(n/2)+O(1)$ for <circuit depth>. The <circuit size> satisfies $S(n)=2S(n/2)+O(\log n)$; summing the work over levels gives $S(n)=O(n)$. Sharing the all-zero flags avoids a serial <adder> along the critical path.
Back to article page
