Livre_silo 30 août 2013 16:32 Page 44
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
44
Informatique pour tous
Exercice 2.35 * Démontrer que l’addition de deux entiers relatifs en machine produit un dépassement
arithmétique si et seulement si :
• ces entiers sont de même signe ;
• et le résultat obtenu en machine est de signe opposé au signe des opérandes.
On pourra commencer par supposer que les entiers sont représentés sur n bits, puis exprimer par un
encadrement quels sont les entiers de chaque signe représentables dans ce format. Enfin, on en déduira
un encadrement du résultat de la somme de deux entiers dans chacun des cas possibles.
De même, déterminer un critère permettant de détecter un dépassement arithmétique lors d’une soustraction de deux entiers relatifs.
Exercice 2.36 * (À réaliser dans une version Python 2.x)
À l’aide de la calculatrice Python, déterminez le plus grand entier représentable par le type int sur votre
machine. Vérifiez si votre machine fonctionne en 32 bits ou en 64 bits et calculez la valeur théorique de
ce plus grand entier pour vérifier votre réponse.
Exercice 2.37 * L’ensemble des entiers naturels machine écrits sur 16 bits, avec les dépassements de
capacité expliqués dans ce chapitre (calcul sur un nombre de bits arbitraire puis troncature des bits surnuméraires) forme-t-il un groupe pour l’addition ? Forme-t-il un anneau pour l’addition et la multiplication ?
Forme-t-il un corps ?
Exercice 2.38 ** L’ensemble des entiers relatifs machine écrits sur 16 bits, avec les dépassements de
capacité expliqués dans ce chapitre forme-t-il un groupe pour l’addition ? Un anneau pour l’addition et la
multiplication ? Un corps ?
Exercice 2.39 * L’ensemble des entiers longs de Python forme-t-il un groupe pour l’addition, en admettant que l’on dispose d’une mémoire illimitée ? Forme-t-il un anneau pour l’addition et la multiplication ?
Forme-t-il un corps ?
Exercice 2.40 Un intérêt majeur de la notation des entiers relatifs en complément à deux est que les
additions, les soustractions et les comparaisons peuvent toutes être effectuées au moyen d’une même
opération, à quelques ajustements près.
Dans tout cet exercice, on supposera que les nombres sont représentés sur n bits.
1 Vérifier sur quelques exemples que la somme de deux entiers naturels représentés sur n bits peut se
faire d’une façon similaire à celle que l’on apprend à l’école primaire pour les nombres en base 10 :
calcul de la somme chiffre par chiffre, de droite à gauche, avec une retenue si nécessaire. Par exemple
la somme 13 + 28 s’écrit en binaire :
32aines seizaines
huitaines
quatraines deuxaines unités
1
1
1
(retenues)
1
1
0
1
(13)
+
1
1
1
0
0
(28)
1
0
1
0
0
1
(41)
2 En lien avec cette procédure d’addition, donner une caractérisation simple des cas où la somme de deux
entiers naturels produit un dépassement de capacité.
3 Soient maintenant x et y deux entiers relatifs que l’on suppose représentables sur n bits. On appelle
m et p les entiers naturels qui représentent respectivement x et y dans la notation en complément à 2.
Démontrer que, quels que soient les signes de x et y, la somme binaire des entiers m et p effectuée
comme à la question 1 donne bien l’entier naturel qui représente l’entier relatif x + y en complément
à 2, éventuellement à un dépassement arithmétique près.
4 On rappelle que pour déterminer la représentation de l’opposé d’un entier relatif, il suffit de partir de
la représentation de cet entier, d’inverser tous ses bits puis d’ajouter 1 au résultat obtenu (voir exercice
corrigé 2.27). En déduire une procédure simple pour calculer la différence de deux nombres relatifs en
binaire en réutilisant encore une fois la procédure d’addition des entiers naturels. On pourra remarquer
que l’étape « ajouter 1 au résultat obtenu » peut être intégrée dans l’addition au moyen d’une retenue.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
44
Informatique pour tous
Exercice 2.35 * Démontrer que l’addition de deux entiers relatifs en machine produit un dépassement
arithmétique si et seulement si :
• ces entiers sont de même signe ;
• et le résultat obtenu en machine est de signe opposé au signe des opérandes.
On pourra commencer par supposer que les entiers sont représentés sur n bits, puis exprimer par un
encadrement quels sont les entiers de chaque signe représentables dans ce format. Enfin, on en déduira
un encadrement du résultat de la somme de deux entiers dans chacun des cas possibles.
De même, déterminer un critère permettant de détecter un dépassement arithmétique lors d’une soustraction de deux entiers relatifs.
Exercice 2.36 * (À réaliser dans une version Python 2.x)
À l’aide de la calculatrice Python, déterminez le plus grand entier représentable par le type int sur votre
machine. Vérifiez si votre machine fonctionne en 32 bits ou en 64 bits et calculez la valeur théorique de
ce plus grand entier pour vérifier votre réponse.
Exercice 2.37 * L’ensemble des entiers naturels machine écrits sur 16 bits, avec les dépassements de
capacité expliqués dans ce chapitre (calcul sur un nombre de bits arbitraire puis troncature des bits surnuméraires) forme-t-il un groupe pour l’addition ? Forme-t-il un anneau pour l’addition et la multiplication ?
Forme-t-il un corps ?
Exercice 2.38 ** L’ensemble des entiers relatifs machine écrits sur 16 bits, avec les dépassements de
capacité expliqués dans ce chapitre forme-t-il un groupe pour l’addition ? Un anneau pour l’addition et la
multiplication ? Un corps ?
Exercice 2.39 * L’ensemble des entiers longs de Python forme-t-il un groupe pour l’addition, en admettant que l’on dispose d’une mémoire illimitée ? Forme-t-il un anneau pour l’addition et la multiplication ?
Forme-t-il un corps ?
Exercice 2.40 Un intérêt majeur de la notation des entiers relatifs en complément à deux est que les
additions, les soustractions et les comparaisons peuvent toutes être effectuées au moyen d’une même
opération, à quelques ajustements près.
Dans tout cet exercice, on supposera que les nombres sont représentés sur n bits.
1 Vérifier sur quelques exemples que la somme de deux entiers naturels représentés sur n bits peut se
faire d’une façon similaire à celle que l’on apprend à l’école primaire pour les nombres en base 10 :
calcul de la somme chiffre par chiffre, de droite à gauche, avec une retenue si nécessaire. Par exemple
la somme 13 + 28 s’écrit en binaire :
32aines seizaines
huitaines
quatraines deuxaines unités
1
1
1
(retenues)
1
1
0
1
(13)
+
1
1
1
0
0
(28)
1
0
1
0
0
1
(41)
2 En lien avec cette procédure d’addition, donner une caractérisation simple des cas où la somme de deux
entiers naturels produit un dépassement de capacité.
3 Soient maintenant x et y deux entiers relatifs que l’on suppose représentables sur n bits. On appelle
m et p les entiers naturels qui représentent respectivement x et y dans la notation en complément à 2.
Démontrer que, quels que soient les signes de x et y, la somme binaire des entiers m et p effectuée
comme à la question 1 donne bien l’entier naturel qui représente l’entier relatif x + y en complément
à 2, éventuellement à un dépassement arithmétique près.
4 On rappelle que pour déterminer la représentation de l’opposé d’un entier relatif, il suffit de partir de
la représentation de cet entier, d’inverser tous ses bits puis d’ajouter 1 au résultat obtenu (voir exercice
corrigé 2.27). En déduire une procédure simple pour calculer la différence de deux nombres relatifs en
binaire en réutilisant encore une fois la procédure d’addition des entiers naturels. On pourra remarquer
que l’étape « ajouter 1 au résultat obtenu » peut être intégrée dans l’addition au moyen d’une retenue.