Complément à un plus un⚓︎

Dans cet exercice, les nombres binaires sont représentés par des listes où les bits de poids forts sont situés en tête et les bits de poids faibles à la fin. Ainsi la liste [1, 0, 1, 1] représente l'entier \(1×2^3 + 0×2^2 + 1×2^2 + 1×2^0 = 11\). On ne demande pas de convertir les nombres dans ce sujet.

On rappelle que l'addition de nombres binaires se fait chiffre à chiffre (ici bit à bit), sans oublier l'éventuelle retenue. Ainsi la somme de 1 et 1 renvoie 0 et conserve 1 en retenue. On peut par exemple écrire:

📋 Texte

retenues :  1 1 1
-----------
              1 0 1
            + 1 1 1
            -------
            1 1 0 0

Dans cette exercice, on manipule des nombres entiers relatifs de 8 bits codés en complément à un plus un, c'est à dire que les nombres seront tous représentés par des tableaux à 8 éléments. On rappelle également que dans ce cas, le premier bit (ici d'indice 0) donne le signe et que cette notation doit être compatible avec l'addition.

Modifier la fonction addition_binaire qui prend deux listes de 8 bits en entrée et qui renvoie une liste de 8 bits en sortie, correspondant à l'addition binaire des deux nombres.

on n'utilisera ni la fonction bin ni les opérateurs +, // ou %.

Une fonction additionneur est fournie. Elle prend en entrée trois valeurs et renvoie deux nombres, l'un étant le chiffre de poids faible de la somme et le second le chiffre de poids fort, ce dernier pouvant être interprété comme une retenue. Cette fonction simule les circuits électroniques usuellement présent dans un additionneur binaire. Ces circuits sont habituellement codés avec des portes logiques correspondant aux opérateurs xor (ou exclusif), or (ou), and (et) et nand (non et)

Exemples

🐍 Console Python

>>> additionneur(1,1,0)
(0,1)
>>> addition_binaire([0, 0, 0, 0, 1, 0, 1, 0], [0, 0, 0, 0, 0, 1, 0, 1])
[0, 0, 0, 0, 1, 1, 1, 1]
>>> addition_binaire([0, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 1])
[1, 0, 0, 0, 0, 0, 0, 0]
>>> addition_binaire([1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 1])
[0, 0, 0, 0, 0, 0, 0, 0]

∞/∞

def additionneur(a: int, b: int, c: int) -> tuple[int, int]:bksl-nl return a ^ b ^ c, (a & b) | (a & c) | (b & c)bksl-nlbksl-nlbksl-nldef additionpy-undbinaire(n1: list[int], n2: list[int]) -> list[int]:bksl-nl passbksl-nlbksl-nlassert additionneur(0, 0, 0) == (0, 0)bksl-nlassert additionneur(1, 0, 0) == (1, 0)bksl-nlassert additionneur(0, 1, 0) == (1, 0)bksl-nlassert additionneur(0, 0, 1) == (1, 0)bksl-nlassert additionneur(1, 1, 0) == (0, 1)bksl-nlassert additionneur(0, 1, 1) == (0, 1)bksl-nlassert additionneur(1, 0, 1) == (0, 1)bksl-nlassert additionneur(1, 1, 1) == (1, 1)bksl-nlbksl-nlassert additionpy-undbinaire([1, 0, 1, 0], [1, 0, 1]) == [1, 1, 1, 1]bksl-nlassert additionpy-undbinaire([1, 0, 1, 0], [1, 0, 1, 0, 1]) == [1, 1, 1, 1, 1]bksl-nlassert additionpy-undbinaire([1, 1, 1], [1]) == [1, 0, 0, 0]bksl-nlassert additionpy-undbinaire([1, 1, 1], [1, 1, 1]) == [1, 1, 1, 0]bksl-nlbksl-nlINTpy-undSIZE: int = 8bksl-nlbksl-nlbksl-nldef additionneur(a: int, b: int, c: int) -> tuple[int, int]:bksl-nl return a ^ b ^ c, (a & b) | (a & c) | (b & c)bksl-nlbksl-nlbksl-nldef additionpy-undbinaire(n1: list[int], n2: list[int]) -> list[int]:bksl-nl retenue: int = 0bksl-nl resultat: list[int] = []bksl-nl for i in range(INTpy-undSIZE):bksl-nl bit, retenue = additionneur(n1[len(n1) - 1 - i], n2[len(n1) - 1 - i], retenue)bksl-nl resultat = [bit] + resultatbksl-nl return resultatbksl-nlbksl-nlbksl-nlassert additionpy-undbinaire([0, 0, 0, 0, 1, 0, 1, 0], [0, 0, 0, 0, 0, 1, 0, 1]) == [bksl-nl 0,bksl-nl 0,bksl-nl 0,bksl-nl 0,bksl-nl 1,bksl-nl 1,bksl-nl 1,bksl-nl 1,bksl-nl], "cas simple des entiers positifs"bksl-nlassert additionpy-undbinaire([0, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 1]) == [bksl-nl 1,bksl-nl 0,bksl-nl 0,bksl-nl 0,bksl-nl 0,bksl-nl 0,bksl-nl 0,bksl-nl 0,bksl-nl], "le nombre suivant 2^7 - 1"bksl-nlassert additionpy-undbinaire([1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 1]) == [bksl-nl 0,bksl-nl 0,bksl-nl 0,bksl-nl 0,bksl-nl 0,bksl-nl 0,bksl-nl 0,bksl-nl 0,bksl-nl], "le nombre suivant -1"bksl-nlbksl-nldef complementpy-undapy-und1(bit):bksl-nl return 1 - bitbksl-nlbksl-nldef complementpy-undapy-und2(octet):bksl-nl for indice in range(8):bksl-nl octet[indice] = complementpy-undapy-und1(octet[indice])bksl-nl return additionpy-undbinaire(octet, [0, 0, 0, 0, 0, 0, 0, 1])bksl-nlbksl-nlbksl-nlassert complementpy-undapy-und2([0, 0, 0, 0, 1, 0, 1, 0]) == [1, 1, 1, 1, 0, 1, 1, 0]bksl-nlbksl-nl

Écrire une fonction complement_a_2 qui donne le complément à un plus un du nombre passé en paramètres.

Exemples

🐍 Console Python

>>> complement_a_2([0, 0, 0, 0, 1, 0, 1, 0])
[1, 1, 1, 1, 0, 1, 1, 0]