Représentation des nombres


Représentation interne des nombres dans un ordinateur

Notion de bit

Un ordinateur est un appareil fonctionnant à laide de circuits électroniques, pour lesquels ils est plus simple de distinguer deux états (absence ou présence dun courant électrique) que plusieurs. Ce système à deux états donc binaire permet en outre de tolérer de légères approximations de mesures.

Ces deux mesures correspondent à 0 (absence de courant) ou 1 (présence de courant). Ces deux chiffres sont les chiffres binaires que lon abrège en bit (pour binary digit).

Regroupement de bits

Si toute les données dans un ordinateur peuvent in fine se représenter par une suite de 0 ou de 1, on regroupe néanmoins ces chiffres binaires en paquets de bits pour des questions de commodité mais aussi defficacité.

  • Le plus petit regroupement utilisé dans les ordinateurs modernes et le paquet de 8 bits, surnomé octet en français (ou byte en anglais, à ne surtout pas confondre avec bit qui, soit dit en passant, ne se prononce pas du tout de la même façon).
  • Les octets sont ensuites regroupés en mots machines (abrégés le plus souvent en *mots**) de taille variable, valant généralement 2 octets (16 bits), 4 octets (32 bits) ou bien 8 octets (64 bits). Lorsque lon parle dun ordinateur 32 bits ou 64 bits, cela signifie quils sont capable de physiquement traiter des paquets de bits de la taille correspondante pour effectuer des opérations (additions, multiplications, etc).

Encodage dun nombre

Nous verrons un peu plus loin comment ces mots machines permettent de représenter des données plus complexes que 0 ou 1, notamment des entiers naturels ou relatifs (mais pas uniquement).

Cela nécessite cependant de trouver un moyen de traduire tout entier naturel en une suite plus ou moins longue de bits: on appelle cela un encodage.

Écriture en base 10

Avant de nous intéresser à la représentation des entiers sous forme binaire, commençons par regarder dun peu plus près comment sont représentés les nombres pour les êtres humains.

Toutes les sociétés utilisent depuis quelques millénaires la base 10, encore appelée représentation décimale des entiers (historiquement, ce nétait pas toujours le cas: les mayas utilisaient par exemple le système vicésimal de base 20, les babyloniens le système sexagésimal de base 60 qui nous est dailleurs resté pour les minutes/secondes ou certains calculs dangles en degrés).

Les nombres entiers sont représentés en base 10 par une suite de chiffres décimaux (il y en a exactement 10, compris entre 0 et 9). Supposons quun entier naturel \(N\) y ait \(n + 1\) chiffres \(a_n, a_{n-1}, \ldots, a_2, a_1, a_0\)\(a_0\) correspond au chiffre des unités, \(a_1\) au chiffre des dizaines, etc.

Il est alors possible de reconstituer le nombre de départ, en constatant que

\[ N = a_n\times 10^n + a_{n-1}\times 10^{n-1} + \cdots + a_2\times 10^2 + a_1\times 10^1 + a_0\times 10^0\]

On dit que le nombre \(10^k\) que lon multiplie à \(a_k\) est le poids de \(a_k\). Le chiffre \(a_n\) est dit de poids fort car il est multiplié à la plus grande puissance de 10. À linverse, le chiffre des unités \(a_0\) est appelé chiffre de poids faible.

Exemple: Prenons \(N = 30\,728\)

On a bien:

\[ \begin{align*} 30\,728 & = 30\,000 + 700 + 20 + 8 \\ & = 3\times 10^4 + 0\times 10^3 + 7\times 10^2 + 20\times 10^1 + 8\times 10^0 \end{align*}\]

Il est possible de démontrer mathématiquement (cest un théorème) quà tout nombre entier \(N\) est associé une unique séquence de chiffres donnant la représentation décimale. Inversement, étant donné une séquence de chiffres décimaux, on peut toujours calculer un unique nombre entier par la formule ci-dessus.

Écriture en base 2

Écriture binaire

On peut se demander à juste titre si le nombre 10 du paragraphe précédent joue un rôle particulier: en réalité, il nen est rien. Les humains comptent très vraissemblablement en base 10 pour une raison physiologique évidente (il suffit de compter le nombre de doigts sur les deux mains). Mais la base 20 est toute aussi naturelle (si on compte les doigts des mains et des pieds)

Les ordinateurs étant très fortement liés au bits comme nous lavons vu un peu plus haut (cest un peu comme si un ordinateur navait quun seul doigt pour compter), on peut naturellement se demander si le théorème mathématique précédent reste valable en base 2. Et cest effectivement le cas !

La différence est que les chiffres seront bien évidemment des chiffres binaires, autrement dit des bits. Lautre différence est que lon nutilise plus des puissances de 10 mais plutôt des puissances de 2.

Exemple: Quel est le nombre dont la représentation en base 2 est 1101011 ?

Il est possible de généraliser lexemple précédent: à toute suite de \(n + 1\) bits \(b_n, b_{n-1}, \ldots, b_2, b_1, b_0\) on peut associer un nombre entier de manière unique par la formule

\[ N = b_n\times 2^n + b_{n-1}\times 2^{n-1} + \cdots + b_2\times 2^2 + b_1\times 2^1 + b_0\times 2^0\]

Regroupement en octets et en mots

Un octet étant un regroupement de 8 bits, il permet de représenter tout entier comportant au plus 8 chiffres binaires. Le plus grand entier que lon peut ainsi représenter par un octet est

\[ \begin{align*} 11111111_2 & = 2^7 + 2^6 + \cdots + 2^1 + 2^0 \\ & = 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 \\ & = 255 \end{align*}\]

La plus petite valeur étant 0, il est donc possible de représenter 256 valeurs (entre 0 et 255) à laide dun octet.

Remarque: Lindice 2 dans \(11111111_2\) permet de ne pas confondre un nombre dont la représentation est en binaire dun nombre décimal. On peut utiliser \(135_{10}\) lorsque lon veut préciser que la représentation est décimale, mais il est plus simple de convenir quen labsence dinformation sur la base, un nombre est décimal.

Notons aussi que légalité précédente na de sens que si lon considère le membre de gauche comme une représentation binaire dun nombre.

Nous verrons un peu plus loin que python a une autre manière de distinguer entre les nombres binaires et les nombres décimaux.

Exercice 1: Expliquer cette blague de programmeur: « Il y a 10 catégories de personnes: celles qui savent compter en binaire et celles qui ne savent pas»

Exercice 2: Donner la représentation décimale des entiers dont les représentations binaires sont 11001100, 10101010 et 1010010011110010.

Exercice 3: Quelle est le plus grand entier que lon puisse représenter sur 16 bits ? Sur 32 bits ? Sur 64 bits ?

Le théorème cité plus haut sur lunicité de la représentation décimal dun entier naturel est aussi valable pour la représentation binaire: un entier naturel \(N\) admet une unique représentation en base 2: il existe donc une seule séquence de bits permettant de représenter \(N\) dans cette base.

Exemple: Considérons lentier naturel 94 (représentation décimale puisquil ny a aucune indication du contraire). Quelle est sa représentation binaire ?

Il suffit de décomposer 94 en somme de puissances de 2, en nutilisant quune seule fois (au plus) chaque puissance. Le théorème précédent nous garantit que cela est non seulement toujours possible, mais quil ny a quune et une seule manière de le réaliser.

Un moyen algorithmique simple de trouver cette décomposition est de partir de la plus grande puissance de 2 inférieure ou égale à 94 (cest donc 64) et de procéder ensuite par soustractions successives.

  • Comme \(64 < 94\), on calcule \(94 - 64 = 30\);
  • La plus grande puissance de 2 inférieure ou égale à 30 est 16. On calcule alors \(30 - 16 = 14\);
  • On a ensuite \(14 - 8 = 6\);
  • Puis \(6 - 4 = 2\);
  • Et enfin \(2 - 2 = 0\).

On vient donc de déterminer que \(94 = 64 + 16 + 8 + 4 + 2\), ce qui donne la représentation binaire 1011110.

Exercice 4: Donner la représentation en base 2 sur 8 bits des entiers 13, 135, 62 et 248.

Représentation des entiers naturels en python

Python étant un langage informatique, les nombres sont bien sûr représentés de manière interne en binaire par lordinateur. Cependant, il faut bien distinguer la représentation interne (qui nest en général pas visible) de la manière dafficher un nombre dans un terminal.

Par défaut, python lit et affiche les nombres en base 10.

>>> 123
123

On peut saisir des nombres en base 2 en les préfixant par 0b:

>>> 0b10110111
183

Notons que python ne garde pas en mémoire le fait quun nombre ait été lu sous forme binaire: un nombre est un nombre, peu importe la base dans laquelle on la lu, ni dailleurs la base dans laquelle on souhaite lafficher.

Il est possible de déterminer la représentation binaire dun entier par la fonction bin(entier) dont le résultat est une chaîne de caractère:

>>> bin(123)
'0b1111011'

Attention: Il ne faut surtout pas confondre la chaîne de caractères '0b1111011' avec le nombre 0b1111011 que python stockera en binaire (puis affichera ensuite) comme lentier 123 en base 10.

Remarque: Quelle que soit larchitecture de lordinateur utilisé (probablement 64 bits de nos jours, mais parfois encore 32 bits), les entiers sont représentés de manière spéciale par python (nous ne préciserons pas comment), et permettent de représenter des nombres de taille arbitraire (la seule limite est la taille de la mémoire). Notons que, quels que soient les détails de cette représentation interne, en dernier ressort lordinateur utilisera toujours des bits. Voici par exemple la représentation décimale et binaire de 31000:

>>> n = 3**1000
>>> n
132207081948080663689045525975214436596542203275214816766
492036822682859734670489954077831385060806196390977769687
258235595095458210061891186534272525795367402762022519832
080387801477422896484127439040011758861804112894781562309
443806156617305408667449050617812548034440554705439703889
581746536825491613622083026856377858229022841639830788789
691855640408489893760937324217184635993869551676501894058
810906042608967143886410281435038564874716583201061436613
2173102768902855220001
>>> bin(n)
'0b111110010110111010000000100010011010100110110100110001
011100000100100000011000001110100111010100010010110011011
001011100101111011110100011000100111100110001011011110000
110001011011100110111101001011111001010100010000001001100
001101000110010111000011111101001100111110110101000101110
010010000001100010010110000101111110110101111001000110000
011100000111000010001101010010001011111101110110000001010
001001101110100111000111011101010110001100100101101110001
010000111001010011100100101000001111110110010001000001101
001010001000010011011011010000100100000101001111101001101
001000001101011000111111001100001101010011001110001011011
100100011101000000100101110011011101010001100111111100010
000011101101111110101100100011100110011000100110101101000
101100011010110001011001011101110100011110010010111100110
100001011010110010110000110111001110110100010101001100001
000101101111010001111001110101011000111010111010010111101
101100001010101100110100000001100001011011000011010110000
010010011010001101101100000101000100011110000010000000010
000111101010001111101100011100010101000000011000111010110
111011101111000000010010001001010101100111101111100000001
011100011110111010101001001011000011010010011001000011110
101101111001011001110110100100010001100100000111011001100
001010000101011010011000000110111010011100000101111010100
011100111101010110110110011100000011001011011110100101010
000001001000111100110010100100111001110111000100001011101
100000010000011010010000011000110001100010010010100000011
000101011011110111100001100111110110111110010101100001011
0100100110111101111010011101110000101101100100001'

Notons quen python, lopérateur délévation à la puissance (appelé exponentiation en mathématiques) se note à laide dune double multiplication **.

Cette souplesse offerte par le langage python est relativement inédite et nexiste quasiment dans aucun autre langage de programmation (en dehors de ceux généralement dédiés aux mathématiques formelles). En général, les variables contiennent des entiers dont le nombre de bits est fixé à lavance (8, 16, 32, 64 ou 128 pour la plupart des langages courants).

Algorithmes de conversion entre binaire et décimal

Bien que python offre déjà toutes les facilités pour convertir vers et depuis le binaire, il est important de bien comprendre les algorithmes sous-jacents et aussi de savoir les implémenter en python.

Le premier algorithme présenté permet de déterminer la représentation binaire dun entier (donné initialement sous forme décimale) en utilisant la même méthode que celle utilisée «à la main» un peu plus haut dans lexemple et lexercice correspondant.

Le second réalise la même tâche mais selon une méthode diamétralement différente. Il a lavantage dêtre finalement plus simple et plus court. Il est aussi plus efficace (bien que cela nait guère dimportance en pratique sur des nombres comportant peu de chiffres).

Enfin, le dernier algorithme présenté réalise la tâche inverse, à savoir déterminer un nombre entier à partir de sa représentation en base 2.

Conversion décimal \(\rightarrow\) binaire

Lorsque lon a cherché une représentation en base 2 dun entier donné, on a plus ou moins procédé comme suit:

Déterminer la plus grande puissance de 2 inférieure ou égale à N. Notons-la P.

Tant que P est positif faire:
    Si P est inférieur ou égal à N alors:
        Afficher 1
        Soustraire P à N
    Sinon:
        Afficher 0
    Diviser P par deux (division euclidienne)

La première partie de lalgorithme peut (et doit) elle même être précisée, comme suit:

P prend la valeur 1
Tant que 2P est inférieur ou égal à N faire:
    P prend la valeur 2P

Tant que P est positif faire:
    Si P est inférieur ou égal à N alors:
        Afficher 1
        Soustraire P à N
    Sinon:
        Afficher 0
    Diviser P par deux (division euclidienne)

À la sortie de la boucle, \(P\) sera la plus grande puissance de 2 inférieur ou égal à \(N\), excepté si \(N = 0\): lalgorithme ne fonctionne dailleurs pas dans ce cas là, puisquaucune des deux boucles nest exécutée. Il faudra traiter le cas nul à part.

Remarquons aussi que cet algorithme réalise la même chose que la fonction bin(nombre) préexistance en python.

Exercice 5: Implémenter lalgorithme précédent en python, sous la forme dune fonction bin1(nombre) prenant pour paramètre un entier naturel et renvoyant en valeur de retour une chaîne de caractère contenant la représentation binaire correcte du nombre. Dit plus simplement: la fonction bin1() doit réaliser exactement la même chose que la fonction bin() de python.

Attention: La fonction bin1(nombre) a pour vocation de renvoyer une valeur, elle ne devra rien afficher dans la console (sauf éventuellement durant la phase de mise au point)

En python il existe deux opérateurs de division: le simple slash / est une division «à virgule»: son résultat est toujours un nombre à virgule flottante (donc une valeur approchée) même si mathématiquement il sagit dun entier.

>>> 4 / 5
0.8
>>> 4 / 2
2.0

Nous aurons ici davantage besoin dune division euclidienne (cest-à-dire la division telle quaprise à lécole primaire, avec dividende et reste). Lopérateur double-slash // sert à cela, et son résultat est toujours un entier.

>>> 4 // 3
1
>>> 4 // 2
2

On peut calculer le reste dune division euclidienne grâce à lopérateur % (quil ne faut surtout pas confondre avec un pourcentage même sil sagit du même caractère. Il se prononce modulo en mathématiques):

>>> 4 % 3
1
>>> 4 % 2
0

Quelques outils sur les chaînes de caractères qui nont pas encore été étudiées cette année: Une chaîne de caractère est indifféremment entourée dapostrophes ' ou bien de guillemets anglais " (à ne pas confondre avec des doubles apostrophes). On peut rajouter des caractères avant ou après une chaîne de caractères à laide de lopérateur + qui sert alors de concaténation et non pas daddition:

>>> s = "mot"
>>> s + "-suffixe"
'mot-suffixe'
>>> 'préfixe-' + s
'préfixe-mot'
>>> binaire = "1011"
>>> binaire = "00" + binaire + "01"
>>> binaire
'0000001011010101'
>>> "0b" + binaire
'0b0000001011010101'

Un algorithme plus efficace

Lalgorithme précédent déterminait la représentation binaire dun entier de la gauche vers la droite, cest-à-dire du bit de poids fort vers le bit de poids faible.

Lalgorithme présenté ici procède exactement à linverse: il détermine dabord le bit de poids faible, puis procède de la droite vers la gauche.

Cet algorithme est basé sur quelques remarques très simples:

  • Le bit de poids faible dun nombre représenté en binaire (cest-à-dire celui situé le plus à droite ou encore le bit des unités) permet de savoir si un entier est pair ou impair: si ce bit est 0, alors lentier est pair, sinon il est impair. En inversant largument précédent, il est donc aisé de déterminer le bit de poids faible en testant si un nombre est divisible par deux ou non. On utilise pour cela lopérateur % de python donnant le reste dune division euclidienne.
  • Une fois que lon a déterminé le bit de poids faible, il suffit de recommencer pour les bits situés plus à gauche, en décalant le tout vers la droite. Un décalage vers la droite en binaire correspond exactement à une division euclidienne par deux (cest léquivalent dune division par 10 en décimal qui elle aussi revient à décaler les chiffres décimaux dun cran vers la droite).

On obtient alors lalgorithme suivant:

Tant que N est strictement positif faire:
    Si N est pair alors:
        Afficher 0
    Sinon:
        Afficher 1
        N prend la valeur N moins 1
    N prend la valeur N divisé par 2

Remarquons que cet algorithme affiche les bits à lenvers: pour éviter cet inconvénient, on créera plutôt une chaîne de caractère pour laquelle il sera facile dordonner les bits correctement (en effet, on peut toujours décider dajouter un caractère soit devant ou soit derrière une chaîne existante, selon ce que lon cherche à obtenir).

Il est possible de détailler davantage le test de la conditionnelle:

Tant que N est strictement positif faire:
    Si N % 2 == 0 alors:
        Afficher 0
    Sinon:
        Afficher 1
        N prend la valeur N moins 1
    N prend la valeur N divisé par 2

En effet, dire que \(N\) est pair équivaut à dire que le reste de la division euclidienne de \(N\) par 2 vaut 0, ce qui se traduit en python par N % 2 == 0.

Exercice 6: Implémenter lalgorithme précédent en python, sous la forme dune fonction bin2(nombre) prenant pour paramètre un entier naturel et renvoyant en valeur de retour une chaîne de caractère contenant la représentation binaire correcte du nombre. Dit plus simplement: la fonction bin2() doit réaliser exactement la même chose que la fonction bin() de python ou que la fonction

bin1() précédente, mais avec un algorithme différent. !

Remarquons en passant que lon observe un des aspects importants des fonctions ici: il est impossible de deviner quel algorithme a été utilisé pour réaliser la tache assignée à la fonction en regardant simplement les paramètres et la valeur de retour. Dailleurs, ce nest pas souhaitable: on peut vouloir remplacer un algorithme par un autre, plus performat, à tout moment, sans quil soit pour autant nécessaire de modifier le reste du programme.

Conversion binaire \(\longrightarrow\) décimal

Lalgorithme permettant de convertir un nombre donné en base 2 vers un nombre décimal est conceptuellement plus simple: il revient simplement à réaliser le calcul:

\[ N = b\_n\times 2^n + b{n-1}\times 2^{n-1} + \cdots + b\_2\times 2^2 + b\_1\times 2^1 + b\_0\times 2^0\]

à partir des bits \(b_k\).

Exercice 7: Implémenter cet algorithme précédent en python, sous la forme dune fonction décimal(chaîne) prenant pour paramètre une chaîne de caractère ne contenant que des 0 et des 1 (aucun test ne sera effectué pour sen assurer) et renvoyant en valeur de retour lentier correspondant.

Utilisation des bases 8 et 16 en informatique

Pourquoi utiliser la base 8 (octale) ?

Les informaticiens ont beaucoup utilisé historiquement les nombres écrits en base 8 (donc nutilisant que les chiffres de 0 à 7) car il faut exactement 3 bits pour coder un nombre compris entre 0 et 7: cela permettait de regrouper les bits par paquets de 3.

Par exemple, le nombre 113 sécrit 1110001 en binaire. En regroupant les bits par paquets de 3 (en partant du bit de poids faible, cest-à-dire le plus à droite), on obtient (001)(110)(001), où on a rajouté 2 zéros à gauche pour compléter. Chaque paquet de 3 bits, pris séparément, correspond à un chiffre entre 0 et 7: ici, le nombre 113 sécrit en octal 161.

On peut le vérifier en python:

>>> oct(113)
'0o161'

On constate que la représentation dun nombre octal en python est préfixée par 0o, ce qui est cohérent avec le préfixe 0b pour le binaire.

Inversement, si on considère le nombre \(715_8\), il est aisé de le convertir en décimal. Deux solutions soffrent à nous:

  • On utilise la formule

    \[ 715\_8 = 7\times 8^2 + 1\times 8^1 + 5\times 8 = 461\]

  • On passe par le binaire: chaque chiffre octal nous donne un paquet de 3 bits:

    \[ 715\_8 = (111)(001)(101)\_2 = 461\]

    Cela nécessite une étape supplémentaire (conversion du binaire vers le décimal), mais les calculs sont bien plus aisé à réaliser à la main.

De nos jours, la base octale nest plus guère utilisée en informatique, bien quon en trouve des traces. Lidée sous-jacente est cependant excellente: regrouper des bits par paquets faciles à compter à la main.

Il est naturel dimaginer un regroupement de bits plus propice à linformatique (où on a à gérer des octets, des mots sur 16, 32 ou 64 bits): on regroupe alors naturellement les bits par paquets de 4, ce qui nous amène à la notion dhexadécimal.

Les nombres hexadécimaux

En hexadécimal, on regroupe les bits par paquets de 4. Il y a donc \(2^4 = 16\) chiffres possibles. Les 10 premiers chiffres seront naturellement notés de 0 à 9, mais pour les 6 chiffres suivants, on convient dutiliser les 6 premières lettres de lalphabet (en majuscule ou en minuscule, peu importe).

Ainsi, il y aura 6 chiffres supplémentaires, dont les valeurs iront de 0 à 15:

Chiffre Valeur Binaire
A 10 1010
B 11 1011
C 12 1100
D 13 1101
E 14 1110
F 15 1111

Nous navons pas représenté les 10 chiffres allant de 0 à 9 puisque leur valeur est évidente.

Reprenons lentier (en base 10) 113, dont la représentation binaire est 1110001. En regroupant les bits par paquets de 4, on aura:

\[ 113 = 1110001\_2 = \underbrace{0111}\_{= 7}\,\underbrace{0001}\_{ = 1}{}\_2 = 71\_{16}\]

Un autre exemple: Considérons le nombre 51042. On aura alors, après lavoir converti en binaire:

\[ 51\,042 = \underbrace{1100}\_{= C} \, \underbrace{0111}\_{= 7} \, \underbrace{0110}\_{= 6} \, \underbrace{0010}\_{= 2}{}\_2 = \text{C}7\,62\_{16}\]

Inversement, si on considère le nombre dont la représentation en base 16 est \(\text{FEED}\), il suffit den déduire les paquets de 4 bits pour ensuite reconvertir vers un nombre décimal:

\[ \text{FE}\,\text{ED}\_{16} = \overbrace{1111}^{= F} \, \overbrace{1110}^{= E} \, \overbrace{1110}^{= E} \, \overbrace{1101}^{= D}{}\_2 = 65\,261\]

Conversion entre représentations décimales et hexadécimales

Dans le paragraphe précédent, nous avons systématiquement utilisé une représentation binaire comme représentation intermédiaire, pour deux raisons:

  • Passer de lhexadécimal au binaire (et inversement) est on ne peut plus simple, comme nous venons de le voir;
  • Convertir du décimal vers le binaire (et inversement) est plus facile à réaliser de tête (pour un humain) que la conversion directe décimal \(\leftrightarrow\) hexadécimal, comme nous allons le voir à présent:

Conversion du décimal vers lhexadécimal

Un point important à réaliser: les algorithmes dépendent très peu des bases utilisées. Convertir depuis et vers lhexadécimal est presque la même chose que convertir depuis et vers le binaire. Seule la base change.

Voici un algorithme efficace pour déterminer la représentation hexadécimale dun nombre \(N\):

N est un entier naturel
Tant que N > 0 faire:
    Afficher le chiffre hexadécimal de valeur N % 16
    N ← N // 16

Tout comme lalgorithme équivalent pour le binaire, les chiffres sont affichés de la droite vers la gauche (du poids le plus faible vers le poids le plus fort). Il est aisé de corriger cela à laide des chaînes de caractères python (nous verrons comment faire en TP).

Conversion de lhexadécimal vers le décimal

Voici un algorithme prenant en entrée une chaîne de caractères contenant uniquement des chiffres hexadécimaux

H est une chaîne de caractères ne contenant que des chiffres hexadécimaux
N ← 0
Pour car parcourant les caractères de H:
    val ← valeur hexadécimale de car
    N ← 16*N + val

Représentation des entiers relatifs

Il est naturel et intéressant de se demander comment un ordinateur peut représenter les entiers relatifs. Le langage python gère bien entendu les entiers relatifs, qui sont représentés à lécran comme on peut sy attendre:

>>> answer = 42
>>> -answer
-42

Cependant, nous savons bien à présent que laffichage en base 10 nest quune représentation pour nous autres humains. Quen est-il en interne ?

Une première tentative consiste à utiliser la fonction `bin` sur un entier négatif:

>>> bin(23)
'0b10111'
>>> bin(-23)
'-0b10111'

Il semblerait donc que python se contente de préfixer lentier par un signe de négation, comme en mathématiques. Mais cela est-il vraiment la représentation interne du nombre ? Nest-ce pas plutôt encore une facilité daffichage ?

Comment représenter le signe moins ? Un premier essai

Nous avons admis le postulat de base que, dans la mémoire de lordinateur, tout doit être représenté sous forme de bits. Un signe moins nest pas un bit, mais on peut peut-être imaginer une méthode permettant un encodage du signe moins: après tout, soit un nombre est positif, soit il est négatif: il ny a que deux états possibles, on peut donc utiliser un bit pour cela.

Prenons le cas dun octet. On pourrait convenir que le premier bit (cest-à-dire le bit de poids fort, le plus à gauche) servirait à représenter le signe du nombre:

  • Un bit de poids fort à `0` signifierait que le nombre est positif;
  • Un bit de poids fort à `1` signifierait que le nombre est négatif.

Ainsi, le nombre \(23\) sécrirait toujours \(00010111_2\), alors que \(-23\) deviendrait \(10010111_2\).

Quels seraient les inconvénients de cette méthode:

  • On perd un bit sur les 8 pour la représentation du signe. Il ne reste donc plus que 128 nombres représentables, mais avec deux signes possibles: on peut donc aller de -127 à 127 sur un octet; Cet inconvénient est absolument impossible à supprimer, quelle que soit la méthode employée, car il faut nécessairement utiliser au moins un bit pour représenter le signe;
  • Le point précédent amène à une possible incohérence: il y a 128 nombres entre 0 et 127, plus les 127 nombres négatifs entre -127 et -1, ce qui ne fait que 255 valeurs distinctes. Or, il est possible dencoder 256 valeurs sur 8 bits. Où est passée la dernière ?
  • Ce paradoxe apparent séclaircit lorsquon saperçoit que le nombre 0 a à présent deux représentations binaires distinctes: \(00000000_2\) et \(10000000_2\). On a donc à nouveau 256 valeurs, mais elles ne sont pas toutes distinctes. Et cela na pas vraiment de sens, mathématiquement parlant;

Ces inconvénients sont bien réels, mais ce nest pas le plus grave. Pour comprendre pourquoi la méthode proposée ici nest pas intéressante, il faut sintéresser à la manière dont un ordinateur additionne des nombres en binaire.

Addition en binaire

Nous verrons dans un cours futur quun microprocesseur possède notamment une partie de ces circuits dédiée aux additions binaires (entre deux octets, entre 2 mots sur 16 bits, mais aussi 32 bits jusquà 64 bits). En attendant, retenons simplement que laddition binaire est une des opérations les plus élémentaire que peut effectuer un microprocesseur, quel quil soit.

Comment additionne-t-on deux nombres en binaire ? Exactement comme en décimal (avec la méthode apprise à lécole élémentaire), à la seule différence quil ny a que deux chiffres. Seules 4 combinaisons peuvent apparaître:

Bit A Bit B Somme Retenue
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

Mais en réalité, il faut aussi tenir compte dune éventuelle retenue précédente, ce qui double le nombre de cas:

Bit A Bit B Retenue précédente Somme Retenue
0 0 0 0 0
0 1 0 1 0
1 0 0 1 0
1 1 0 0 1
0 0 1 1 0
0 1 1 0 1
1 0 1 0 1
1 1 1 1 1

Calculons en exemple la somme 108 + 23. Les représentations binaires de ces deux nombres sur un octet sont 01101100 et 00010111 respectivement.

\[ \begin{array}[t]{r} \tt \overset{1}{0}\overset{1}{1}\overset{1}{1}\overset{1}{0}\,\overset{1}{1}100 \\ \tt 0001\,0111 \\ \hline \tt 1000\,0011 \end{array}\]

On peut constater quil y a beaucoup plus de retenues quen décimal. On conviendra que, sil y avait eue une retenue sur le bit de poids fort, alors on laurait abandonnée: on dit que cette addition se fait sans dépassement (les microprocesseur offrent tous un moyen de savoir si cette dernière retenue a existé ou non, car lorsque cela arrive, il est souvent de pouvoir réagir en conséquence).

À présent que nous savons additionner, nous souhaiterions que laddition soit idéalement compatible avec notre représentation des nombres relatifs. Cela est-il bien le cas ?

Effectuons laddition de 23 et de -23 avec les représentations binaires associées:

\[ \begin{array}[t]{r} \tt 00\overset{1}{0}1\,\overset{1}{0}\overset{1}{1}\overset{1}{1}1 \\ \tt 1001\,0111 \\ \hline \tt 1010\,1110 \end{array}\]

On trouve le nombre \(1010\,1110_2 = 174\), qui nest pas du tout le zéro attendu (même avec les deux représentations possibles de zéro).

Le système proposé ici nest donc pas compatible avec laddition binaire, il faut trouver autre chose.

La solution idéale: le complément à 2

Remarquons une chose intéressante: si on effectue laddition sans dépassement de \(1111\,1111_2 = 255\) avec 1, on trouvera \(0000\,0000_2 = 0\) (en effet, le résultat devrait théoriquement être \(1\,0000\,0000_2 = 256\), mais la dernière retenue a été perdue.

Cela nous met sur la bonne voie: dans la représentation idéale des entiers relatifs, le nombre \(1111\,1111_2\) devrait représenter lentier \(-1\), puisquil donne zéro lorsquon lui ajoute 1 !

Cest exactement comme cela que nous allons procéder: puisque nous avons vu que, en tronquant à 8 bits, le nombre 256 donne zéro, on pourra représenter un entier négatif \(-n\) par \(256 - n\).

Dans la pratique, on neffectuera pas de soustraction, il y a beaucoup plus rapide. En effet, on peut écrire:

\[ 256 - n = 255 + 1 - n = (255 - n) + 1\]

Pourquoi faire cela ? Tout simplement parce que \(255 - n\) se calcule très facilement en binaire: il suffit dinverser tous les bits. Nous procéderons donc en deux temps: on inverse tous les bits, puis on rajoute 1 (sans dépassement); cest ce quon appelle le complément à deux.

Complément à deux Pour calculer le complément à deux dun entier \(n\) sur un nombre de bit donné, on procède toujours en deux étapes:

  1. On inverse les bits de la représentation binaire de \(n\);
  2. On ajoute 1 (sans dépassement)

Le nombre obtenu sera appelé le complément à deux de \(n\), et il représente le nombre \(-n\), bien que son nom réel devrait être complément à deux puissance \(N\), où \(N\) est le nombre de bits de la représentation de ce nombre (8, 16, 32, etc).

Deux questions se posent:

  • Pourquoi \(255 - n\) correspondil à linversion des bits ? Tout simplement parce que \(255 = 2^7 + 2^6 + \cdots + 2^0\) est la somme des huits puissances de deux. En effectuant \(255 - n\), on supprime donc de cette somme les puissances composant le nombre \(n\): cela revient à chercher exactement les puissances qui ne sont pas dans \(n\), autrement dit, à inverser les bits de la représentation de \(n\).
  • Combien de nombres négatif peut-on représenter ainsi ? Comme on a 256 valeurs possibles, le plus judicieux est de couper la poire en deux: on aura 128 valeurs positives (les nombres entre 0 et 127) et 128 valeurs négatives (les nombres entre -128 et -1). Cela fonctionne très bien:
Représentation binaire Entier non signé Entier signé
1111 1111 255 -1
1111 1110 254 -2
1111 1101 253 -3
\(\vdots\) \(\vdots\) \(\vdots\)
1000 0010 130 -126
1000 0001 129 -127
1000 0000 128 -128
0111 1111 127 127
0111 1110 126 126
\(\vdots\) \(\vdots\) \(\vdots\)
0000 0010 2 2
0000 0001 1 1
0000 0000 0 0

On constate plusieurs choses:

  • Le zéro a à nouveau une représentation unique, ce qui est une bonne chose;
  • Étant donné une représentation binaire sur un octet (ou toute autre taille), il ny a aucun moyen de savoir sil sagit dun nombre signé (entre -128 et +127) ou bien un nombre non signé (entre 0 et 255): il appartient au programmeur de toujours savoir ce que contient un octet: sil y a placé un nombre signé, il devra linterpréter comme tel.
  • On garde tout de même un effet bénéfique de notre tentative ratée de représenter les entiers négatifs: un entier sera négatif si et seulement si son bit de poids fort est à 1 !

Exercices pratiques

Comment déterminer dans la pratique le complément à deux dun entier \(n\) sur une représentation à \(N\) bits ? Nous avons vus plusieurs algorithmes potentiels:

  • Le complément à deux se calcule simplement par lopération \(2^N - n\), par exemple \(256 - n\) si on est sur 8 bits, \(65536 - n\) sur 16 bits, etc.
  • On peut avantageusement remplacer cette soustraction par:
    • Inverser les bits (ce qui correspond à une négation logique)
    • Ajouter 1
  • Ce dernier algorithme peut même être raccourci davantage pour une conversion de tête:

    • En commençant par le bit de poids faible (à droite), chercher le premier bit à 1 (sil y en a).
    • Inverser tous les bits situés à gauche de celui-ci.

    Notons que sil ny a aucun bit à 1, on ninverse rien du tout. Le seul cas où cela pourrait se produire est le cas où \(n = 0\), et cest alors normal de ne pas inverser de bits puisque la représentation de 0 est unique.

Comparons ces trois algorithmes sur le nombre \(n = 37\) avec une représentation sur 8 bits signés.

  • Le calcul de \(256 - 37\) donne \(11011011_2\).
  • La représentation de 37 étant \(00100101_2\) sur 8 bits, linversion des bits donne \(11011010_2\), ce qui nous amène bien à \(11011011_2\) lorsque lon rajoute 1.
  • Dans la représentation de 37, le 1 le plus à droit est le dernier. Si on inverse tous les bits situés à sa gauche, cest-à-dire \(\underline{0010010}\mathbf{1}_2\), on trouve bien \(11011011_2\).

Comment effectuer lopération inverse, à savoir déterminer un nombre dont la représentation en complément à deux sur \(N\) bits est connue ?

  • On peut inverser lalgorithme précédent:

    • Soustraire 1
    • Inverser les bits
  • Mais en réalité il est beaucoup plus simple de constater le fait suivant: le complément à deux du complément à deux de \(n\) est \(n\). Autrement dit, appliquer deux fois lopération du complément à deux retourne au nombre de départ. Cest plutôt logique lorsque lon se rappelle que le complément à deux sert à calculer lopposé dun nombre. Et cela se justifie aisément dun point de vue mathématique:

    • Le premier complément à deux revient à calculer \(2^N - n\).
    • Le second complément à deux donne alors \(2^N - \big(2^N - n\Big) = 2^N - 2^N + n = n\).

Prenons par exemple le nombre dont la représentation sur 16 bits signés est \(1111111101101000_{16}\). Quel est le nombre \(n\) représenté ?

Il suffit dinverser tous les bits situés à gauche du 1 le plus à droite, cest-à-dire \(\underline{111111110110}\mathbf{1}000_{16}\) pour trouver \(0000000010011000_{16} = 152\). Le nombre original représente alors \(n = -152\).