Complément – Demi-additionneur et additionneur complet

La somme de trois bits vaut $0$, $1$, $2$ ou $3$, écrite en binaire $r_{\text{out}}s$ :

Le bit de somme vaut $1$ lorsque le nombre de $1$ parmi $(a,b,r)$ est impair (1 ou 3). Or $a\oplus b\oplus r$ vaut précisément $1$ si et seulement si ce nombre est impair (le XOR est une somme modulo $2$, associative) : $s=a\oplus b\oplus r$, la parité des trois bits, la fonction même que réalise un va-et-vient à trois endroits. La retenue vaut $1$ dès que deux bits au moins valent $1$ : c'est la fonction majorité, $r_{\text{out}}=ab+br+ra$, qu'on écrit aussi $ab+r(a\oplus b)$ : la retenue naît soit de $a$ et $b$, soit de $r$ quand exactement un des deux bits vaut $1$. Le demi-additionneur ($r=0$) donne $s=a\oplus b$ et $r_{\text{out}}=ab$.