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\wedge z_L$, $r_{k-1}=z_H\wedge \neg z_L$, and $r_i=\mathrm{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.