Iterierte assoziative Operationen

Prinzip: wenn ⊕ assoziativ, dann sollte man

x₁⊕x₂⊕x₃⊕x₄⊕x₅⊕x₆⊕x₇⊕x₈⊕

so auswerten:

((x₁⊕x₂)⊕(x₃⊕x₄))⊕((x₅⊕x₆)⊕(x₇⊕x₈))

Beispiel: carry-lookahead-Addierer

(die assoziative Operation ist die Verkettung der Weitergabefunktionen des Carry)

• beweise Assoziativität von ++
• welches ist die assoziative Operation für „(parallele) maximale Präfix-Summe``?