kombinatorischer logischer Schaltkreis zur Berechnung der Summe von zwei n-stelligen binären Zahlen.

Für einen beliebigen Wert k ∈ {1, …, n – 1} unterteilt man den ersten Operanden α = (α_n–1, …, α₀) in den Wert

\begin{eqnarray}{\alpha }^{(k,1)}=\displaystyle \sum _{i=k}^{n-1}{\alpha }_{i}{2}^{i-k},\end{eqnarray}

der die n – k höherwertigen Stellen von α darstellt, und den Wert

\begin{eqnarray}{\alpha }^{(k,0)}=\displaystyle \sum _{i=0}^{k-1}{\alpha }_{i}{2}^{i},\end{eqnarray}

der die k niederwertigen Stellen von α darstellt. In gleicher Art und Weise spaltet man den Operanden β = (β_n–1, …, β₀) in die Werte β^(k,1) und β^(k,0) auf.

Der Leitgedanke des Verfahrens ist, daß sowohl die Summe α^(k,1) + β^(k,1) als auch die Summe α^(k,1) + β^(k,1) + 1 der höherwertigen Bits berechnet werden und je nachdem wie der Übertrag an der Stelle k – 1 aussieht, das richtige Resultat ausgewählt wird.

Setzt man \(k=\lfloor \frac{n}{2}\rfloor \) und wendet man das geschilderte Verfahren rekursiv an, so erhält man einen conditional-sum Addierer, der eine Laufzeit hat, die sich asymptotisch wie log n verhält. Die Fläche verhält sich wie n · log n.