桁上げ先読みと接頭辞計算

$g_i = a_i \land b_i$、$p_i = a_i \oplus b_i$ とおくと、定義 4.1 の桁上げは $c_{i+1} = g_i \lor (p_i \land c_i)$ と書けます。ここで $\{0,1\}^2$ 上の二項演算

を定めると、次が成り立ちます。

1. $\circ$ は結合的で、$(0,1)$ を単位元とするモノイドを与えます。
2. $(G_i, P_i) = (g_i, p_i) \circ (g_{i-1}, p_{i-1}) \circ \cdots \circ (g_0, p_0)$ とおくと、$c_{i+1} = G_i \lor (P_i \land c_0)$ が成り立ちます。
3. ファンイン 2 の AND・OR・XOR ゲートからなる回路で、すべての $c_{i+1}$（$0 \le i \le n-1$）を深さ $O(\log n)$、ゲート数 $O(n \log n)$ で計算できます。