= Solution
Use a <hierarchical leading-zero counter>. A block of $2^j$ <bits> returns a zero flag $z$ and $j$ low count <bits> $r$: its <count leading zeros> result is the concatenation $(z,r)$. Thus $z=1$ means that the block is entirely zero and $r=0$; otherwise $z=0$ and $r$ is its leading-zero count. A one-<bit> block needs just $z=\neg x$ and no low count <bits>.
For a block of $n=2^k$ <bits>, run two such <Boolean circuits> on the upper and lower halves in parallel. Write their flags as $z_H,z_L$ and their $k-1$ low count <bits> as $h_i,\ell_i$. Set
$$
\boxed{z=z_H\land z_L,\quad r_{k-1}=z_H\land\neg z_L,\quad r_i=(\neg z_H\land h_i)\lor(z_H\land\ell_i)\quad(0\le i<k-1).}
$$
The last expression is a two-input <multiplexer>. When the upper half is nonzero, its count is already the answer and $r_{k-1}=0$. When only the upper half is zero, $r_{k-1}=1$ supplies the contribution $n/2$ while the <multiplexers> supply the lower half's count. When both halves are zero, the answer is $(1,0,\ldots,0)$, representing $n$. This special encoding avoids an <adder> on the critical path.
Each node adds constant <circuit depth>, even though it uses $O(k)$ <logic gates> for its parallel <multiplexers>. Hence
$$
D(2^k)=D(2^{k-1})+O(1)=O(k),\qquad S(2^k)=2S(2^{k-1})+O(k)=O(2^k).
$$
Indeed the internal-node work is bounded by a constant times $\sum_{j=1}^k(n/2^j)j<2n$, and the $n$ leaves add $O(n)$. \b[Delay is $O(\log n)$ and size is $O(n)$], counting fixed-fan-in <logic gates> and the usual wire fan-out model.
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2022/digital-systems-linear-algebra-introduction-to-formal-proof-leading-zero-tree.png]
{title=Leading-zero summaries combine in parallel: the input $00000101$ gives the four-bit count $0101$}
{description=Internal nodes display their block length and encoded leading-zero count; leaves display the one-bit count. A count's first <bit> is the shared all-zero flag. The highlighted branch supplies the low count at the root.}
Back to article page
