Bienvenue dans la matrice ...
I. Systèmes de numération¶
On considère les systèmes de numération positionnels (comme la représentation des nombres en base 10 que nous utilisons habituellement)
C'est-à-dire : les chiffres représentent différentes valeurs selon leur position dans l'écriture d'un nombre
- "121" ?
- le '1' à gauche vaut 100
- le '2' vaut 20
- le '1' à droite vaut 1
Cuturel : il a existé bien d'autres systèmes de numérations.
Ex : chez les Mayas (système répétitivo-additif)
Ex : chez les romains (système additif - soustractif)
I.1 Les bases¶
Les bases de numération couramment utilisées en informatique :
base 10 (décimal) : avec les symboles
0,1,2,3,4,5,6,7,8,9base 2 (binaire) : avec les symboles
0,1base 8 (octal) : avec les symboles
0,1,2,3,4,5,6,7base 16 (hexadécimal) : avec les symboles
0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
En base $b$, on utilise $b$ symboles ("chiffres")
I.2 Ecriture d'un nombre¶
L'écriture d'un nombre (entier naturel) est une suite de symboles
Les nombres sont habituellement notés en base 10 : par exemple $157$
Lorsque la base a besoin d'être précisée, on note :
- $\overline{101}^2$, $\overline{a_n...a_1a_0}^b$ ou $101_2$, ${a_n...a_1a_0}_b$ (notation mathématique)
- $b01110$, $o777$, $xE9$ (notation informatique)
Gros-boutisme, petit-boutisme¶
Par convention, le symbole le plus significatif est placé en premier (à gauche) (convention "big-endian" ou "gros-boutiste")
NB : sur quelques machines, c'est le symbole le moins significatif qui est placé en premier (convention "little-endian" ou "petit-boutiste")
NB : l'origine de ces termes racontée sur Wikipedia
I.3 De l'écriture à la valeur¶
$\overline{752}^{10}$ vaut $7 \times 10^2 + 5 \times 10^1 + 2 \times 10^0$ = $752$
$\overline{101}^2$ vaut ??
$1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0$ = $5$
$\overline{133}^8$ vaut ??
$1 \times 8^2 + 3 \times 8^1 + 3 \times 8^0$ = $91$
$\overline{AF}^{16}$ vaut ??
$10 \times 16^1 + 15 \times 16^0$ = $175$
Formule générale : $\overline{a_n...a_1a_0}^b$ vaut ??
$\overline{a_n...a_1a_0}^b = a_0\times b^0 + ... + a_n\times b^n =\displaystyle \sum_{k=0}^n a_k\times b^k$
A Retenir¶
I.4 De la valeur à l'écriture¶
Pour écrire un nombre $x$ (entier naturel) dans la base $b$, on cherche à le décomposer :
$x = \displaystyle \sum_{k=0}^n a_k b^k$ avec $0 \leq a_k < b$
On obtient alors l'écriture $\overline{a_n...a_1a_0}^b$ (écriture unique si l'on impose $a_n \neq 0$)
Exemple : écriture de 38 en base 3 ?
NB : $n = max\{k \in \mathbb{N} \,|\, b^k \leq x\}$ : l'exposant de la plus grande puissance de $b$ inférieure ou égale à $x$
quelle est la plus grande puissance de 3 inférieure à 38 ?¶
Les puissances de 3 : 1, 3, 9, 27, 81 ...
$38 = 1 \times 27 + 1 \times 9 + 0 \times 3 + 2 \times 1 $ d'où l'écriture $\overline{1102}^3$
ou bien, par divisions successives¶
$x = \displaystyle \sum_{k=0}^n a_k b^k = a_0 + a_1\times b^1 + ... + a_n\times b^n $
Donc $x \% b =$ ?
$x \% b = a_0$
Par division entière $x$ $//$ $b$ $= ?$
Par division entière $x$ $//$ $b$ $= a_1 + a_2 \times b^1 + ... + a_n\times b^{n-1}$
NB : $a_0$ $//$ $b = 0$ car $0\leq a_0 < b$
par divisions successives¶
$x = \displaystyle \sum_{k=0}^n a_k b^k = a_0 + a_1\times b^1 + ... + a_n\times b^n $
$x \% b = a_0$
$x$ $//$ $b$ $= a_1 + a_2 \times b^1 + ... + a_n\times b^{n-1}$
De proche en proche, on trouve $a_0$, $a_1$, ... tous les symboles de l'écriture
Exemple : écriture de 38 en base 3 (par divisions successives) ?
$38 \% 3$ = ...
$38$ $//$ $3$ = ...
Finalement, c'est la division euclidienne ...
les restes sont les chiffres en base b (le moins significatif d'abord)
1.5 Langages de programmation¶
(HP) La plupart des langanges offrent la possibilité d'écrire en décimal / octal / hexadécimal / binaire
#include <stdio.h>
// en C
int main(){
int x = 017; /* notation octale */
int y = 0x10; /* notation hexadécimale */
int z = 17; /* notation décimale */
printf("Ecriture décimale : %d %d %d\n",x, y, z);
printf("Ecriture octale : %o %o %o\n",x, y, z);
printf("Ecriture hexadécimale : %x %x %x\n",x, y, z);
return 0;
}
Ecriture décimale : 15 16 17 Ecriture octale : 17 20 21 Ecriture hexadécimale : f 10 11
(* OCaml *)
print_int 0o11;;
print_newline ();;
print_int 0x11;;
print_newline ();;
- : unit = ()
9
- : unit = ()
- : unit = ()
17
- : unit = ()
II. La base 2¶
Un bit : unité élémentaire d'information
- 0/1
- tension haute / basse
- transistor passant / bloqué
Un octet : une séquence de 8 bits. $2^8=256$ octets différents.
Sur $N$ bits, on peut représenter $2^N$ séquences / valeurs distinctes .
La base 2 en informatique¶
En machine, l'information est manipulée en binaire
- types de base codés comme séquence de bits : 8,16,32,64 bits (1,2,4,8 octets)
Pour rendre cette information plus lisible, on est parfois amené à regrouper :
un symbole octal permet de représenter 3 bits (cf permissions fichiers Linux : rxw -> 7)
un symbole hexadécimal permet de représenter 4 bits ($1010_2$ -> A)
2 symboles hexadécimaux permettent de représenter 8 bits : (cf table ASCII)
8 symboles hexadécimaux permettent de représenter des adresses 32 bits : adresse
0xffffffff
Valeurs à connaître en base 2¶
$\bullet\quad \overline{0}^2$ = $0 \qquad \bullet\quad\overline{1}^2$ = $1 \qquad \bullet\quad\overline{10}^2$ = $2 \qquad \bullet\quad\overline{11}^2$ = $3$
$\bullet\quad \overline{100}^2$ = $4 \qquad \bullet\quad \overline{1000}^2$ = $8 \qquad \bullet\quad \overline{10000}^2$ = $16 \qquad$ ...
$\bullet\quad \overline{100..0}^2$ ($1$ suivi de n $0$) = $2^n$
$\bullet\quad \overline{111}^2$ = $7 \qquad \bullet\quad \overline{1111}^2$ = $15 \qquad$ ...
$\bullet\quad \overline{11..1}^2$ (n $1$ successifs) = $2^n-1$
Conversion de la base 2 vers la base 10 :¶
$\overline{1101}^2$ vaut $1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0$ = $13$
Conversion de la base 10 vers la base 2 :¶
On cherche une (la) décomposition $\displaystyle \sum_{k=0}^n a_k 2^k$ avec $0 \leq a_k < 2$
Ex : écriture de 20 en 2 ?
$20 = 1 \times 16 + 0 \times 8 + 1 \times 4 + 0 \times 2 + 0 \times 1 = \overline{10100}^2$
ou bien, par divisions successives : $20 \% 2 = 0$ ...
- Table de multiplication en base 2 :
| x | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
C'est bien plus simple qu'en base 10
Exercice :¶
Calculer $\overline{1101}^2 + \overline{101}^2$
Calculer $\overline{1001}^2 \times \overline{1001}^2$
$\overline{1101}^2 + \overline{101}^2 = \overline{10010}^2$ ($13 + 5 = 18$)
$\overline{1001}^2 \times \overline{1001}^2 = \overline{1010001}^2$ ($9\times 9 = 81$)
A savoir¶
En base 2 :
multiplier un nombre par 2, c'est ajouter un 0 à droite de son écriture
l'écriture d'un nombre pair se termine par 0
l'écriture d'un nombre impair se termine par 1
diviser par deux (division entière), c'est supprimer le bit le plus à droite
III. Les types entiers et leurs représentations¶
III.1 les types entiers signés/non-signés en C¶
int: entier signé (sur 16, 32 ou 64 bits, selon la machine)unsigned int: entier non signé (idem)
(HP : short, unsigned short, long, unsigned long ... idem, le nombre de bits dépend de la machine)
Pour utiliser un codage sur un nombre de bits précis, on utilise #include <stdint.h> :
uint8_tpour un codage sur 8 bits ($2^8=256$ valeurs : de 0 à 255)int8_tpour un codage sur 8 bits (256 valeurs : de -128 à +127)uint16_t,int16_t,uint32_t,int32_t,uint64_t,int64_t, pour des codages sur 16, 32 ou 64 bits
NB : on retrouve le même principe dans la plupart des langages de programmation.
NB : cas particulier des entiers de taille "illimtée" en Python (codés sur un variable de bits)
III.2 Entiers ayant une représentation en machine¶
NB : sur $N$ bits, on peut représenter $2^N$ valeurs
Représentation sur :
- 8 bits = 1 octet : $2^8 = 256$ possibilités
- 16 bits = 2 octets : $2^{16} = 2^{10} * 2^6 \simeq 64$ mille possibilités
- 32 bits = 4 octets : $2^{32} = 2^{10} *2^{10} *2^{10} * 2^2 \simeq 4$ milliards de possibilités
- 64 bits = 8 octets : $2^{64} \simeq 16$ milliards de milliards de possibilités
NB : $2^{10}=1024\simeq 1000$
Les entiers non signés (unsigned int) :
uint8_tsur 8 bits : de 0 à 255uint16_tsur 16 bits : de 0 à 65 535uint32_tsur 32 bits : de 0 à 4 294 967 295uint64_tsur 64 bits : de 0 à ...
Les entiers signés (signed int) :
int8_tsur 8 bits : de -128 à 127 (256 possibilités)int16_tsur 16 bits : de -32 768 à 32 767int32_tsur 32 bits : de -2 147 483 648 à 2 147 483 647int64_tsur 64 bits : de ... à ...
NB : on ne peut représenter qu'un nombre fini d'entiers en machine ... (donc pas $\mathbb{N}$)
A retenir pour les uint8_t, uint16_t ... int8_t ... :¶
Attention aux débordements :
avec des
uint8_t: $255 + 1$ = $0$avec des
int8_t: $127 + 1$ = $-128$choisir un type adapté :
- signé / non signé (attention un type non signé ne prend jamais de valeur négative ...)
- de taille adaptée : éviter les débordements, sans gâcher inutilement de la mémoire
NB : dans la plupart des cas : int / unsigned int conviennent
// Débordement sur les entiers : exemple1
#include <stdio.h>
#include <stdint.h>
int main(){
uint8_t x = 255;
int8_t y = 127;
x += 1; y += 1;
printf("%d %d", x, y);
return 0;
}
0 -128
// Débordement sur les entiers : exemple2
#include <stdio.h>
#include <stdint.h>
int main(){
uint8_t x = 255;
while (x >= 0){ // boucle infinie
x-=1;
}
return 0;
}
// Débordement sur les entiers : exemple3
#include <stdio.h>
#include <stdint.h>
int8_t fact(int8_t n){
if (n == 0){
return 1;
} else {
return n*fact(n-1);
}
}
int main(){
printf("%d\n", fact(6));
printf("%d\n", fact(-1));
}
-48 0
III.3 Représentation des entiers non signés¶
C'est celle de l'écriture en base 2 sur un nombre de bits donné par le type.
Exemples :
uint8_t x0 = 1->00000001uint8_t x1 = 8->00001000uint8_t x2 = 27->00011011(16+8+2+1)uint8_t x3 = 255->11111111uint16_t x4 = 255->0000000011111111
Exercice¶
Comment comparer deux entiers non signés à partir de leur représentation binaire ? (par exemple, sur 8 bits) :
A : $a_7a_6a_5a_4a_3a_2a_1a_0$
B : $b_7b_6b_5b_4b_3b_2b_1b_0$
On parcourt les bits en parallèle de gauche à droite :
- Pour i allant de 7 à 0
- si $a_i > b_i$ : resultat "A > B"
- sinon si $a_i < b_i$ : resultat "A < B"
- resultat : "A == B"
NB : c'est la comparaison de l'ordre lexicographique
NB : le processeur (ALU) dispose de circuits (portes logiques) permettant de faire cette opération en un cycle d'horloge
III.4 Les opérations "bit à bit" (sur uint)¶
Les entiers non-signés sont représentés comme séquences de bits.
Il est possible de les manipuler comme tels
uint8_t a = 3; // 00000011
uint8_t b = 255; // 11111111
Opérations "bit-à-bit" en C (existe aussi en OCaml) :
a & b: ET sur chacun des bits
a | b: OU sur chacun des bits
a ^ b: OU EXCLUSIF
~a: NEGATION
a >> n: décalage de n bits vers la droite (n bits disparraissent, n bits à 0 apparaissent)a << n: décalage de n bits vers la gauche (n bits disparraissent, n bits à 0 apparaissent)
// Exemples de manipulations bit à bit
#include <stdio.h>
#include <stdint.h>
int main(){
uint8_t a = 3; // ????????
uint8_t b = ~a; // ????????
uint8_t c = b << 2; // ????????
uint8_t d = b^c; // ????????
printf("%d %d %d",b, c, d); // ? ? ?
return 0;
}
// Exemples de manipulations bit à bit
#include <stdio.h>
#include <stdint.h>
int main(){
uint8_t a = 3; // 00000011
uint8_t b = ~a; // 11111100
uint8_t c = b << 2; // 11110000
uint8_t d = b^c; // 00001100
printf("%d %d %d",b, c, d);
return 0;
}
252 240 12
III.5 Stockage d'information (sur uint)¶
On peut utiliser des entiers non signés pour y stocker des informations diverses et variées.
dans un uint8_t (chaque bit correspond à un booléen)
C'est un peu technique ...
// Exemple : utiliser un uint_8 pour représenter 8 booléens
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
typedef uint8_t bitSet8;
bool getNth(bitSet8 b, int n){
return (b & (1 << n)) != 0;
}
void setNth(bitSet8* b, int n, bool val){
if (val) *b = *b | (1 << n);
else *b = *b ^ (1 << n);
}
int main(){
bitSet8 b = 0;
setNth(&b, 0, true);
setNth(&b, 4, true);
for (int i = 0; i < 8; i+=1){
if (getNth(b, i)) printf("%d:True ", i);
else printf("%d:False ", i);
}
return 0;
}
0:True 1:False 2:False 3:False 4:True 5:False 6:False 7:False
dans un uint64_t (chaque bit correspond à la présence d'un pion noir sur une des 64 cases de l'échiquier)
Coder des informations¶
Comment coder un état du jeu du "tic-tac-toe" ?¶
On note :
- 0 pour vide,
- 1 pour O
- 2 pour X
Un plateau est donc un nombre à 9 chiffres écrit en base 3.
Il y a donc $3^9 = 19683$ plateaux différents.
On peut représenter chacun d'eux par un nombre entre 0 et $3^9-1$
Sur $N$ bits, on peut stocker $2^N$ valeurs différentes
Pour stocker $n$ valeurs différentes, on a besoin de $\lceil\log_2 n\rceil$ bits
$\lceil\log_2 19683\rceil = 15$ bits. On peut donc coder un plateau de jeu par un uint16_t
codage : plateau -> uint16_t , on calcule le nombre associé à l'écriture en base 3
$1 \times 3^0 + 0 \times 3^1 + 0 \times 3^2 + 2 \times 3^3 + 2 \times 3^4 + 1 \times 3^5 + 1 \times 3^6 + 0 \times 3^7 + 2 \times 3^8 = 14311$
decodage : uint16_t-> plateau , on récupère l'écriture en base 3 à partir du nombre
$14311 = \overline{201122001}^3$
III.6 Représentation des entiers signés¶
Pour représenter un entier signé $x$ sur $n$ bits, on pourrait penser au codage suivant :
- 1 bit de signe
- n-1 bits pour $|x|$
Ce n'est pas cette représentation qui est utilisée.
Représentation des entiers signés¶
On utilise la représentation en complément à 2 :
- si $x \geq 0$ : 0 puis $n-1$ bits représentant $|x|$
- si $x < 0$ : 1 puis $n-1$ bits représentant $2^{n-1}-|x|$
Exercice : Représenter sur 8 bits les entiers signés : 84 et -84
sur 8 bits : 1 bit de signe, 7 bits pour la valeur ($2^7 = 128$)
84 est codé par 0 suivi du codage de 84 sur 7 bits :
- 0 1010100 (0 puis 64+16+4)
-84 est codé par 1 suivi du codage de 128-84=44 sur 7 bits :
- 1 0101100 (1 puis 32+8+4)
Avantage de cette représentation ? :
$84 + (-84) = 01010100 + 10101100 = (1)00000000 = 0$
NB : la retenue finale n'est pas prise en compte : il y a débordement
L'addition usuelle reste valide !¶
Exercice : donner les valeurs des entiers signés représentés par les 8 bits suivants
00100101 ?
10100101 ?
Exercice : donner les valeurs des entiers signés représentés par les 8 bits suivants
00100101 : premier bit nul : 1 + 4 + 32 = 37
10100101 :
- premier bit à 1 : c'est un nombre négatif ... calcul assez pénible ...
NB : pour déterminer la valeur d'un entier signé négatif $x$, on peut chercher son opposé¶
x : 10100101 (négatif car premier bit à 1)
$-x$ est le nombre qu'il faut additionner à $x$ pour atteindre le débordement¶
x : 10100101
-x : 01011011 = 1 + 2 + 8 + 16 + 64 = 91
Donc x = -91
IV. Les types "réels" et leurs représentations¶
IV.1 Représentation des réels¶
Représentation décimale : $27.53$ = $2 \times 10^1 + 7 \times 10^0 + 5 \times 10^{-1} + 3 \times 10^{-2}$
- la représentation décimale finie ne permet de représenter que les nombres décimaux
- tous les réels ne sont pas décimaux (ex : 1/3 = 0.33333...)
Représentation binaire : $\overline{10.011}^2$ = ??
$1 \times 2^1 + 0 \times 2^0 + 0 \times 2^{-1} + 1\times 2^{-2}+ 1\times 2^{-3}$ = $2 + 0.25 + 0.125$ = $2.375$
- la représentation binaire finie ne permet de représenter que les nombres dyadiques
- tous les réels ne sont pas dyadiques
Exercice :¶
Réprésenter en binaire 4.5
- $4.5 = 1 \times 2^2 + 0 \times 2^1 + 0 \times 2^0 + 1 \times 2^{-1}$
- $\overline{100.1}^2$
Réprésenter en binaire 4.7
- $4.7 = 1 \times 2^2 + 0 \times 2^1 + 0 \times 2^0 + ... ??? ... $
On compare ce qui reste à représenter (ici $0.7$) et la puissance suivante (ici $2^{-1} = 0.5$)
- $0.7 \geq 0.5$ : bit à 1 ... et on poursuit
- $0.2 \leq 0.25$ : bit à 0 ... etc
Pour plus de lisibilité, on multiplie par 2 les restes, et on compare à 1 : reste $0.7$
$0.7 \times 2 = 1.4 \geq 1$ : bit à 1
$0.4 \times 2 = 0.8 < 1$ : bit à 0
$0.8 \times 2 = 1.6 \geq 1$ : bit à 1
$0.6 \times 2 = 1.2 \geq 1$ : bit à 1
$0.2 \times 2 = 0.4 < 1$ : bit à 0
$0.4 \times 2 = 0.8 < 1$ : bit à 0 (cyclique !)
Au final : $4.7 = \overline{100.10110011001100....}^2$
NB : 4.7 n'est pas un nombre dyadique
IV.2 Les types réels en C¶
float: représentation machine sur 32 bitsdouble: repréentation machine sur 64 bits
IV.3 La représentation machine des types réels¶
Représentation machine des
floatetdouble:- même principe que la notation scientifique en décimal : $-15342.13241323 \simeq -1.534213\times 10^{4}$
- plus grand
floatreprésentable : $\simeq 2^{128} \simeq 10^{38}$ - plus grand
doublereprésentable : $\simeq 2^{1024} \simeq 10^{308}$
NB : pour les détails, cf Norme IEEE 754, avec de nombreuses subtilités
NB : pour les détails, cf Norme IEEE 754, avec de nombreuses subtilités
cas particuliers lorsque l'exposant vaut 000...0 ou 1111..11.
Permettent de représenter :
des nombres encore plus proche de 0 : les nombres "dénormalisés" (en dehors de la norme)
0+ et 0- $+\infty$ et $-\infty$
NaN : "not a number" (utilisé parfois comme résultat d'une division par 0 ...)
Exercice¶
A priori, combien de float différents peut-on représenter (sans tenir compte des nombres dénormalisés) ?
32 bits, donc $2^{32}$ séquences différentes, donc $2^{32}$ float (au plus)
Exercice¶
Comment comparer deux float à partir de leur représentation binaire ? :
- 1 bit pour le signe
- 8 bits pour l'exposant
- 23 bits pour la mantisse
A : $as$ $ae_7ae_6ae_5ae_4ae_3ae_2ae_1ae_0$ $am_{22}am_{21}am_{20}...am_0$
B : $bs$ $be_7be_6be_5be_4be_3be_2be_1be_0$ $bm_{22}bm_{21}bm_{20}...bm_0$
- on compare les signes : si différents, on conclut
- si égaux, on compare les exposants : si différents, on conclut
- si égaux on compare les mantisses
- si égaux, on compare les exposants : si différents, on conclut
NB : au final, c'est le même principe que pour les entiers : on compare les bits de gauche à droite
Exercice¶
Les float sont en nombre finis ... Quel est l'écart entre deux float successifs ?
avec la notation scientifique décimale avec 6 chiffres après la virgule
Ecart entre $1.534213\times 10^{4}$ et $1.534214\times 10^{4}$
$0.000001 \times 10^4$
Pour les float, l'écart correspond à la valeur du dernier bit de la mantisse, et il faut tenir compte de l'exposant
$2^{-23} \times 2^e$
NB l'écart n'est pas absolu : il dépend de l'exposant. Les float proches de 0 sont plus resserrés que les grands float
A retenir pour les float et double :¶
il est peu pertinent de tester l'égalité de deux flottants.
On utilise : if (abs(x-y) < 1e-6) ... (pour des float)
ou bien if (abs(x-y) < 1e-14) ... (pour les double)
Pourquoi ?¶
- La représentation machine des réels est souvent approchée
- Les calculs sur les flottants sont souvent inexacts (arrondis)
- Phénomène d'absorption lorsqu'on additionne deux flottants très éloignés
// Exemple1 : représentations approchées
#include <stdio.h>
int main(){
float x = 1453131345.0; // il n'y a que 7 chiffres significatifs
float y = 1453131365.3;
if (x == y) {
printf("???");
}
return 0;
}
???
// Exemple2 : calcul sur des représentations machines approchées
#include <stdio.h>
int main(){
if (0.1 * 3 != 0.3) {
printf("???");
}
return 0;
}
???
// Exemple3 : erreurs d'arrondis
#include <stdio.h>
int main(){
float a = 0.0;
for (int i = 1; i<=100000;i+=1){
a += 1e-5;
}
printf("%f",a);
return 0;
}
1.000990
// Exemple4 : absorption
#include <stdio.h>
int main(){
double z = 14e18 + 2e-8 - 14e18;
if (z == 0.0) {
printf("???");
}
return 0;
}
???
// Exemple5 : calculs approchés
#include <stdio.h>
int main(){
float s=0.0, t=0.0;
for (int i = 1; i<1000; i+=1){
s += 1.0/i;
}
for (int i = 999; i>0; i-=1){
t += 1.0/i;
}
printf("%f %f", s, t);
}
7.484478 7.484472
NB : additionner / soustraire des nombres proches permet de limiter les erreurs d'arrondis