Addition binaire
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, 1, 0, 1] représente l'entier \(1×2^3 + 1×2^2 +0×2^2 + 1×2^0 = 13\).
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.
La fonction additionneur fournie permet de mettre en œuvre ces additions élémentaires de bits.
Elle prend les valeurs de trois bits (les deux valeurs à sommer suivie de la retenue à prendre en compte) et renvoie le tuple contenant en première position le bit de retenue et en seconde le bit de poids faible de la somme .
On a ainsi :
>>> additionneur(0, 0, 0)
(0, 0)
>>> additionneur(0, 1, 0)
(0, 1)
>>> additionneur(1, 1, 0)
(1, 0)
>>> additionneur(1, 1, 1)
(1, 1)
La fonction additionneur
def additionneur(a, b, retenue):
return (a & b) | (a & retenue) | (b & retenue), a ^ b ^ retenue
Cette fonction utilise des opérateurs booléens :
&est l'opérateur \(\text{et}\) ;|est l'opérateur \(\text{ou}\) ;^est l'opérateur \(\text{ou exclusif}\).
Lorsque que l'on additionne trois bits, le résultat peut-être exprimé à partir de ces opérateurs :
- la retenue de \(a+b+c\) vaut \((a\text{ et }b)\text{ ou }(a\text{ et }c)\text{ ou }(b\text{ et }c)\) ;
- le bit de poids faible vaut \(a\text{ ou exclusif }b\text{ ou exclusif }c\).
On souhaite dans cet exercice écrire une fonction addition_binaire qui étend la fonction additionneur aux additions
de nombres s'écrivant sur \(8\) bits.
On se restreint donc aux cas des nombres entiers positifs de \(8\) bits. Les nombres sont donc tous représentés par des tableaux à \(8\) éléments.
Écrire la fonction addition_binaire qui prend en paramètres deux « nombres » représentés par des listes de \(8\) bits et renvoie une liste de \(8\) bits correspondant à l'addition binaire des deux nombres.
Interdiction
On n'utilisera pas les fonctions natives de Python permettant la manipulation des bits.
Exemples
>>> a = [0, 0, 0, 0, 1, 0, 1, 0]
>>> b = [0, 0, 0, 0, 0, 1, 0, 1]
>>> addition_binaire(a, b)
[0, 0, 0, 0, 1, 1, 1, 1]
>>> a = [0, 1, 1, 1, 1, 1, 1, 1]
>>> b = [0, 0, 0, 0, 0, 0, 0, 1]
>>> addition_binaire(a, b)
[1, 0, 0, 0, 0, 0, 0, 0]
>>> a = [1, 1, 1, 1, 1, 1, 1, 1]
>>> b = [0, 0, 0, 0, 0, 0, 0, 1]
>>> addition_binaire()
[0, 0, 0, 0, 0, 0, 0, 0]
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)