Aller au contenu

Écriture binaire d'un entier relatif⚓︎

Rappels⚓︎

  • nous avons déjà vu comment écrire en binaire un nombre entier positif ;
  • un entier relatif est un entier positif ou négatif.

Première approche⚓︎

Soit un entier est positif, soit il est négatif donc il est naturel de stocker le signe de cet entier dans un bit. Ainsi, le bit 1 peut désigner un entier négatif et 0 un entier positif.

Exemple :
1210 = 8 + 4 = 11002 donc +12 peut être représenté sur 5 bits par 01100 et -12 peut être représenté par 11100.

Cependant, cette première approche pose des problèmes :

  • le nombre 0 a deux représentations : 00 et 10 ;
  • 11100 est aussi une représentation binaire du nombre positif 16 + 8 + 4 = 28 : il faut donc définir sur combien de bits nous allons écrire les nombres.

Par exemple, si nous codons les entiers sur 1 octet :

  • le premier bit (celui de gauche) est réservé pour le signe ;
  • les 7 bits restants permettent de coder les nombres ;
  • ceci permet de coder les nombres de -(27-1) = -127 à 27-1 = 127 soit 255 entiers (0 est représenté deux fois) : il y a perte d'un nombre par rapport à la représentation des entiers positifs (256 nombres).

Exercice

Supposons pour simplifier que je choisisse de coder sur trois bits :

  • quelle est la représentation binaire de 3 ?
  • quelle est celle de -3 ?
  • que donne l'addition des deux ?
Réponses

En ignorant le "1" qui sort de la représentation sur 3 bits, il reste 010 donc 2 en décimal. Conclusion : 3 + (-3) = 2 !

Nous voyons donc que cette représentation ne peut pas fonctionner (même en augmentant le nombre de bits)...

Représentation des entiers négatifs avec le complément à 2⚓︎

Supposons que nous codions les entiers sur 3 bits (par exemple si nous travaillions sur une machine antique avec très peu de mémoire !). Alors, lors d'une addition, les retenues qui dépassent cette capacité seraient perdues.

Exercice

Restons sur l'exemple de a = 3 et cherchons comment écrire le nombre b = -3 ; il faut que la somme des deux fasse 0 (ce qui n'est possible qu'avec un 1 qui sort de la capacité de 3 bits) :

011← a
...... ← b
1000 ← c

Cherchez l'écriture binaire de b.

Réponse

En cherchant un peu, nous trouvons b = 101.
Il était possible de convertir les nombres en décimal et de considérer l'opération comme s'il s'agissait d'une addition d'entiers positifs, ainsi
b = c - a = 8 - 3 = 5 = 1012.

Remarquons que c = 10002 est une puissance de 2 (ici 23) et que b = c - a = 23 - a. Autrement dit, b est le complément de a pour arriver à une puissance de 2 ; nous disons que b est le "complément à 2" de a.

Nous allons voir maintenant comment éviter de convertir en décimal.

À retenir

Voici une technique pour obtenir rapidement le complément à 2 sur n bits d'un nombre x :

  • si x est positif, on écrit simplement sa représentation binaire habituelle sur n bits ;
  • si x est négatif :
    • retirer le signe de x, ce qui donne un nombre positif a (la valeur absolue de x) qu'on écrit en binaire sur n bits (pensez à compléter avec des zéros à gauche si nécessaire) ;
    • changer, dans l'écriture binaire de a, tous les 0 en 1 et inversement ;
    • ajouter 1 au résultat.

Exemple : donner une représentation binaire de -1410 avec un complément à 2 sur 5 bits.

Réponse : 1410 = 8 + 4 + 2 = 11102 donc 011102 sur 5 bits ; 01110 → 10001 ; 10001 + 1 = 100102 est une représentation de -1410.

Exercice

Donnez l'écriture binaire sur un octet des entiers relatifs suivants, donnés sous forme décimale :

  • 31
  • -113
  • -59
  • 150

À retenir

  • Si le nombre est positif, il suffit de prendre sa représentation binaire habituelle ; s'il est négatif il faut utiliser le complément à 2 sur la valeur absolue de ce nombre.
  • Dans la technique du complément à deux, le signe est représenté sur le premier bit. Si l'on code sur n bits, il ne reste plus que n-1 bits pour coder la valeur absolue du nombre.
  • Lorsqu'on additionne deux nombres codés sur n bits et qu'il y a une retenue sur le (n+1)ème bit alors cette retenue est perdue.

Attention

  • Il faut nécessairement préciser sur combien de bits se fait la représentation pour le complément à 2.
  • Une même écriture désigne deux nombres différents, l'un positif et l'autre négatif. Ainsi, 1012 peut représenter suivant les contextes le nombre positif 5 ou le nombre négatif -3 avec le complément à 2 sur 3 bits. Pour préciser le contexte, nous dirons si nous parlons d'entiers "non signés" ou d'entiers "signés".

Exercice

  1. Donnez la représentation de -3 en complément à 2 sur 4 bits.
  2. Donnez la représentation de -3 en complément à 2 sur 8 bits.
  3. Un nombre s'écrit 11001110 en complément à 2 sur 8 bits. Quel est ce nombre (en décimal) ?
  4. Un nombre s'écrit 01001110 en complément à 2 sur 8 bits. Quel est ce nombre (en décimal) ?

Plage des valeurs possibles⚓︎

Voici toutes les valeurs permises par le complément à 2 sur 3 bits :

Décimal 0 1 2 3 -4 -3 -2 -1
Binaire 000 001 010 011 100 101 110 111

Nous le voyons, dans cette représentation, les nombres négatifs sont déplacés après les positifs, en effet nous avons vu qu'un nombre négatif b est remplacé par 2n + b.

Exercice

Supposons que je code des entiers relatifs sur 4 bits.

Quel est le plus petit nombre que je peux coder ?

Quel est le plus grand ?

Même questions avec un codage sur un octet.

Réponses

Sur 4 bits : Le plus petit nombre est 10002 qui représente un nombre négatif (le premier bit est 1) donc en soustrayant 1 et en inversant les 0 et les 1 : 1000 - 1 → 0111 → 1000 ce qui représente l'entier positif 8 donc l'entier négatif représenté est -8.

Le plus grand nombre est 01112 qui représente l'entier positif 4 + 2 + 1 = 7.

Sur 1 octet : Le même raisonnement montrerait que l'on peut coder les nombres de -27 = -128 à 27-1 = 127 soit 256 entiers.

plage source de l'image

Exercice

Complétez : avec 32 bits, nous pouvons coder des entiers relatifs allant de ... à ....

À retenir

Avec n bits, il est possible de représenter les entiers allant de -2n-1 à 2n-1-1 soit 2n entiers.

Nombre de bits nécessaires à l’écriture en base2 d’un entier⚓︎

Les entiers sont fréquemment représentés sur 8, 16, 32 ou 64 bits.

Nous nous demandons ici combien de bits sont nécessaires pour représenter un entier donné. Dans le cas des nombres entiers, il faudra préciser si l'on travaille dans un contexte d'entiers signés ou d'entiers non signés.

Pour rappel, avec n bits :

  • avec des entiers non signés je peux représenter les nombres de 0 à 2n-1 ;
  • avec des entiers signés je peux représenter les nombres de -2n-1 à 2n-1-1.

Exemples : combien de bits faut-il pour représenter

  • l'entier non signé 14 ? réponse : 4 bits car 14 ≤ 24-1 = 15 (et 14 > 23-1 = 7) ;
  • l'entier signé 14 ? réponse : 5 bits car 14 ≤ 25-1-1 = 15 ;
  • l'entier non signé 16 ? réponse : 5 bits car 16 ≤ 25-1 = 31 (et 16 > 24-1 = 15) ;
  • l'entier signé 16 ? réponse : 6 bits car 16 ≤ 26-1-1 = 31 ;
  • l'entier signé -38 ? réponse : 7 bits car -38 ≥ -27-1 = -63 (et -38 < -25-1 = -31).

Exercice

  1. Combien faut-il de bits pour écrire l'entier non signé 2427 ?
  2. Combien faut-il de bits pour écrire l'entier signé 2427 ?
  3. Combien faut-il de bits pour écrire l'entier signé -3486 ?

Remarques pour finir :

  • s'il faut n bits pour représenter un nombre A et m bits pour représenter un nombre B alors le nombre de bits maximum :
    • pour représenter A+B sera 1+max(n,m) (1 pour une retenue éventuelle) ;
    • pour représenter A × B sera n + m ;
  • dans beaucoup de langages, il faut définir si l'on veut utiliser des petits entiers ou des grands ; en fonction de cela le nombre de bits réservé est différent.

En Python, cette distinction n'existe plus depuis 2001 et il est donc possible de représenter des entiers de taille arbitraire.

Exercices

  1. "Exercices sur le codage en complément à 2", présents en bas de cette page.
  2. Entraînez-vous pour le prochain DS avec 16 questions sur la "Représentation binaire d'un entier relatif" issues des QCM de la banque nationale de sujets (BNS) (vour y trouverez aussi les corrigés).