Écrire une fonction oppose(s) qui, donnée une chaîne de bits en…

Pourquoi ça marche. Notons $v$ la valeur non signée de la chaîne, sur $n$ bits. Inverser tous les bits remplace chaque $1$ par un $0$ et réciproquement, donc transforme $v$ en $(2^n-1)-v$ : c'est la chaîne de $n$ uns moins $v$, sans aucune retenue. En ajoutant $1$, on obtient $2^n-v$, c'est-à-dire $-v$ modulo $2^n$ : exactement le codage de l'opposé.

def oppose(s):
    """Codage en complément à 2 de l'opposé de l'entier codé par s.

    Précondition : s ne code pas -2**(n-1), dont l'opposé n'est
    pas représentable sur n bits.
    """
    inverse = ""
    for c in s:
        inverse = inverse + ("1" if c == "0" else "0")
    return addition_base(inverse, "1", 2)[-len(s):]

La tranche finale [-len(s):] jette la retenue sortante — c'est la réduction modulo $2^n$ du théorème du cours.

Validation exhaustive sur $4$, $8$ et $12$ bits, pour toutes les valeurs sauf la plus petite :

for n in (4, 8, 12):
    for x in range(-2**(n - 1) + 1, 2**(n - 1)):
        s = complement_a_2(x, n)
        assert depuis_complement_a_2(oppose(s)) == -x

La valeur qui échoue. C'est $-2^{n-1}$, soit $-128$ sur 8 bits. Son codage est 10000000 ; inversé il donne 01111111, plus $1$ : 10000000. La fonction rend l'entrée elle-même, et $-(-128)=128$ n'est effectivement pas représentable sur 8 bits — l'intervalle $[-128;127]$ n'est pas symétrique.

Piège : y voir un bogue de la fonction. Ce n'en est pas un : c'est une limite du codage, qui possède un négatif de plus que de positifs. La fonction ne peut que la signaler, d'où la précondition.