DIU Bloc 1Codage des nombres (entiers)

Laure Gonnord

Universite de Lyon

Mars 2020

Source : Nicolas Louvet et LG pour Archi (L2)

2 / 25

Plan

Entiers naturelsChangements de baseCodage en machine

Entiers relatifs : codage en complement a 2DefinitionAddition et calcul de l’oppose en complement a 2

Representation de nombres rationnels

Changement de base : decimal vers binaire

Changement de base : binaire vers decimal

3 / 25

Soit β ∈ N, β > 1, une base. Tout n ∈ N peut etre representede maniere unique par sa representation positionnelle en baseβ :

(xp−1xp−2 · · · x1x0)β :=

p−1∑i=0

xiβi .

• Les xi ∈ {0, 1, . . . , β − 1} sont les chiffres de l’ecriture den en base β.

• On attribue un symbole a chaque chiffre :• β = 2, chiffres 0 et 1 ;• β = 10, chiffres de 0 a 9 ;• β = 16, chiffres de 0 a F.

• p est le nombre de chiffres necessaires pour ecrire del’entier naturel n.

Ex : (5134)10 = 5·103 + 1·102 + 3·10 + 4 = 5134 en ecrituredecimale.

4 / 25

Plan

Entiers naturelsChangements de baseCodage en machine

Entiers relatifs : codage en complement a 2DefinitionAddition et calcul de l’oppose en complement a 2

Representation de nombres rationnels

Changement de base : decimal vers binaire

Changement de base : binaire vers decimal

5 / 25

Utiliser la definition de la notation positionnelle

Soient β la base de depart et γ celle d’arrivee. On ecritn =

∑p−1i=0 xiβ

i .

Il est toujours possible de

• convertir les xi et β vers leurs ecritures en base γ,

• de calculer∑p−1

i=0 xiβi en effectuant toutes les operations

en base γ.

On deduit l’ecriture de n en base γ : il suffit de calculer dansla base d’arrivee γ.

Ex - conversion binaire vers decimal : avec n = (10100)2.On ajoute les puissances de 2 correspondant aux bits non-nuls.

chiffre 1 0 1 0 0position 4 3 2 1 0poids 24 0 22 0 0

Donc (10100)2 = 24 + 22 =16 + 4 = 20.

6 / 25

Utiliser la definition de la notation positionnelle

Soient β la base de depart et γ celle d’arrivee. On ecritn =

∑p−1i=0 xiβ

i .

Il est toujours possible de

• convertir les xi et β vers leurs ecritures en base γ,

• de calculer∑p−1

i=0 xiβi en effectuant toutes les operations

en base γ.

On deduit l’ecriture de n en base γ : il suffit de calculer dansla base d’arrivee γ.

Ex - conversion binaire vers decimal : avec n = (10100)2.On ajoute les puissances de 2 correspondant aux bits non-nuls.

chiffre 1 0 1 0 0position 4 3 2 1 0poids 24 0 22 0 0

Donc (10100)2 = 24 + 22 =16 + 4 = 20.

6 / 25

Divisions euclidiennes successives

Le reste dans la division euclidienne d’un entier naturel n par βdonne le chiffre de poids faible dans la representation de n enbase β. En effet,

n = xp−1·βp−1 + xp−2·βp−2 + · · ·+ x2·β2 + x1·β1 + x0,

=(xp−1·βp−2 + xp−2·βp−3 + · · ·+ x2·β1 + x1

)︸ ︷︷ ︸quotient

·β + x0︸︷︷︸reste

,

avec 0 ≤ x0 < β. En d’autres termes, n mod β = x0.

On peut donc obtenir tous les chiffres de l’ecriture d’un entiernaturel n par des divisions euclidiennes successives, ens’arretant au premier quotient nul :on obtient les chiffres de poids faibles d’abord !

7 / 25

Deux exemplesEx : soit n = (423)10, a convertir en base 2.

423 = 211 × 2 + 1211 = 105 × 2 + 1105 = 52 × 2 + 152 = 26 × 2 + 026 = 13 × 2 + 013 = 6 × 2 + 16 = 3 × 2 + 03 = 1 × 2 + 11 = 0 × 2 + 1

On en deduit que n = (110100111)2.Ex : Conversion decimal vers octal. Soit n = (3452)10, aconvertir en base 8.

3452 = 431 × 8 + 4431 = 53 × 8 + 753 = 6 × 8 + 56 = 0 × 8 + 6

Donc n = (6574)8.8 / 25

Entre les bases 2, 8 et 16 : methodes directesComme 8 = 23, chaque chiffre octal est represente par unentier sur trois bits, et chaque entier sur trois bits estrepresente par un chiffre octal :

(x8x7x6x5x4x3x2x1x0)2 = (x8x7x6)2︸ ︷︷ ︸=y2

·82+(x5x4x3)2︸ ︷︷ ︸=y1

·81+(x2x1x0)2︸ ︷︷ ︸=y0

·80 = (y2y1y0)8.

Ex - octal vers binaire : n = (34521)8.On fait un tableau de conversion entre nombres binaires etchiffres octaux :

rep. chiffre rep. chiffrebinaire octal binaire octal

000 0 100 4001 1 101 5010 2 110 6011 3 111 7

On a n = (011′100′101′010′001)2.9 / 25

Plan

Entiers naturelsChangements de baseCodage en machine

Entiers relatifs : codage en complement a 2DefinitionAddition et calcul de l’oppose en complement a 2

Representation de nombres rationnels

Changement de base : decimal vers binaire

Changement de base : binaire vers decimal

10 / 25

En machine, le nombre de bits p de la representationpositionnelle est fixe pour chaque formats de codage (entiers8, 16, 32 ou 64 bits).Si le resultat d’une operation requiert plus de p bits pour etrerepresente :• le resultat calcule est forme des p bits de poids faibles du

resultat exact,• le drapeau de depassement de capacite de l’ALU est leve.

Cela n’implique pas un arret des calculs, car le resultat peutetre exploite.Soit m un entier code sur q ≥ p bits :

m =

q−1∑i=0

mi2i =

(q−1∑i=p

mi2i−p

)︸ ︷︷ ︸quotient de m par 2p

×2p +

p−1∑i=0

mi2i

︸ ︷︷ ︸reste

.

Lorsqu’on effectue une operation arithmetique entre entiersnaturels, et que l’on represente le resultat m sur p bits, leresultat obtenu est m mod 2p. 11 / 25

Plan

Entiers naturelsChangements de baseCodage en machine

Entiers relatifs : codage en complement a 2DefinitionAddition et calcul de l’oppose en complement a 2

Representation de nombres rationnels

Changement de base : decimal vers binaire

Changement de base : binaire vers decimal

12 / 25

Plan

Entiers naturelsChangements de baseCodage en machine

Entiers relatifs : codage en complement a 2DefinitionAddition et calcul de l’oppose en complement a 2

Representation de nombres rationnels

Changement de base : decimal vers binaire

Changement de base : binaire vers decimal

13 / 25

Representation en complement a 2Soit un entier relatif n, −2p−1 ≤ n ≤ 2p−1 − 1, a coder enmachine sur p bits. La notation utilisee pour le codage de n encomplement a 2 sur p bits est :

n = (cp−1cp−2 . . . c1c0)2.

On adopte la definition suivante :

(cp−1cp−2 . . . c1c0)2 := −cp−12p−1 +

p−2∑i=0

ci2i .

On peut montrer que :{n ≥ 0 ssi cp−1 = 0,n < 0 ssi cp−1 = 1.

14 / 25

Une maniere d’interpreter le codage en complement a 2 estdonc de considerer que le bit le plus a gauche a un poidsnegatif (−2p−1).

Ex : par exemple, supposons qu’on effectue un codage sur 8bits (p = 8).

• Quelle est la valeur decimale codee par (10000011)2 ?

(10000011)2 = −128 + 1 + 2 = (−125)10.

• Comment coder (−120)10 en complement a 2 ?(−120)10 = −128 + 8, donc (−120)10 = (10001000)2.

15 / 25

Une maniere d’interpreter le codage en complement a 2 estdonc de considerer que le bit le plus a gauche a un poidsnegatif (−2p−1).

Ex : par exemple, supposons qu’on effectue un codage sur 8bits (p = 8).

• Quelle est la valeur decimale codee par (10000011)2 ?(10000011)2 = −128 + 1 + 2 = (−125)10.

• Comment coder (−120)10 en complement a 2 ?

(−120)10 = −128 + 8, donc (−120)10 = (10001000)2.

15 / 25

Une maniere d’interpreter le codage en complement a 2 estdonc de considerer que le bit le plus a gauche a un poidsnegatif (−2p−1).

Ex : par exemple, supposons qu’on effectue un codage sur 8bits (p = 8).

• Quelle est la valeur decimale codee par (10000011)2 ?(10000011)2 = −128 + 1 + 2 = (−125)10.

• Comment coder (−120)10 en complement a 2 ?(−120)10 = −128 + 8, donc (−120)10 = (10001000)2.

15 / 25

Plan

Entiers naturelsChangements de baseCodage en machine

Entiers relatifs : codage en complement a 2DefinitionAddition et calcul de l’oppose en complement a 2

Representation de nombres rationnels

Changement de base : decimal vers binaire

Changement de base : binaire vers decimal

16 / 25

Addition et complement a 2Soient m = (cm)2 et n = (cn)2 en complement a 2 sur p bits.

Addition en complement a 2En l’absence de depassement de capacite, le codage de m + nen complement a 2 sur p bits est le codage de (cm + cn)mod 2p en tant qu’entier naturel. Depassement de capacite,i.e. le resultat est incorrect :

• si m et n sont de signes opposes aucun depassement n’estpossible.

• si m et n sont de meme signe, il y depassement ssi lesigne du resultat calcule differe du signe des operandes.

Oppose en complement a 2En l’absence de depassement de capacite, le codage de −n encomplement a 2 sur p bits est le meme que celui de l’entiernaturel

(cp−1cp−2 . . . c1c0)2 + 1 mod 2p. 17 / 25

Ex : p = 7, (36)10 = (0100100)2 a pour oppose(−36)10 = (1011100)2.Notons que si on additionne (1011100)2 et (0100100)2, onobtient bien 0 :

1 1 1 0 1 1 1 1 1 1 0 0+ 0 1 0 0 1 0 061 0 0 0 0 0 0 0

↪→ 0

18 / 25

Plan

Entiers naturelsChangements de baseCodage en machine

Entiers relatifs : codage en complement a 2DefinitionAddition et calcul de l’oppose en complement a 2

Representation de nombres rationnels

Changement de base : decimal vers binaire

Changement de base : binaire vers decimal

19 / 25

Les rationnels sont les nombres de la forme pq

, avec p ∈ Z et

q ∈ N− {0}.On veut coder dans un format de longueur fixe des nombresdont l’ecriture en binaire est potentiellement infinie : il faut secontenter d’une approximation.

Tout nombre rationnel x ∈ Q positif peut etre decompose en

• une partie entiere bxc ∈ N telle que bxc ≤ x < bxc+ 1 ;

• une partie fractionnaire {x} = x − bxc avec 0 ≤ {x} < 1.

On utilise la notation positionnelle pour l’ecriture de {x} : s’ilexiste q ∈ N t.q.

{x} = (0, x−1 . . . x−q)β =

q∑i=1

x−iβ−i ,

alors x = (xp−1xp−2 . . . x0,x−1x−2 . . . x−q)β est l’ecriture x enbase β.

20 / 25

PeriodiciteLe probleme est que l’ecriture d’un rationnel en base β n’estpas forcement finie : par contre, on sait que cette ecriture estnecessairement periodique.Ex : en base β = 10, quelle est l’ecriture de 13/7 ?

1 3 76 0 1, 85714285 . . .

4 05 0

1 03 0

2 06 0

4 0

Dans ce cas, on note x = (1, 857142)10, pour indiquer laperiode.

21 / 25

PeriodiciteLe probleme est que l’ecriture d’un rationnel en base β n’estpas forcement finie : par contre, on sait que cette ecriture estnecessairement periodique.Ex : en base β = 10, quelle est l’ecriture de 13/7 ?

1 3 76 0 1, 85714285 . . .

4 05 0

1 03 0

2 06 0

4 0

Dans ce cas, on note x = (1, 857142)10, pour indiquer laperiode.

21 / 25

Plan

Entiers naturelsChangements de baseCodage en machine

Entiers relatifs : codage en complement a 2DefinitionAddition et calcul de l’oppose en complement a 2

Representation de nombres rationnels

Changement de base : decimal vers binaire

Changement de base : binaire vers decimal

22 / 25

Changement de base : decimal vers binaireSoit 0 ≤ x < 1 dont on connaıt l’ecriture en decimal. On veutdeterminer son ecriture en binaire :

x = (0, x−1 . . . x−q)2.

On a 2× x = (x−1, x−2 . . . x−q)2, donc x−1 = b2× xc.On procedant par des multiplications successives par 2, onpeut ainsi extraire un par un les bits de l’ecriture binaire de x .

Ex : convertir 1/10 = (0, 1)10 en ecriture binaire.

1/10× 2 = 0 + 2/102/10× 2 = 0 + 4/104/10× 2 = 0 + 8/108/10× 2 = 1 + 6/106/10× 2 = 1 + 2/10

On en deduit que (0, 1)10 = (0, 00011)2.

23 / 25

Plan

Entiers naturelsChangements de baseCodage en machine

Entiers relatifs : codage en complement a 2DefinitionAddition et calcul de l’oppose en complement a 2

Representation de nombres rationnels

Changement de base : decimal vers binaire

Changement de base : binaire vers decimal

24 / 25

Changement de base : binaire vers decimal

On considere un rationnel 0 ≤ x < 1 dont on connaıt l’ecritureen binaire. On souhaite determiner son ecriture en decimale.

On peut utiliser la meme methode que precedemment :

• Il suffit d’effectuer des multiplications par(10)10 = (1010)2, en calculant en binaire : on obtient leschiffres decimaux de l’ecriture de x .

• Les calculs a la main sont fastidieux, mais une machinepeut les mener efficacement.

Pour des nombres binaires comptant peu de bits apres lavirgule, il est suffisant de sommer le poids de ces bits.

2−1 = 0, 5 2−2 = 0, 25 2−3 = 0, 125 2−4 = 0, 0625

25 / 25