 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$. SetThe 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,\dots ,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. HenceIndeed 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)$. Delay is $O(\log n)$ and size is $O(n)$, counting fixed-fan-in logic gates and the usual wire fan-out model.