Écrire additionne c2(s, t) , qui additionne deux codages en complément…

Pourquoi ce critère. Additionner un positif et un négatif ne peut pas déborder : le résultat est compris entre les deux opérandes, donc dans l'intervalle. Le débordement ne peut donc survenir que si les deux signes coïncident — et il se manifeste alors par un résultat de signe opposé, puisque la somme « repasse de l'autre côté » du cercle des $2^n$ configurations.

def additionne_c2(s, t):
    """Somme de deux codages en complément à 2 de même longueur.

    Renvoie (codage de la somme, débordement), où débordement
    est un booléen. Précondition : len(s) == len(t).
    """
    assert len(s) == len(t)
    n = len(s)
    res = addition_base(s, t, 2)[-n:]
    deborde = (s[0] == t[0]) and (res[0] != s[0])
    return res, deborde

Validation exhaustive — on compare au calcul exact fait par Python :

for n in (4, 8):
    lo, hi = -2**(n - 1), 2**(n - 1) - 1
    for x in range(lo, hi + 1):
        for y in range(lo, hi + 1):
            res, deb = additionne_c2(complement_a_2(x, n),
                                     complement_a_2(y, n))
            assert deb == (not lo <= x + y <= hi)
            if not deb:
                assert depuis_complement_a_2(res) == x + y

Les $16^2+256^2=65792$ cas passent : le critère est donc exact, pas seulement plausible.

Contrôle : additionne_c2(c(60), c(-100)) rend ("11011000", False) et additionne_c2(c(70), c(70)) rend ("10001100", True) — les deux exercices de TD, retrouvés automatiquement.

Piège : croire que la retenue sortante signale le débordement. Elle ne le signale pas : dans $c(60)+c(-100)$ il n'y a pas de retenue sortante et pas de débordement, mais dans $c(-1)+c(-1)$ il y a une retenue sortante et aucun débordement.