En informatique les nombres ne sont pas codés sous forme décimale mais sous forme binaire ou hexadécimale.
Sur $8$ bits on peut représenter les entiers de $0$ à $255$.
Pour trouver l'écriture binaire d'un entier ${\tt n}$, on effectue des divisions euclidiennes par 2 jusqu'à obtenir un quotient nul. L'écriture binaire est alors formée de la suite des restes dans l'ordre inverse de celui dans lequel on les a calculés.
Par exemple avec ${\tt 57}$:
${\tt 57=28\times 2+1}$ le quotient ${\tt 28}$ n'est pas nul
${\tt 28=14\times 2+0}$ le quotient ${\tt 14}$ n'est pas nul
${\tt 14=7\times 2+0}$ le quotient ${\tt 7}$ n'est pas nul
${\tt 7=3\times 2+1}$ le quotient ${\tt 3}$ n'est pas nul
${\tt 3=1\times 2+1}$ le quotient ${\tt 1}$ n'est pas nul
${\tt 1=0\times 2+1}$ le quotient est ${\tt 0}$ $\fbox{STOP}$
Pour avoir l'écriture binaire on écrit les restes dans l'ordre inverse de celui dans lequel on les a calculés: ${\tt 57=\overline{111001}^2}$ ce qui se note en Python avec une chaîne de caractères préfixées par '0b'
: '0b111001'
.
Si les nombres sont des entiers non signés codés sur 8 bits l'écriture est complétée en mémoire par Python avec des ${\tt 0}$ sur la gauche :
'0b00111001'
mais ceci est invisible par l'utilisateur.
On peut vérifier avec la commande ${\tt bin()}$.
bin(57)
'0b111001'
L'opération inverse se fait avec la commande ${\tt int(\;\cdot\;,2)}$:
int('0b111001',2) # remarquez que la commande ignore automatiquement le préfixe '0b'
57
Ces deux fonctions ne sont pas au programme, s'il faut les utiliser elles seront rappelées.
Ne pas confondre avec l'instruction
int(x)
qui force l'argumentx
a être transtypé dans le typeint
.
int('32')
32
Si une addition ou une soustraction n'a pas un résultat entre $0$ et $255$ le calcul est effectué mais le résultat est faux: on appelle cela un dépassement de capacité.
C'est une source fréquence de bugs informatiques dont les conséquences peuvent être dramatiques: par exemple en 1996 l'explosion de la fusée Ariane 5 trente secondes après son décollage.
https://fr.wikipedia.org/wiki/Vol_501_d%27Ariane_5
On peut manipuler les entiers non signés sur $8$ bits avec la fonction uint8
du module Numpy
: uint(x)
est l'entier signé sur codé sur $8$ bits égal à x
.
import numpy as np
x = np.uint8(130)
y = np.uint8(178)
x+y # pourquoi 52 ?
/tmp/ipykernel_19481/588968075.py:5: RuntimeWarning: overflow encountered in scalar add x+y
52
Le module
numpy
et son typeuint8
ne sont pas à connaître.
Inversement si
n
est codé en binaire sur $8$ bits par ${\tt \overline{a_0a_1a_2a_3a_4a_5a_6a_7}^2}$ alors en décimal: $$n=a_0\times 2^7+a_1\times 2^6+a_2\times 2^5+a_3\times 2^4+a_4\times 2^3+a_5\times 2^2+a_6\times 2^1+a_7\times 2^0$$
On représente les entiers de $-128$ à $127$.
La méthode utilisée est celle du complément à 2:
Le premier bit donne donc le signe: 1 si le nombre est négatif et 0 s’il est positif.
Avec cette méthode l’addition peut se faire bit à bit.
Par exemple sur $57$ est encore représenté par 00111001
.
Pour $-57$ on inverse les bits ce qui donne 11000110
puis on ajoute 1, on obtient 11000111
.
On peut vérifier avec numpy
. On dispose de la fonction int8
pour manipuler des entiers signés sur $8$ bits (cette fonction n'est pas à connaître).
np.uint8('111001') # convertit l'écriture binaire donnée sous forme d'une chaîne de caractères
# en entier non signé codé sur 8 bits
57
np.int8('11000111') # convertit l'écriture binaire donnée sous forme d'une chaîne de caractères
# en entier signé codé sur 8 bits
47
Python travaille avec des entiers multiprécisions, c’est-à-dire qu’il adapte le nombre de bits utilisés pour le codage aux besoins du calcul, de façon à garantir des calculs exacts.
Aucune connaissance théorique n'est exigé sur les entiers multiprécisions.
On représente aussi les nombres en base 16:
les chiffres sont alors 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A (pour 10),B (pour 11),C (pour 12),D (pour 13),E (pour 14), F (pour 15).
Par exemple ${\tt \overline{A1}^{16}=10\times 16+1=161}$ et ${\tt \overline{32E}^{16}=3\times16^2+2\times 16+14=814}$.
En Python l'écriture hexadécimale (c'est-à-dire en base $16$) est préfixée de '0x'
:
int('0xA1',16)
161
int('0x32E',16)
814
Pour trouver l'écriture hexadécimale d'un entier naturel on peut procéder par des divisions successives par $16$ et récupérer les restes (comme pour la base $2$).
Si on dispose de l'écriture binaire de l'entier il suffit de grouper les bits par paquets de 4 (en ajoutant le nombre de 0 nécessaires à gauche). Ensuite on utilise les conversions suivantes:
${\tt \begin{array}{cccc}0000=0& 0001=1& 0010=2& 0011=3\\
0100=4& 0101=5& 0110=6& 0111=7\\
1000=8& 1001=9& 1010=A& 1011=B\\
1100=C&
1101=D&
1110=E&
1111=F\end{array}}$
C'est cette méthode qui est la plus simple lorsqu'on demande de coder << à la main >> un entier en base $16$.
Par exemple ${\tt 705=\overline{1011000001}^2=\overline{0010\,\,1100\,\,0001}^2=\overline{2C1}^{16}}$
Si les nombres sont codés sur 8 bits cela donne donc 2 chiffres en hexadécimal (4 bits par chiffre).
On peut vérifier avec la commande ${\tt hex()}$:
hex(705)
'0x2c1'
Cette fonction n'est pas à connaître.
On donne le pseudo-code de l'algorithme qui calcule l'écriture binaire d'un entier n
sous forme d'une liste :
Donnée: n
de type int
Sortie: liste
liste des chiffres binaires de la représentation de n
liste
à la liste vide.n
n'est pas nul:liste
le reste de la division euclidienne de n
par 2n
par le quotient de la division euclidienne de n
par 2liste
.Q1. Ecrire une fonction binaire(n)
qui renvoie la liste des chiffres de l'écriture binaire de n
.
Par exemple binaire(57)
renvoie [1, 1, 1, 0, 0, 1]
.
Q2. Ecrire une fonction hexa(n)
qui renvoie la liste des chiffres de l'écriture hexadécimale de n
.
Par exemple hexa(814)
renvoie [3, 2, 'E']
.
On pourra utiliser une variable symboles = [0, 1, 2, 3, 4 ,5 ,6 ,7 ,8, 9, 'A', 'B', 'C', 'D', 'E', 'F']
.
Q3. Ecrire une fonction decimal(L)
qui reçoit en entrée la liste L
des chiffres de l'écriture binaire de n
et renvoie la valeur décimale de n
.
Par exemple decimal([1, 1, 1, 0, 0, 1])
renvoie 57
.
Q4. Une photo en noir et blanc a une taille de $2048\times 1536$ pixels. La couleur de chaque pixel est codée par un entier non signé sur $8$ bits. Quelle est la taille de cette image en Mo?
Dans cet exercice, on s'intéresse à la suite $(u_n)_{n\in\mathbb{N}}$ vérifiant $u_0=3$, $u_1=1$ et la relation de récurrence linéaire: $${\tt \forall n\in\mathbb{N},\qquad u_{n+2}=u_n-\dfrac{8}{3}u_{n+1}}$$
Q5. Ecrire une fonction uRec(n)
qui prend en argument un entier naturel n
et renvoie la valeur de ${\tt u_n}$ calculée avec la relation de récurrence précédente.
Q6. On peut montrer que ${\tt u_n=\left(\dfrac{1}{3}\right)^{n-1}}$ pour tout ${\tt n\in\mathbb{N}}$.
Ecrire une fonction uExp(n)
qui prend en argument un entier naturel n
et renvoie la valeur de ${\tt u_n}$ calculée avec cette formule explicite. Comparer sur un même graphique les 100 premières valeurs de $u_n$ calculés avec Q5 et Q6.
On rappelle que si u
et v
sont deux listes alors on les représente graphiquement avec les instructions:
import matplotlib.pyplot as plt
plt.figure() # Initialise une nouvelle figure
plt.plot(u,'r')
plt.plot(v,'g')
plt.show()
Q7. L'opérateur ${\tt xor}$ (ou exclusif) est défini par:
${\tt 0\;xor\;0=0}$
${\tt 1\;xor\;0=1}$
${\tt 0\;xor\;1=1}$
${\tt 1\;xor\;1=0}$
Ecrire une fonction xor(n, p)
qui prend en argument deux entiers naturels n
et p
et renvoie l'entier naturel obtenu après application de l'opérateur ${\tt xor}$ bit par bit sur les bits de l'écriture binaire de n
et p
(complétées par des 0 pour que les deux écritures soient de même longueur).
Par exemple:
xor(3, 5)
renvoie 6
puisque ${\tt 3=\overline{011}^2}$ et ${\tt 5=\overline{101}^2}$ et ${\tt 6=\overline{110}^2}$.
xor(302, 234)
renvoie 452
puisque ${\tt 302=\overline{100101110}^2}$ et ${\tt 234=\overline{011101010}^2}$ et ${\tt 452=\overline{111000100}^2}$.
Pour vérifier on peut utiliser la commande ${\tt \widehat{\;}}$ qui correspond à ${\tt xor}$ en Python.
3^5
6
302^234
452
Cette instruction n'est pas au programme.
Q8. Ecrire une fonction dec2signed(n)
qui reçoit en entier n
supposé être entre $-128$ et $127$ et donne en sortie son codage d'entier signé sur 8 bits sous la forme d'une liste.
Par exemple dec2signed(56)
renvoie [0, 0, 1, 1, 1, 0, 0, 0]
et dec2signed(-56)
renvoie [1, 1, 0, 0, 1, 0, 0, 0]
.
Q9. Ecrire une fonction signed2dec(L)
qui reçoit une liste des chiffres du codage de n
comme entier signé $8$ bits et renvoie la valeur décimale de n
.
Par exemple signed2dec([0, 0, 1, 1, 1, 0, 0, 1])
renvoie 57
et signed2dec([1, 1, 0, 0, 0, 1, 1, 1])
renvoie -57
.
Q10. Utiliser ces fonctions pour:
L'addition est-elle correcte ?
Q11. Ecrire une fonction temps(chaine)
qui prend en argument une chaîne de caractères sous la forme '${\tt hhmmss.ss}$' représentant une durée (par exemple ${\tt 092828.02}$ correspond à 09 h 28 min 28,02 secondes) et renvoie un flottant égal à cette durée en secondes.
Q12. Ecrire une fonction angle(chaine, card)
qui prend en argument une chaîne de caractères sous la forme d'une longitude '${\tt dddmm.mmmmm}$' ou d'une latitude '${\tt ddmm.mmmmm}$' (par exemple 4754.68988 représente la latitude 47°54,68988’ et 00154.69147 représente la longitude 001°54,69147’), ainsi qu'une chaîne caractères ${\tt card}$ égale à '${\tt N}$', '${\tt S}$', '${\tt E}$' ou '${\tt O}$' et renvoie le flottant signé correspondant
à la valeur de l’angle en degré (il faudra convertir les minutes d’angle en valeur décimale).
On rappelle qu'au Nord et à l'Ouest les angles sont comptés positivement et qu'au Sud et à l'Est ils sont comptés négativement.
Par exemple angle('00154.69147', 'E')
renvoie -1.9115245
et angle('4754.68988', 'N')
renvoie 47.911498
.