Si l'on dispose de l'écriture décimale d'un entier, une multiplication par 10 de cet entier est facile : on ajoute 0 à la fin de l'écriture décimale.
On dispose maintenant de l'écriture binaire d'un entier. Quel est l'effet de l'ajout d'un 0 à la fin (à droite) de cette écriture ?
Ajouter un zéro à la fin de l'écriture binaire revient à multiplier l'entier par 2.
De façon plus générale, si l'on ajoute un zéro à la fin de l'écriture en base b d'un entier x, on obtient l'écriture en base b de l'entier \( b\times x \).
Soit x un entier ayant pour chiffres xk, xk-1, ..., x1, x0 dans son écriture en base b, c'est à dire : \[ x = x_k \times b^k + x_{k-1} \times b^{k-1} + \dots + x_1 \times b^1 + x_0 \times b^0 \] L'entier \( b \times x \) s'écrit alors : \[ b\times x = x_k \times b^{k+1} + x_{k-1} \times b^{k } + \dots + x_1 \times b^2 + x_0 \times b^1 + 0 \times b^0 \] L'ajout d'un 0 en fin d'écriture correspond donc à la multiplication par b.
Dans le langage python, on dispose d'un opérateur de décalage des bits.
Testez le code suivant :
a=0b101
print(bin(a >> 1))
Essayez avec d'autres valeurs.
En déduire le rôle de l'opérateur >> et expliquer quelle est l'opération arithmétique qui correspond à >> 1.
a>> 1 "pousse" les chiffres binaires de a vers la droite : cela revient à effacer le bit de poids faible.
a>> 1 est égal au quotient de la division entière de a par 2.
En effet, si on a : \[ a = x_k \times 2^k + x_{k-1} \times 2^{k-1} + \dots + x_1 \times 2^1 + x_0 \times 2^0 \] L'effacement du bit \( b_0 \) permet d'obtenir l'entier : \[ a' = x_k \times 2^{k-1} + x_{k-1} \times 2^{k-2} + \dots + x_1 \times 2^0 \] Comme \( 2a'+ x_0 = a \), on constate que \( a' \) est le quotient de la division entière de a par 2.
a >> 2 pousse les bits de deux rangs vers la droite et donne donc le quotient de a par 4=22, a >> 3 pousse les bits de trois rangs vers la droite et donne donc le quotient de a par 8=23...
Pour additionner des entiers écrits en binaire, on procède comme avec l'écriture décimale (en n'oubliant pas les retenues !)
Pour savoir appliquer les retenues, il faut connaître les tables d'addition de deux chiffres et trois chiffres :
Posez les additions suivantes (en restant en base 2).
| a1 | 1 | 0 | 1 | 1 | |||
| a2 | 1 | 1 | 1 | 0 | 1 | 1 | |
| retenue | 1 | 1 | 1 | 1 | 1 | ||
| somme | 1 | 0 | 0 | 0 | 1 | 1 | 0 |
Vous pouvez contrôler votre opération avec python :
bin(0b1011+0b111011)
qui donne :
'0b1000110'
| b1 | 1 | 1 | 1 | 0 | 0 | 0 | |
| b2 | 1 | 1 | 0 | 1 | 1 | 1 | |
| retenue | 1 | 1 | |||||
| somme | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
On suppose que les entiers sont donnés dans leur écriture binaire sous la forme d'une chaîne de caractères
composée de '0' et de '1'.
L'entier 4 sera par exemple donné par '100'.
Écrire un programme python qui prenne en entrée deux entiers naturels donnés sous la forme précédente et qui donne en sortie la somme de ces deux entiers, exprimée sous la même forme.
On s'interdira toute traduction en entier python, la somme devant être programmée en travaillant uniquement sur les caractères constituant les chaînes définissant les deux entiers donnés en entrée.
On définit en premier lieu les fonctions de somme de deux ou trois bits. Le résultat est donné sous la forme d'un couple (tuple) : (bit de poids 21, bit de poids 20).
def sommeDeuxBits(a, b) :
if (a, b) == ('0', '0') : return ('0', '0')
if (a, b) == ('0', '1') : return ('0', '1')
if (a, b) == ('1', '0') : return ('0', '1')
if (a, b) == ('1', '1') : return ('1', '0')
def sommeTroisBits(a,b,c) :
if (a, b, c) == ('0', '0', '0') : return ('0', '0')
if (a, b, c) == ('0', '0', '1') : return ('0', '1')
if (a, b, c) == ('0', '1', '0') : return ('0', '1')
if (a, b, c) == ('0', '1', '1') : return ('1', '0')
if (a, b, c) == ('1', '0', '0') : return ('0', '1')
if (a, b, c) == ('1', '0', '1') : return ('1', '0')
if (a, b, c) == ('1', '1', '0') : return ('1', '0')
if (a, b, c) == ('1', '1', '1') : return ('1', '1')
Pour éviter des problèmes de chaînes de caractères de longueurs distinctes, on écrit une fonction ajoutant des 0 à gauche de l'écriture de la chaîne la plus courte.
def aligne(A, B) :
""" A et B str de 0 et 1 représentants des entiers en binaire.
On ajoute des 0 à gauche du plus court pour qu'ils aient même longueur."""
if len(A)>len(B) : A,B=B,A # échange de A et B éventuel pour que A soit le plus court
d = len(B)-len(A)
for i in range(d) :
A='0'+A
return (A, B)
Il nous reste alors à reproduire l'algorithme d'addition tel qu'on le pratique à la main lorsqu'on pose cette addition.
def sommeDeuxEntiersBin(A, B) :
""" A et B sont des str composés de 0 et 1, représentants en binaire des entiers.
On veut déterminer leur somme, en travaillant bit par bit comme on le ferait à la main."""
A,B = aligne(A, B)
s = sommeDeuxBits(A[-1], B[-1])
somme=s[1]
retenue=s[0]+'0'
for i in range(-2, -len(A)-1,-1) :
s = sommeTroisBits(A[i],B[i],retenue[i])
somme = s[1]+somme
retenue = s[0]+retenue
if retenue[0] == '1' : somme = retenue[0]+somme
return somme
Exemple d'utilisation :
A='111000'
B='110111'
sommeDeuxEntiersBin(A, B)
Lorsqu'un langage ne manipule que des entiers toujours codés sur le même nombre de bits, on peut observer des phénomènes de dépassement de capacités.
On suppose par exemple que tous les entiers (positifs) sont codés sur 4 bits. Que se passe-t-il si l'on cherche à sommer les entiers 1000 et 1000 ?
1000 + 1000 = 1 0000, mais les entiers étant codés sur 4 bits on obtient 0000.
Lorsque la somme de deux entiers n'est pas représentable avec le nombre de bits imposé, si l'on effectue la somme on obtient un résultat faux, il s'agit de l'erreur "dépassement de capacité".
On pourra retenir qu'en machine la somme de deux entiers n'est pas définie pour tout couple d'entiers connu par la machine.
En langage C par exemple, on aura effectivement ce type d'erreurs. Dans un langage comme python, des algorithmes sont mis en oeuvre pour dépasser le nombre de bits par défaut. En python, on peut ajouter des entiers aussi grands que l'on veut (théoriquement bien sûr, la machine reste finie ainsi que le temps accordé à l'exécution !). Avec les nombres de type float, on aura également -- y compris en python -- des problèmes de dépassement de capacités.