Inutile que je fignole cette page, vous trouverez bien mieux sur internet. En particulier http://sdz.tdct.org/sdz/les-calculs-en-binaire.html
On peut représenter des nombres par une combinaison de zéros et de uns. Chaque chiffre binaire (BInary digIT) est appelé BIT. 8 bits forment un octet (BYTE). Mais plusieurs codifications sont envisageables. La plus utilisée est le binaire (ou binaire naturel en cas d'ambiguïté).
passage binaire (indice b) -> décimal (indice d) :
1011001b représente :
1x26 +0x25 +1x24 +1x23 +0x22 +0x21 +1x20
= 1x64 +0x32 +1x16 +1x8 +0x4 +0x2 +1x1
= 89d
Bien sûr, avec un peu d'habitude vous connaîtrez les premières puissances de deux : 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 (210, appelé 1k)... 220=1M, 230=1G...
à l'inverse, pour transformer 89d en binaire, on peut utiliser la
méthode des divisions successives
par 2 : on divise successivement par 2 jusqu'à un résultat de 0,
les restes successifs (de bas en haut) forment le nombre binaire.
De tête, j'utilise une autre méthode : 89 = 1x64 reste 25 à répartir. Donc 0x32, 1x16, il reste 9, 1x8 reste 1 donc 0x4, 0x2, 1x1.
Dans la pratique, la mémoire des ordinateurs est découpée en octets. Si l'on se limitait à des entiers sur 8 bits, nous ne pourions utiliser que des nombres entre 0 et 255, ce qui n'est pas acceptable. Nous allons donc stocker les entiers sur plusieurs octets. Malheureusement, en regardant des suites de 0 et 1, rien ne peut nous indiquer qu'à un endroit, un nombre se finit (vous metteriez quoi, un 0 ou un 1, c'est à dire allumé ou éteint ?).
La seule solution est de fixer (par le programmeur) le nombre d'octets utilisés par chaque entier. C'est pourquoi il faut les déclarer. En C, un "char" est un entier sur un octet, un "short" sur 2, un "long" sur 4. Au programmeur de se débrouiller pour empêcher qu'on dépasse la place prévue (le processeur ne le fait pas). C'est le même principe dans la plupart des langages. Sauf Python, où il n'y a pas de limite (j'ai déja essayé plusieurs Mo, ça fonctionne, mais c'est plus lent, de l'ordre de la seconde pour un calcul. Mais le nb fait quand même 400 000 chiffres en décimal).
On utilise les chiffres 0 à 9 puis les lettres A à F. 3A5h vaut 3x162 + 10x161 + 5x160 =3x256 + 160 + 5 = 933d . On passe de l'hexa au décimal par divisions successives par 16. Transformer de l'hexadécimal en binaire est enfantin : il suffit de remplacer chaque chiffre par sa valeur binaire sur quatre bits : 3A5h = 0011 1010 0101b (on peut vérifier que ça vaut 933d). En effet, 001110100101b
= 0.211 +0.210 +1.29 +1.28 +1.27 +0.26 +1.25 +0.24 +0.23 +1.22 +0.21 +1.20
= (0.23 +0.22 +1.21 +1.20)28 +(1.23 +0.22 +1.21 +0.20)24 +0.23 +1.22 +0.21 +1.20
= 0011bx28 +1010bx24 +0101bx20
= 3dx162+10dx16+5d
=3A5h
bien sûr il est important de savoir passer rapidement de l'hexa au binaire pour toutes les combinaisons de 4 chiffres binaires : |
|
Contrairement à ce que beaucoup de gens croient, aucune machine ne compte en hexadécimal. Elles travaillent toutes en binaire, et ne se servent de l'hexa que pour dialoguer avec nous (nous nous trompons trop souvent dans de longues listes de 0 et 1).
Dans certains cas particuliers, on utilise l'octal (base 8, donc chiffres de 0 à 7). Son intérêt est que le passage en binaire se fait par paquets de 3 bits. L'application la plus connue est la gestion des droits d'accès aux fichiers, où 3 bits précisent les 3 droits Read, Write, eXecute.
Si vous achetez un voltmètre numérique (10€ en supermarché), la valeur mesurée est transmise à l'afficheur en numérique. Mais elle est auparavant transformée en décimal, chaque chiffre décimal est transmis à un afficheur en binaire naturel (sur 4 bits). C'est le BCD : la juxtaposition des valeurs binaires (sur quatre bits) des chiffres décimaux. Donc 583d se notera 0101 1000 0011bcd. Cette codification pose deux problèmes principaux :
On désire qu'en passant d'un nombre à son suivant (+1) ou précédent (-1), on n'aie qu'un seul bit qui change. On désire de plus que les zéro rajoutés à gauche d'un nombre ne soient pas significatifs. Sur deux bits, on utilisera les codes 00, 01, 11 puis 10. Sur 3 bits, on gardera les mêmes premiers codes (précédés d'un zéro). La combinaison suivante débutera donc obligatoirement par 1, donc les deux autres bits ne peuvent pas changer. On continuera à prendre les mêmes codes, en ordre inverse, débutant par 1 : 110, 111, 101 et 100. En passant à 4 bits, on précède ces 8 cas d'un 0, les 8 suivants étant les mêmes, dans l'ordre inverse, précédés d'un 1. Ce codage est utilisé dans les cas où des valeurs ne peuvent varier que par incrémentation ou décrémentation : si l'on voit que plus d'un bit a changé entre deux valeurs, c'est qu'il y a eu un problème (en général le nombre a changé trop vite, le système n'a pas eu le temps de lire toutes les valeurs). Il faut par contre passer en binaire naturel pour tout autre calcul que l'incrémentation.
Un exemple est le capteur de position angulaire (voir transparent T4). Un capteur incrémental comptant des impulsions est utilisé par exemple sur les robots. C'est un disque, entaillé d'encoches régulièrement espacées, passant devant un capteur optique. Certaines impulsions trop rapprochées peuvent être "oubliées" en cas de choc par exemple, et donc occasionner un mauvais réglage. A l'initialisation et en cas de problème, on doit ramener toutes les articulations en position de repos, puis mettre les compteurs à 0, avant de pouvoir utiliser le robot. Un capteur absolu quand à lui donne toujours le position exacte (bien qu'il y ait souvent une démultiplication, le mouvement total fait plus d'un tour mais aucun choc ne fera sauter le capteur d'exactement un tour). On utilise un code binaire réfléchi car un autre codage nécessiterait, pour passer d'une valeur à la suivante, une modification simultanée de plusieurs bits (voir explication sur T4)
Vous pouvez choisir tout code qui vous intéresse, tant qu'il existe une règle pour savoir ce que cette suite de 0 et de 1 représente. Par exemple, pour un code barre simple (juste des 0 et 1), il faut choisir des combinaisons dont l'ordre inverse est réservé à la m&ecric;me valeur (si on lit l'étiquette dans l'autre sens). Il y a aussi les codes de type "3 parmi 5" : les chiffres décimaux sont représentés sur 5 bits, avec toujours 2 uns et 3 zéros. Le codage "excès de 3" est plus adapté aux soustractions en décimal. Pour plus de détails, Google est votre ami.
Dernier code dont je vais parler : l'ASCII. Les nombres sont en décimal, chaque chiffre est son code ASCII, donc directement affichable. Le code vaut 48+le chiffre (en hexa 0x30+i).
Que vaut 10010.011b en décimal ? 32.375d.
En effet, en décimal c'est 3*101 + 2*100 + 3*10-1 + 7*10-2 + 5*10-3, donc après la virgule, le dixième, le centième... Ici, en binaire, après la virgule, nous avons 0*2-1 (demi) + 1*2-2 (quart) + 1*2-3 (huitième). Un quart (0.25) plus 1/8 (0.125) donnent bien 0.375. Donc passer du binaire au décimal est facile (surtout avec une calculatrice ;-).
L'inverse l'est moins. En effet certains nombres réels se représentent mal dans certaines bases. Par exemple 1/3 en base 10 nécessite un arrondi (reste à décider la précision désirée, donc le nombre de chiffres après la virgule). Pourtant 1/3 se noterait 0.1 en base 3 (chiffres entre 0 et 2, avant la virgule l'unité, la "troisaine", la "neuvaine"... et derrière le tiers, le 9ème...
Autre exemple : 0.1d donne une suite infinie en binaire : 0.0001100110011001100... : pas 1/2, pas 1/4, pas 1/8, mais 1/16 et 1/32... C'est pour cela qu'en math, un sous-ensemble des nombres réels ℝ s'appelle les nombres décimaux ⅅ : tous ceux qui se représentent par une suite de chiffres finie en décimal. Dans un ordinateur, on ne pourra donc stocker qu'une partie des nombres réels : ceux qui se représentent par une suite finie de chiffres en binaire. On aurait pu les appeler les "binimaux", on a préféré les appeler des "flottants", je dirai pourquoi plus loin. De plus on se limite souvent à un certain nombre de chiffres après la virgule (23 bits par exemple). Donc dans cet exemple je serai précis à 2-23, qui vaut environ 10-7, c'est ce que l'on appelle la "simple précision" dans beaucoup de langages, dont le C.
pour représenterla virgule, nous n'avons pas la possibilité d'utiliser ni un 0 ni un 1, on ne les reconaîtrait pas parmi les la suite des chiffres. On a deux solutions :
Sur 32 bits, celui le plus à gauche est le signe (0 si positif, 1 si négatif). Puis il y a 8 bits pour l'exposant, les 23 restant pour la mantisse. La mantisse est la suite de chiffres binaires sauf le premier 1, commençant à gauche, complétée par des zéros à droite si nécessaire (et tronquée s'il y en avait plus de 23). L'exposant est de combien il faut décaler la virgule dans la mantisse, en supposant qu'initialement elle est derrière le premier 1 (qui n'est même pas stocké dans la mantisse), vers la droite si positif, la gauche si négatif. Ce décalage est en fait stocké en lui additionnant 127 (appelé le "biais"). On comprendra mieux sur un exemple :
-10110.011 (22.375 en décimal) sera représenté par :
En 64 bits, le bit de gauche est aussi le signe, suivi de l'exposant sur 11 bits (avec un biais de 1023), et 52 bits de mantisse. Pour notre exemple, l'exposant vaut 4+1023=10000000011, donc :
1 10000000011 0110011000000000000000000000000000000000000000000000 (en hexa : C03660000000000)
cas particulier, 0 est réprésente par une suite exclusive de zéros (32 ou 64 pour les deux cas étudiés ici), ce qui aurait dû valoir un nombreb négatif, d'exposant -biais, valant 1,00000..... et la virgule décalée de 127 ou 1023 crans à gauche. Donc un nombre très petit, qui correspondant à l'erreur de précision sur les flottants proches de 0.
Ah, la précision. En 32 bits, la mantisse fait 23 bits. Donc le plus petit écart entre deux nombres est en changeant le dernier chiffre de la mantisse. Quelle que soit la position de la virgule (des grands nombres ou de très petits), la différence est de 2-23 valant environ 10-7. Cette erreur est relative, c.a.d par rapport à la valeur absolue du nombre. Ca veut donc dire qu'en décimal, en notation scientifique, quel que soit l'exposant, seuls les 7 premiers chiffres de la mantisse sont justes (et qu'il est impossible d'additionner deux nombres de plus de 107 d'écart). Exemple : 10/3 = 3.333333, les chiffres suivants seraient n'importe quoi. En C, le programme suivant :
#include <stdio.h>
int main(void)
{
float x=10/3.0;
printf("%20.15f\n",x);
}
affiche : 3.333333253860474 (c'est pour cela que le C n'affiche par défaut que 6 chiffres après la virgule).
en Python, 10/3 affiche 3.3333333333333335. Il utilise 64 bits, l'erreur relative est de l'ordre de 10-15 (si je demande d'afficher plus de chiffres, ce sera aussi n'importe quoi : print(("%30.26f")%(10/3)) donne 3.33333333333333348136306995).
C'est bien parce que sur les float il y a des imprécisions, qu'on les distingue des entiers, où les résultats sont toujours justes (sauf si l'on dépasse le nombre de bits alloués).
Supposons être sur 8 bits (c'est rare, mais plus court à écrire). Soit N=41d=00101001 (sur 8 bits) On ne code PAS -N par 10101001 car N+(-N) ne donne pas 0 ! :
exercice 1 : vérifiez que retrouvez N en calculant le complément à deux de -N (toujours en complémentant et ajoutant 1, surtout pas soustraire !)
exercice 2 : calculez -N sur 16 bits, et sur 32 bits.
il y a plein d'autres choses à dire, mais ici ce serait trop long.
le premier calcul à connaître est comment on passe au suivant (nommé "incrémentation", c'est à dire ajouter 1). C'est la même chose dans toutes les bases. On commence par 0, puis on passe à la prochaine unité, jusqu'à la dernière. Le suivant est obligatoirement 10 : c'est à dire prochaine "dizaine" (en binaire je dirais "deuxaine", en hexa "seizaine") et on repart sur l'unité 0). Donc en binaire :
0, 1 puis 10, 11, puis prochaine "quatraine" : 100. De là, comme en décimal si vous savez compter de 0 à 99, vous mettez une centaine devant et vous savez compter jusqu'à 199. Donc 100, 101, 110, 111. Puis vous recommencerez avec 1000, etc...
idem en hexa : 0...9,A...F,10...19,1A...1F,20...99,9A...9F,A0...FF,100...
Facile : 0+0=0, 0+1=1, 1+1=0 et je retiens 1 (éventuellement 1+1+1=1 et je retiens 1). Reste à poser l'addition, en faisant bien attention à bien aligner les chiffres de même poids (unités, deuxaines, quatraines...). S'il y a une virgule, il faut bien entendu aligner les virgules. Exemples :
vérifiez, en traduisant en décimal !
Je ne parle pas ici de la soustraction : c'est une opération relativement délicate, même en décimal : pour A-B, il faut rechercher "ce qu'il faudrait ajouter" à B pour obtenir A. C'est à dire le complément, dans A, de B. Dans la pratique, en binaire, on préfère ajouter le "complément à 2" de B (qui vaut -B dans le cas des entiers, voir plus haut)
une seule table de multilication à savoir : 1*1=1 ! (et bien sûr 0* n'importe quoi = 0). Posons la multiplication de 45*10 :
Quelles que soient les valeurs, à chaque fois, vous multipliez par 0 ou par 1 (facile), puis vous décalez d'un cran. Et à la fin, vous additionnez le tout. En fait, pour cet exemple, 10*N = 2*N + 8*N (décalage de 1 puis de 3, voir plus loin).
Pour les nombres à virgule, comme vous le faisiez en décimal, vous posez la multiplication sans vous occuper des virgules, puis vous placez la virgule (somme des deux décalages de la virgule). Exercice : 5,75 * 3,25
il faut la poser (comme en décimal). Simplement, inutile de se demander "combien de fois ça rentre" : c'est soit 0 soit 1. On peut s'arrêter à un résultat entier, ou s'il y a un reste, continuer après la virgule.
exemple 1 : 231/12 = 9 reste 3, ou, si je continue après la virgule, 9.25 ; exemple 2 : 10/3 (suite infinie) ; exemple 3 : 1/10 (un bon moyen pour calculer 1/10ième en binaire) :
Pour les soustractions, je sais que ce n'est pas facile. Vous pouvez utiliser la même démarche qu'en décimal. L'ordi, lui, fait l'addition du complément à 2. Moi, souvent, je triche : je traduis en décimal, je fais la soustraction, je retraduis en binaire, et je vérifie que la somme est bonne.
Le processeur ne sait faire que des calculs sur des entiers. Au début, il fallait prévoir une bibliothèque mathématique (c.a.d un ensemble de programmes). Puis on a créé des "coprocesseurs mathématiques" qui faisaient le calcul plus rapidement; puis on les a intégrés dans le processeur (mais pas dans l'ALU), depuis le Pentium. Il reste que ce qui permet de comparer les gros ordinateurs est leur nombre de FLOPS (opérations en flottants par seconde).
Abordons quand même la méthode (approximativement) : pour une addition, il faut d'abord aligner les virgules (et donc que les deux exposants soient égaux). Ensuite on additionne comme des entiers. Pour la multiplication, on ne s'occupe pas de la virgule, on fait le produit des mantisses et on gère la position de la virgule (il faut les additionner).
les opérations logiques s'effectuent (en une fois) à tous les bits de la variable. Ces opérations ne se font que sur des bits de même rang, sans influence sur les rangs voisins (contrairement aux opérations arithmétiques, via la retenue). On suppose 1=vrai, 0=faux.
ET : =1 uniquement si les 2 bits valent 1; OU : =1 si l'un ou l'autre ou les deux ; OU exclusif : si l'un ou l'autre mais pas les deux ; complément : chaque bit est complémenté (on l'appele "complément à 1", quand on veut le distinguer du complément à 2).
Dans beaucoup de langages, ET se note &, OU se note |, le complément se note ~, le OU exclusif XOR ou ^.
10110110 10110110 10110110 ET 00001111 OU 00001111 XOR 00001111 ~ 10110110 ----------- ----------- ------------ ------------ 00000110 10111111 10111001 01001001
on a aussi le décalage à droite (qui correspond à une division par 2 pour un entier positif) qui perd le bit de poids faible, mais recopie le bit de poids fort (donc le signe est gardé).
Exemples : sur 8 bits, 10110110<<1 donne 01101100, 10110110<<5 donne 11000000 et 10110110>>1 donne 11011011 (je note les nombres en binaire, généralement ce sont des variables).
Quand on a un ensemble de bits, et qu'on ne veut en "regarder" qu'un seul, on utilise un masque, et une opération ET : soit un nombre "e" contenant 8 bits notés de e7 à e0. Si je veux cacher tous les bits sauf e3, je le masque avec 00001000 (qui se note 1<<3) :
e7e6e5e4e3e2e1e0 & 0 0 0 0 1 0 0 0 ----------------- 0 0 0 0 e3 0 0 0si le résultat est nul, c'est qu'e3 vallait 0.
Avec le même masque, mais une opération OU, on garde tous les bits sauf e3 qui devient un 1 (forçage à 1). Avec un XOR ils sont tous gardés sauf e3 qui est inversé. En prennant un masque avec que des 1 et un seul 0, on garde TOUS les bits, sauf un qui est forcé à 0. On peut aussi utiliser des masques à "plusieurs ouvertures" (plein d'utilisations utiles, mais je ne peux pas tout détailler).
Le segment a s'allume si s0=0, s'éteint sinon (idem pour les autres segments). On cherche le schéma interne du composant X qui permet d'afficher le chiffre correspondant au nombre binaire disponible en entrée (e0 bit de poids faible) On peut en premier lieu faire une table de vérité, donnant l'état des 7 sorties si pour les 16 combinaisons possibles des 4 entrées ei. Puis on peut rechercher l'équation de chaque sortie en fonction des entrées (Karnaugh par exemple), puis on peut rechercher si certains termes apparaissent dans plusieurs équations afin de ne pas câbler plusieurs fois la même fonction (je dis "on peut", moi je peux, mais vous ? ) je l'ai traité ici).
En utilisant plusieurs afficheurs, on affichera un nombre binaire en hexa ou un nombre BCD en décimal, pour des nombres de bits supérieurs à 4
étudier le circuit : (transparent T3)
_ _ _ _
s= r NOR 2 ; 2= a NOR b = a.b ; r= 3 NOR 4 ; 3= b NOR b = b ; 4= a
a b
r s 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0
_ _ donc r = ba ; s= ba + abc'est donc un additionneur binaire. (s=somme r=retenue, 0+0=0, 1+0=1, 1+1=0 et je retiens 1).
Exercice : faire le même composant uniquement avec des NAND.
A l'aide de ce composant, on peut maintenant faire un additionneur sur plusieurs bits (en général au moins 8, analysons ici uniquement le cas de 3 bits).
a2 a1 a0
|
|
| +
b2 b1 b0
|
-> r0, r1, r2 sont les retenues intermédiaires
|
| r3
s2 s1 s0
|
Trouver le schéma d'un composant admettant en entrée un nombre binaire naturel, donnant en sortie son équivalent en code binaire réfléchi. On se limitera aux nombres de 3 bits. On peut trouver g1 et g0 par tableau de Karnaugh:
exercice (d'ailleurs, c'est plutôt celui-là que je propose en cours) : traduire dans l'autre sens, de Gray vers binaire (c'est ce composant que l'on utilisera pour entrer une valeur d'un capteur Gray, dans un système numérique).
Le décodeur 3 dans 8 comporte 3 entrées e0 à e2, 8 sorties s0 à s7. Il allume une et une seule sortie à la fois, celle correspondant à la valeur binaire donnée en entrée (donc entre 0 et 7, ce qui fait entre 000 et 111 en binaire). A l'inverse, un encodeur 8 dans 3 pose quelques problèmes : quelle sortie donner si plusieurs entrées sont allumées ? On prévoit en général soit une priorité, soit une sortie supplémentaire signalant l'erreur.
Le multiplexeur (voir transparent T6) comporte 2n (ici 8) entrées d'information
