Correction de la fiche d'exercice "ÉCRITURE BINAIRE D'UN ENTIER SIGNÉ"

Vous trouverez ici la méthode pour résoudre les exercices de la feuille distribuée.

Pour retenir

Il faut travailler la méthode et pas simplement l'apprendre par coeur. Vous devez l'utiliser sur différents exemples, pas simplement sur un.

Exercice 1

Note

Écrire le nombre –3 en binaire sur 4 bits, puis sur 8 bits.

Ici on vous demande d'écrire un entier signé (avec un -) en binaire. Vous devez donc utiliser l'algorithme du complément à 2 vu en cours.

Représentation d'un entier signé

Pour représenter les nombres signés on utilise la méthode suivante:

• On précise le nombre de bits de la représentation.
• Si l'entier est positif (0 ou plus):
  • On utilise la méthode des entiers non signés (division par deux ou soustraction)
  • On complète avec des 0 à gauche pour atteindre le nombre de bits voulus.
• Sinon on applique la méthode du complément à deux:
  • On code la valeur absolue avec la méthode des entiers non signés. (Ici on code donc 3).
  • On complète avec 0 à gauche pour atteindre le nombre de bits voulus.
  • On inverse tout les bits ($1 \leftrightarrow 0$)
  • On ajoute 1 au nombre obtenu (ATTENTION AUX RETENUES !).

Un exemple

Je veux coder -22 sur 8 bits. Mon nombre final sera donc de la forme BBBB BBBB avec B soit 0 soit 1.

Mon entier est négatif, j'utilise donc le complément à 2.

• Je code la valeur absolue de -22, donc 22
• Avec la méthode des soustractions j'obtiens: $22 = 16 + 4 + 2$ donc $22_{10} = 10110_{2}$.
• Je complète avec des 0 pour obtenir 8 bits: $0001\quad0110$.
• J'inverse tout les bits: $1110\quad1001$.
• J'ajoute 1 au nombre obtenu en faisant attention à la retenue: $1110\quad1001 + 1 = 1110\quad1010$.
• Donc $-23$ s'écrit $1110\quad1010$ en binaire signé.

Exercice 2

Note

Écrire les nombres ci-dessous en binaire sur 8 bits. Puis faire la somme des deux nombres binaires obtenus et vérifier que l'on retrouve bien 0.

• 7 et -7
• 31 et -31
• 72 et –72

Ici on nous demande trois choses:

1. Écrire en binaire un entier non signé (Voir les méthodes de division et soustraction du cours).
2. Écrire en binaire un entier signé (Voir exercice précédent).
3. Faire l'addition sur 8 bits de deux entiers binaires.

Pour la troisième étape, on utilise l'algorithme d'addition binaire habituel, avec la table de vérité suivante.

Table de vérité pour l'addition de deux bits avec une retenue

Bit en haut	Bit en bas	Retenue ?	Résultat	Retenue sur le prochain bit ?
0	0	Non	0	Non
0	0	Oui	1	Non
0	1	Non	1	Non
1	0	Non	1	Non
1	1	Non	0	Oui
1	0	Oui	0	Oui
0	1	Oui	0	Oui
1	1	Oui	1	Oui

En résumé, parmi les trois bits (haut, bas, retenue):

• Si on a un seul bit à 1 le résultat est 1 sans retenue.
• Si on a deux bits à 1, le résultat est 0 avec une retenue de 1
• Si on a trois bits à 1, le résultat est 1 avec une retenue de 1.

Pour cet exercice, il faut aussi faire attention au résultat final qui est sur 8 bits. On enlèvera donc le 9eme bit (le plus à gauche) pour bien obtenir le 0.

Un exemple

Je réponds pour le couple 7,-7.

Pour écrire 7 en binaire: $7 = 4 + 2 + 1 = 111_{2} = 0000\quad 0111_{2}$

Pour écrire -7 en binaire:

• On repart de l'écriture de $7_{10} = 0000\quad0111_{2}$.
• On inverse tout les bits: $1111\quad1000$.
• On ajoute 1 : $1111\quad1001 = -7_{10}$.

On fait ensuite l'addition (^1 représente une retenue de 1):

📋 Texte

     ^1 0^1 0^1 0^1 0^1 0^1 1^1 1^1 1
    +   1   1   1   1   1   0   0   1
    -----------------------------------
     1  0   0   0   0   0   0   0   0

On ne prend pas en compte le 1 qui est le 9eme bit, le résultat est donc bien 0.

Exercice 3

Note

Pour chacun des entiers binaires signés ci-dessous, déterminer l’opposé, puis l'opposé de l'opposé et vérifier que l'on retrouve bien le nombre binaire de départ.

1. 0011, 1011, 1111 ...

Ici on nous demande de calculer l'opposé d'un entier binaire signé. Pour cela, on a juste à calculer son complément à deux à partir de la représentation binaire, c'est à dire:

1. Inverser tout les bits ($1 \leftrightarrow 0$)
2. Ajouter 1 au résultat.

Pour l'opposé de l'opposé, il suffit donc de refaire l'opération sur la chaîne binaire obtenue et de vérifier que l'on obtient bien le nombre de départ.

Exemple avec 0011

On calcule l'opposé de 0011:

• Inversion des bits: 1100.
• Ajout de 1 : 1101.

On calcule ensuite l'opposé du nombre obtenu : 1101

• Inversion des bits : 0010.
• Ajout de 1 : 0011

On obtient bien le nombre initial.

Donc l'opposé de l'opposé est bien le nombre initial, donc le complément à deux se comporte bien comme une soustraction.

Exercice 4

Note

Convertir en décimal les nombres binaires ci-dessous qui sont signés et codés sur un octet :

1. 11111111, 00000110, 11111110 ...

Ici on nous demande la valeur décimale d'un octet binaire signé. On doit donc appliquer la méthode du complément à deux à l'envers.

Pour cela, on suit la méthode suivante:

Si le nombre commence par 0, l'entier est positif, donc on convertit avec la méthode habituelle (Écriture dans le tableau des $2^n$.

Sinon, l'entier est négatif on doit donc trouver sa valeur absolue. Pour cela on calcule son opposé avec le complément à deux.

Exemple avec 11111111

Le nombre commence par 1, il est donc négatif on doit donc calculer son complément à 2.

• On inverse tout les bits ce qui donne 00000000
• On ajoute 1, ce qui donne 00000001

La valeur absolue de 11111111 est donc $1\times2^0=1_{10}$, donc 11111111 vaut -1 car c'est un nombre négatif dont la valeur absolue vaut 1.

On pourra vérifier nos résultats à l'aide de ce site

Exercice 5

Ici on nous demande encore de calculer la valeur décimale de nombres signés et codés.

La seule étape en plus par rapport à l'exercice précédent est de passer de l'hexadécimal au binaire.

Pour cela on utilise la table ci dessous:

Hexa	Binaire	Hexa	Binaire
0	0000	8	1000
1	0001	9	1001
2	0010	A	1010
3	0011	B	1011
4	0100	C	1100
5	0101	D	1101
6	0110	E	1110
7	0111	F	1111

Exemple avec A1

On convertit A1 en binaire: 1010 0001. Le nombre commence par un 1, il est donc négatif on calcule sa valeur absolue:

• Inversion des bits: 0101 1110
• Ajout de 1: 0101 1111
• Calcul de la valeur absolue: $0\times 128 + 1\times 64 + 0\times 32 + 1\times 16 + 1\times 8 + 1\times 4 + 1\times 2 + 1\times 1 = 64+16+8+4+2+1 = 95$

Donc A1 représente -95.

Exercice 6

C'est exactement le même que l'exercice précédent avec des nombres sur 16 bits, on applique donc la même méthode.

Exemple avec 8000

• En binaire: 1000 0000 0000 0000
• Inversion: 0111 1111 1111 1111
• Ajout de 1: 1000 0000 0000 0000
• Calcul de la valeur absolue: $1\times 2^{15} + 0 = 32768$

Donc $8000_{16}$ représente -32768 en décimal.

Exercice 7

Ici on commence par calculer l'addition, comme vu à l'exercice 2. Cela nous donne comme résultat: 1111 0100

On nous demande ensuite ce à quoi cela correspond si les nombres sont non signés, pour cela on doit convertir les trois nombres en décimal non signé. Pour cela on fait juste la conversion habituelle avec le tableau des $2^n$.

Pour la dernière question, on doit de nouveau convertir les trois nombres en décimal signé. Pour cela on remarque que:

• 00100110 commence par 0, c'est donc un nombre positif (méthode du tableau)
• les deux autres commencent par un 1, on applique donc la méthode des exercices 4,5,6.

À la fin on doit obtenir des additions en décimal cohérentes (La somme du premier et second nombre doit bien donner le troisième).

Exercice 8

On retrouve ici l'exercice 4 mais avec un entier de 16 bits. Le résultat final est: -9867 pour le premier et -32531 pour le deuxième.

Exercice 9

Le cas d'un entier non signé

On a vu dans le cours sur les entiers non signés que pour diviser par 2 un nombre positif non signé en binaire, il suffit de le décaler d'un rang vers la droite.

Justification sur 4 bits

Un nombre binaire $b_3b_2b_1b_0$ représente le nombre décimal: $b_3 \times 2^3 + b_2 \times 2^2 + b_1 \times 2^1 + b_0 \times 2^0$. Si on le divise par 2 on obtient: $b_3 \times 2^2 + b_2 \times 2^1 + b_1 \times 2^0 (+ b_0 \times 2^-1)$. Comme on est sur une division entière, on supprime le terme $b_0 \times 2^-1$ qui vaut soit 0 soit $1/2$.

Si on décale d'un rang vers la droite notre nombre original on obtient bien: $0b_3b_2b_1 = 0 \times 2^3 + b_3 \times 2^2 + b_2 \times 2^1 + b_1 \times 2^0 = b_3 \times 2^2 + b_2 \times 2^1 + b_1 \times 2^0$.

Le cas d'un entier signé

On observe ici que faire la même opération ne suffit pas, en effet on perd le bit de signe et la valeur n'a pas vraiment de lien.

Si on observe une valeur et sa moitié en complément à deux on peut cependant observer une propriété intéressante:

Exemple avec -92

-92 se code en binaire signé : 1010 0100. La moitié de -92 est -46 qui se code : 11010010

Si on les écrit l'un au dessus de l'autre on obtient:

📋 Texte

11010010  = -46
 10100100 = -92

Pour passer de -92 à -46, on doit donc décaler d'un rang vers la droite (supprimer le bit le plus à droite) et rajouter le bit de signe devant (ici 1).

Décalage arithmétique versus Décalage logique

Cette seconde opération (décaler + ajout du bit de signe) est nommé le décalage arithmétique. La première qui consiste juste à rajouter un 0 au lieu du bit de signe est le décalage logique. Pour en savoir plus : Wikipédia

Exercice 10

Pour la question 1, on utilise la méthode des exercices 1 et 2 sans se limiter en nombre de bits. C'est à dire que l'on ne va pas supprimer les bits au delà du 8eme.

Donc pour coder -279 :

• On code 279 : 1 0001 0111
• On inverse : 0 1110 1000
• On ajoute 1 : 0 1110 1001

Ici on voit que le dernier bit (n° 9) n'est pas à 1 alors que l'on veut coder un entier négatif. On doit donc pour trouver le codage:

• Coder 279 avec 1 bit de plus au début (à 0)
• Inverser le codage obtenu
• Ajouter 1
• Si le résultat obtenu commence par un 1, on a fini et on peut compter
• Sinon, on recommence à la première étape.

Finalement, le codage de -279 en complément à deux est: 10 1110 1001

Pour la question 2, on peut essayer de coder -128 sur 8 bits (un octet) avec la méthode du complément à deux:

• On code 128 (valeur absolue) en non signé: 1000 0000
• On inverse tout les bits : 0111 1111
• On ajoute 1 : 1000 0000

Le nombre obtenu tient bien sur un octet et commence par un 1, donc -128 est codable sur un octet.

Exercice 11

On a vu dans le cours que sur $n$ bits on peut coder l'intervalle signé $-2^{n-1}; +2^{n-1} - 1$. Il suffit donc de réutiliser la formule.

Pour la retrouver, on peut remarquer le plus grand entier positif sur n bits se code toujours: 0111 ... avec $n-1$ 1, ce qui correspond à $1000... -1$ donc $2^{n-1} -1$ car le 1 est situé sur le $n$-ième bit.

Pour le plus petit entier négatif, on sait que 1111.... correspond toujours à -1, il s'agit donc de 1000.... Pour trouver sa valeur absolue, on fait le complément à 2 qu'on interprète comme nombre positif:

• Inversion de tout les bits: 01111....
• Ajout de 1: 10000... (avec la retenue tout les bits à 1 s'annule et le dernier passe à 1).

Il s'agit donc de $-2^{n-1}$ car le $n$-ième bit est à 1.

Exercice 12

Le cercle va aller de 0000 jusqu'à 1111 (nombres binaires sur 4 bits). Pour écrire la valeur non signée, on utilise la méthode du tableau des $2^n$. Pour la valeur valeur signée, on utilise la méthode du complément à 2 (exercice 3).

La valeur correspondante à 0000 est 0 dans les deux cas. Les valeurs pour 1111 sont : 15 en non signé et -1 en signé.

On pourra observer que en arithmétique signée, on revient vers le 0 car les codes donnent dans l'ordre : 0,1,2...,7,-8,-7,...,-2,-1.

Exercice 13

On sait que sur 4 bits on peut stocker les entiers signés entre -8 et 7. De plus on sait que les entiers négatifs sont stockés $2^4-x$ (avec x la valeur absolue de l'entier (sans le signe).

On peut donc écrire le script suivant (qui marche pour n'importe quel nombre de bits), utilisant la fonction native $bin$:

🐍 Script Python

n = 4
for nombre in range(-(2**(n-1)),2**(n-1)):
    if nombre < 0 :
        nombre_complement = 2 ** n + nombre #+ car nombre est déjà négatif
        print(bin(nombre_complement))
    else:
        print(bin(nombre))

Exercice 14

Un script utilisant les compréhensions de listes peut être:

🐍 Script Python

def mon_complement(nb_en_chaine):
    return [ '0' if bit == '1' else '1' for bit in nb_en_chaine]

La version déroulée étant:

🐍 Script Python

def mon_complement(nb_en_chaine):
    chaine_inversee = ''
    for bit in nb_en_chaine:
        if bit == '1':
            chaine_inversee.append('0')
        else:
            chaine_inversee.append('1')
    return chaine_inversee

Une version avec un tableau de caractère :

🐍 Script Python

def mon_complement(nb_en_tab):
    tab_inverse = ['']*len(nb_en_tab)
    for indice in range(len(nb_en_tab)):
        if nb_en_tab[indice] == '0':
            tab_inverse[indice] = '1'
        else:
            tab_inverse[indice] = '0'
    return tab_inverse

Exercice 15

Ici on doit juste coder l'addition de 1 à une chaine binaire. On suppose l'utilisation de la version avec un tableau de caractères.

🐍 Script Python

def complement_a_2(nb_en_tab):
    nb_ca1 = mon_complement(nb_en_tab) #nombre inversé
    resultat = ['0'] * 8 #On a dit sur 8 bits
    # Si le bit à droite (dernier bit ici) est à 1
    if nb_ca1[7] == '1':
        retenue = '1' #On a une retenue de 1 car 1 + 1 = 0 avec une retenue de 1
        resultat[7] = '0'
    else: # Sinon on a une retenue de 0 car 0+1 donne 1 sans retenue
        retenue = '0'
        resultat[7] = '1'
    for i in range(len(nb_ca1)-2,-1,-1): # Pour parcourir le tableau à l'envers
    # Sans accéder au dernier élément (déjà calculé)
        if nb_ca1[i] == '0' and retenue == '0':
            resultat[i] = '0'
            retenue = '0'
        elif nb_ca1[i] == '0' and retenue == '1':
            resultat[i] = '1'
            retenue = '0'
        elif nb_ca1[i] == '1' and retenue == '0':
            resultat[i] = '1'
            retenue = '0'
        else: #nb_ca1[i] == '1' et retenue == '1'
            resultat[i] = '0'
            retenue = '1'
    return resultat

On peut simplifier ce script en remarquant qu'il suffit de commencer avec une retenue à 1 au lieu de la pré calculer.

Les conditions booléennes sont aussi simplifiables avec des or et en isolant celles qui donnent le même résultat dans le else.