Codage d'entiers relatifs

On a vu précédemment comment coder un nombre entier positif en binaire. Mais comment coder $-1$, $2$, $\dots$ ?

I. Première approche

On se place dans le cadre d'un ordinateur pour lequel l'espace alloué au stockage d'un nombre est fixe.

import sys

# Le plus grand entier que python puisse gérer a priori
sys.maxsize

9223372036854775807

# Ce nombre est égal à :
2**63-1

9223372036854775807

Pour simplifier les choses dans un premier temps, imaginons que nos nombre occupents $4$ bits. On peut donc coder $2^4 = 16$ nombres différents.

Une première idée pour coder les nombres positifs et négatifs est d'utiliser le bit de poids fort : si c'est un $0$ on est face à un nombre positif, si c'est un $1$, un négatif :

Commence par $0$	Commence par $1$
$0000_2 = +0 $	$1000_2 = -0$
$0001_2 = +1 $	$1001_2 = -1$
$0010_2 = +2 $	$1010_2 = -2$
$0011_2 = +3 $	$1011_2 = -3$
$ \dots $	$ \dots $

Est-ce satisfaisant ?

• On constate tout d'abord qu'il y a deux codages pour $0$. Ce n'est pas très grave mais pas idéal quand même
• Essayons de faire une addition. Normalement, $+1 + (-1) = 0$:

	0	0	0	1
+	1	0	0	1
	1	0	1	0

Celon nos règles de codages, on obtient $1010_2 = -2$ ! Cela ne va pas du tout... Cette façon de coder n'est donc pas satisfaisante.

II. La bonne méthode

La méthode correcte de codage des entiers relatifs est la suivante (on se place sur $6$ bits) :

• On écrits tous les nombres binaires dans l'ordre
  • $000000$
  • $000001$
  • $000010$
  • $\dots$
  • $111111$

• Les premiers correspondent aux entiers positifs classiques
  • $000000_2 = +0$
  • $000001_2 = +1$
  • $000010_2 = +2$
  • $\dots $

• Lorsque l'on doit basculer le bit de poids fort (le plus à gauche) à $1$ on passe dans les négatifs en commençant par le plus petit possible, ici $-32$, en remontant vers les positifs
  • $011111_2 = +31$
  • $100000_2 = -32$
  • $100001_2 = -31$
  • $100010_2 = -30$
  • $\dots$
  • $111111_2 = -1$

Comme on peut le voir on a donc moins d'entiers positifs que de négatifs. Sur $6$ bits :

• le plus grand entier est $2^{6-1}-1 = 31$

• le plus petit entier est $-2^{6-1} = -32$

Et dans la réalité ? Si l'on utilise $64$ bits :

• le plus grand entier est $2^{64-1}-1 = 9\:223\:372\:036\:854\:775\:807$

• le plus petit entier est $-2^{64-1} = -9\:223\:372\:036\:854\:775\:808$

Remarque : En python, les entiers sont de taille indéfinie, on peut tout à fait dépasser ces valeurs.

Remarque : La fonction bin de python ne gère pas les nombres négatifs. Elle ajoute un signe $-$ devant l'écriture binaire du nombre positif correspondant.

bin(-19)

'-0b10011'

III. Complément à deux

La méthode utilisée pour écrire rapidement les nombres négatifs est celle du complément à deux.

Elle nécessite trois étapes. Pour coder un nombre entier négatif :

• on écrit en binaire sa valeur absolue (son opposé, qui est positif)
• on inverse tous les bits (les $0$ en $1$ et réciproquement)
• on ajoute $1$, en binaire, au résultat

Essayons avec $-19$. On se place dans le cas où les nombres occupent $6$ bits :

• en binaire on a $+19 = 010011_2$
• on inverse tous les bits : $101100$
• on ajoute $1$ au résultat $101101$

On obtient $-19 = 101101_2$. Pour vérifier on additionne $+19 + (-19)$ :

	0	1	0	0	1	1
+	1	0	1	1	0	1
0	0	0	0	0	0	0

On obtient bien $0$ par le jeu des retenues.

Exercice 1 :

Coder en binaire (sur $6$ bits) les nombres suivants :

• $-1$ :

• $-2$ :

• $-9$ :

• $-31$ :

Cette façon de faire va grandement simplifier les soustractions.

En effet soustrait un nombre, c'est additionner son opposé. Or l'addition binaire est facile à faire !

Pour faire $8 - 9$ (sur $6$ bits), on commence par coder $8$ et $-9$ en binaire :

• $8 = 001000_2$
• $-9 = 110111_2$

On fait ensuite l'addition :

	0	0	1	0	0	0
+	1	1	0	1	1	1
	1	1	1	1	1	1

On obtient le dernier nombre possible : $-1$.