Sam & Max » base 2 http://sametmax.com Du code, du cul Sat, 07 Nov 2015 10:56:13 +0000 en-US hourly 1 http://wordpress.org/?v=4.1 La fin du mystère du binaire (nananère) 52 http://sametmax.com/la-fin-du-mystere-du-binaire-nananere/ http://sametmax.com/la-fin-du-mystere-du-binaire-nananere/#comments Tue, 21 Jan 2014 15:01:56 +0000 http://sametmax.com/?p=8808 Quand mon voisin de table en cours de SVT a commencé à m’expliquer le binaire (il programmait en assembleur sur sa TI89), j’ai pas bien pigé. Des années plus tard, en cours d’archi, un prof nous a fait un cours magistral sur la question. Je n’ai définitivement rien pigé. J’ai regardé des tutos sur le net. RIEN P-I-G-É.

J’ai mis presque 10 ans (littéralement) avant que mon cerveau tilte. Non pas que je n’avais pas compris le principe, mais le détails, comment on faisait la conversion, ce qu’on pouvait faire avec, etc… Ca me passait au dessus de la tête.

Je râle beaucoup sur le manque de pédagogie d’autrui, et après tout, d’autres ont compris le truc à partir de ces explications. Mais je vais me répéter : leurs explications étaient merdiques.

Le binaire c’est simple. Tout le monde peut le comprendre.

Si vous ne pigez pas, c’est que le mec en face de vous est une grosse pine.

Par contre, il y a beaucoup de choses à savoir, alors à long article, loooooooooooongue musique :

Long article car j’ai vu des connards mélanger tout et n’importe quoi dans leurs explications du binaire, et je vais devoir démêler le sac de nœuds qu’ils ont fait dans votre tête.

Pourquoi apprendre le binaire ?

Pour le sport, essentiellement. La culture G. Parce qu’en toute honnêteté, aujourd’hui, ça ne sert plus à grand chose, tellement vous avez de couches d’abstraction entre les manipulations binaires et vous.

Il y a toujours quelques grincheux qui vous diront des trucs de grincheux comme “oui, mais pour comprendre les erreurs de flottant en arithmétique, il faut comprendre le binaire” comme mon père qui me disait qu’il fallait apprendre le latin au lycée. Meh.

D’abord, on a pas plus besoin d’apprendre le binaire pour comprendre les erreurs de flottant qu’on a besoin de comprendre la composition moléculaire de l’essence pour savoir pourquoi une voiture tombe en panne quand il y en a plus. Ensuite, vous n’avez même pas besoin de comprendre pourquoi il y a des erreurs de flottant, juste à savoir comment les éviter (ce que des tas de gens “qui les comprennent” ne sont pas foutu de faire).

Bref, c’est l’éternel bataille de l’arrière garde qui veut défendre le savoir aujourd’hui obsolète – qu’il a accumulé parce qu’a son époque c’était indispensable – à grand renfort de pédanterie. On voit ça dans tous les domaines. Généralement avec force exemples de niches et enculage de mouche.

Mais au delà de ça, le binaire est encore utilisé dans certains domaines, comme la programmation de micro-contrôleurs (si vous planifiez de bosser chez Intel, Nvidia ou la NASA, ça peut servir), la cryptographie ou la programmation de calculatrices en cours de bio. Ce dernier point étant semble-t-il, un sujet intemporel qui ne se démode jamais.

Néanmoins ça reste 0.00001 % de l’informatique actuelle. Vous n’aurez pas besoin du binaire pour vos tâches de Sys Admin, vos GUI, votre app mobile, votre site Web, votre algo de simulation, etc. Bref, les trucs pour lesquels les gens sont payés dans les années 2000.

Maintenant que j’ai bien été désagréable avec une partie du lectorat, précisons tout de même que savoir 2, 3 trucs sur le binaire, ça ne fait pas de mal. Vous êtes informaticiens, ça fait un peu partie du folklore.

Valeur et représentation

En informatique, il y a le problème sans fond de la dualité valeur / représentation. L’écriture des nombres est un exemple parfait de cela.

Par exemple, j’ai ce nombre d’étoiles :

* * * * *

Il y a la valeur du nombre d’étoiles. Cette valeur ne peut pas être manipulée, elle existe, c’est tout. On ne peut que constater le nombre d’étoiles en interprétant ce que l’on voit.

Si on veut manipuler cette valeur (parler d’une valeur, c’est déjà manipuler la valeur), il faut lui donner une représentation.

Les arabes nous ont donné une représentation : 5.

Les romains avaient une autre représentation : V.

La valeur derrière ces deux représentations est strictement la même.

Le binaire est juste une autre représentation. Il n’y a rien de magique derrière le binaire.

Par exemple, la valeur que l’on représentante par 5, se représente ainsi en binaire : 101.

C’est la même valeur de nombre d’étoiles. Juste écrit différemment. Cela n’a aucun impact sur la réalité, ne change rien sur la nature des étoiles ou la valeur manipulée. C’est une manière de transmettre une information.

A la base de la base

La raison pour laquelle on s’embrouille facilement avec le binaire, c’est que la plupart d’entre nous ont appris à lire les nombres par cœur. On lit un nombre comme un tout.

En vérité, un nombre est une notation qui obéit à des règles très strictes, et non seulement chaque chiffre donne une information, mais sa place dans le nombre donne une information. Ce qu’on appelle “centaine”, “millier”, etc, sont des notions qu’on manipule sans y penser, mais derrière, il y a en fait un système.

Le système des bases.

Quand on utilise les chiffres arabes pour écrire un nombre, on utilise une série de symboles, et on les aligne dans un ordre précis. Selon la base utilisée, l’ordre implique une valeur différente.

On ne s’en rend pas compte, mais on utilise tous les jours l’ordre de la base 10. On pense en base 10. On a tellement l’habitude de tout calculer en base 10 qu’on ne se rend pas compte qu’on suit une règle précise pour cela.

Que signifie le fait d’utiliser une base 10 ?

Deux choses.

La première, c’est que l’on a DIX symboles pour représenter DIX valeurs. On ne sait représenter directement que ces DIX valeurs là.

          0
*         1
**        2
***       3
****      4
*****     5
******    6
*******   7
********  8
********* 9

On a des valeurs (un nombre d’étoiles), et on fait correspondre complètement arbitrairement dix symboles pour ces valeurs. On connait ces symboles par cœur, ce sont des conventions. Ils ne signifient rien par eux-même, nous leur avons donné cette signification.

Ça c’est la première règle. La deuxième règle, c’est que quand on tombe à cours de symboles parceque la valeur est trop grande, on utilise la position des symboles pour dire combien de groupes de dizaines de symboles il y a.

Par exemple avec ce nombre :

10

10 veut dire (en lisant de droite à gauche, ce sont des chiffres arabes, je le rappelle), 0 unité, et 1 groupe d’une dizaine.

Si on a 587, on dit (toujours de droite à gauche) : il y a 7 unités et 8 groupes d’une dizaine et 5 groupes d’une dizaine de dizaines.

La position du chiffre dit si l’on parle d’un groupe de 1, de 10, de 10 groupes de 10 (cent), de 10 groupes de 10 groupes de 10 (1000), etc.

C’est pour ça qu’on parle de base 10. Tout est en groupe de 10. On fait des paquets de 10. Puis des paquets de 10 paquets de 10. Puis des paquets de 10 paquets de 10 paquets de 10…

Exemple avec le nombre 1982 :

[1][9][8][2]
 |  |  |  |
 |  |  |  2 unités
 |  |  8 groupes de 10
 |  9 groupes de 10 groupes de 10 (10 x 10 = 100)
1 groupe de 10 groupes de 10 groupes de 10 (10 x 10 x 10 = 1000)

Si on lit un chiffre comme un tableau en informatique (donc en commençant par 0), mais de droite à gauche, on peut utiliser les puissances pour noter ça de manière propre :

[1][9][8][2]
 |  |  |  |
 |  |  |  2 est à la place 0, sa "valeur" est 2 x 10^0 = 2 * 1 = 2
 |  |  8 est à la place 1, sa "valeur" est 8 x 10^1 = 8 * 10 = 80
 |  9 est à la place 2, sa "valeur" est 9 x 10^2 = 9 x 10 x 10 = 9 x 100 = 900
1 est à la place 3, sa "valeur" est 1 x 10^3 = 1 x 10 x 10 x 10 = 1 x 1000 = 1000

Ça vous parait évident sans avoir à faire le calcul ? C’est parce que vous êtes tellement habitué à compter en base 10 que c’est automatique pour vous. Pourtant, en base 2, c’est exactement la même chose.

On a DEUX symboles pour représenter DEUX valeurs. On ne sait représenter que ces DEUX valeurs là.

  0
* 1

Quand on tombe à cours de symbole parce qu’une valeur est trop grande, on utilise la position des symboles pour dire combien de groupes de deux symboles il y a.

Par exemple avec ce nombre :

10

10, qui ne se prononce PAS dix, veut dire (en lisant de droite à gauche), 0 unité, et 1 groupe d’une paire. Donc deux en base 10 :-).

Pour les chiffres plus longs, c’est kiff, kiff :

[1][1][1][0]
 |  |  |  |
 |  |  |  0 unité
 |  |  1 groupes de 2
 |  1 groupes de 2 groupes de 2 (2 x 2 = 4 en base 10)
1 groupe de 2 groupes de 2 groupes de 2 (2 x 2 x 2 = 8 en base 10)

Donc en base 10 : 8 + 4 + 2, soit 14.

Si on le représente en puissance de 2 :

[1][1][1][0]
 |  |  |  |
 |  |  |  0 est à la place 0, sa "valeur" est 0 x 2^0 = 0 * 1 = 0
 |  |  1 est à la place 1, sa "valeur" est 1 x 2^1 = 1 * 2 = 2
 |  1 est à la place 2, sa "valeur" est 1 x 2^2 = 1 x 2 x 2 = 1 x 4 = 4
1 est à la place 3, sa "valeur" est 1 x 2^3 = 1 x 2 x 2 x 2 = 1 x 8 = 8

En gros pour convertir du binaire en base 10, il suffit de réciter les puissances de deux dans sa tête :

2, 4, 8, 16, 32… (2 fois 2 = 4, 2 fois 4 = 8, 2 fois 8 = 16, 2 fois 16 = 32…)

Et les appliquer de droite à gauche :

[1][0][1][1][1][0] => [1 * 32] + [0 * 16] + [1 * 8] + [1 * 4] + [1 * 2] + [O * 1] => 46 en base 10

Une illustration graphique ?

Voici quarante-six étoiles :

**********************************************

Si je les représente en base 10, je noterais ça 46, soit 4 groupes de dizaines, et 6 unités :

    4          6

**********   ******
**********
**********
**********

Si je le représente en base 2, je le note 101110: soit 1 groupe de trente-deux, 0 groupe de seize, 1 groupe de huit, 1 groupe de quatre, 1 groupe de deux, et 0 unité.

                1                  0      1        1     1    0

********************************   -   ********   ****   **   -

On peut faire ça avec n’importe quelle base. On peut compter en base 3 (ternaire) ou en base 4, 5, 6… On utilise notamment parfois en informatique la base 8 (octale) et la base 16 (hexadécimale). Pour cette base, il y a 16 symboles : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, représentant chacun une valeur, puis, quand on a plus de symbole, on utilise la position pour signaler un paquet de 16.

Passons au code

En Python on peut écrire un nombre en binaire en le préfixant de ‘0b':

>>> 0b101110
46

Mais par défaut Python représente toujours à l’affichage ce nombre en base 10. La valeur derrière est la même de toute façon (qui, de manière amusante, est sockée en binaire).

Si vous voulez forcer l’affichage du nombre en binaire, vous pouvez utilisez bin() ou format() :

>>> 'Le nombre {0} en binaire donne : {0:b}'.format(46)
u'Le nombre 46 en binaire donne : 101110'
 
>>> bin(46)
'0b101110'

A l’inverse, si vous avez une représentation textuelle d’un chiffre binaire, vous pouvez préciser la base via le second paramètre de int() :

>>> int('101110') # la base 10 est le réglage par défaut...
101110
>>> int('101110', 10) # ...donc on récupère cent un mille cent dix.
101110
>>> int('101110', 2) # si on précise la base 2, on récupère quarante-six.
46

Mais si on n’a pas codé sa petite fonction pour faire pareil à la main à 50 ans, on a raté sa vie. Donc, voici un exemple simple d’une fonction qui convertit une représentation textuelle d’un chiffre binaire en int Python :

def bin2dec(s):
 
    # on rejette les chaînes vides
    if not s:
        raise ValueError('The string cannot be empty')
 
    total = 0
 
    # on itère sur la chaîne, de droite à gauche
    reversed_number = s[::-1]
    for pos, num in enumerate(reversed_number):
 
        # on multiplie le chiffre en cours par la puissance de 2
        # qui correspond à sa position
        total += int(num) * (2 ** pos)
 
    return total
 
print(bin2dec('0'))
print(bin2dec('1'))
print(bin2dec('10'))
print(bin2dec('101'))
print(bin2dec('10011100'))
 
## 0
## 1
## 2
## 5
## 156

Et la fonction inverse :

 
from __future__ import division # pour être tous d'accord sur la division entière
 
def dec2bin(i):
 
    numbers = []
 
    if i == 0:
        return i
 
    # On divise (avec la division entière) par deux jusqu'à ce qu'il ne reste
    # plus rien à diviser (on fait des paquets de 2, quoi).
    # Avant chaque division par deux, on regarde si il y aura un reste
    # pour la prochaine division. Si oui, on met 1 pour le paquet de 2 actuel,
    # sinon on met 0.
    # C'est comme pour la multiplication à la main ("je met 2 et je retiens 1"),
    # mais à l'envers.
    while i != 0:
        numbers.append(str(i % 2))
        i = i // 2
 
    # Ensuite on inverse tout ça et on join() tout en une belle string
    return (''.join(numbers[::-1]))
 
print(dec2bin(0))
print(dec2bin(1))
print(dec2bin(2))
print(dec2bin(5))
print(dec2bin(156))
 
## 0
## 1
## 10
## 101
## 10011100

Et les opérateurs bitwise ?

Dans les tutos on voit souvent mélanger la notion de binaire, avec la représentation des nombres, du texte, et les opérateurs spécialisés dans la manipulation du binaire :

|, ^, ~, >>, <<, >>>, &, etc

C’est le bordel.

On les appelle ces opérateurs “bitwise”, et ils sont essentiellement de deux types : les shifts, et les opérateurs logiques.

Les shifts, souvent notés >>, <<, etc, décalent d’un bit. Un bit, c’est une case dans un nombre binaire, une d’un chiffre position, qui prend donc la valeur 0 ou 1.

Ex: 1010 est un nombre de 4 bits. 10100 est un nombre de 5 bits.

Par décaler, j’entends qu’ils poussent littéralement les bits dans un sens ou dans l’autre :

1010 >> 1 va donner 101 (les bits se sont décalés vers la droite d’un cran, c’est le rshift). Ca fait disparaitre un bit à droite.
1010 << 1 va donner 10100 (les bits se sont décalés vers la gauche d’un cran, c’est le lshift). Ca rajoute un bit à droite.

Si on met un plus grand nombre, on décale de plusieurs bits :

1010 << 3 va donner 1010000 (les bits se sont décalés vers la gauche de 3 crans)

C’est une opération très rapide, puisqu’il suffit de décaler les chiffres, sans faire de calculs complexes. Pourtant, c’est l’équivalent de certaines opérations mathématiques.

Par exemple, un lshift peut être équivalent à une multiplication par une puissance de 2.

Ainsi, si je prends le chiffre 10 en (binaire 1010), et que je lui applique un lshift de 3, c’est comme si je le multipliais par 2^3 (soit 8). Démo en Python :

>>> 0b1010
10
>>> 0b1010 << 3
80

Mais l’opération prend beaucoup moins de cycles CPU qu’une multiplication. C’est une astuce d’optimisation qui a été beaucoup utilisée au paléolithique et qui reste en vigueur chez les cryptonerds. Néanmoins ne l’utilisez pas en Python, les gains sont minimes. C’est surtout utile pour les codes C ou assembleur qui sont déjà sur optimisés et ont besoin de ce petit coup de pouce supplémentaire.

Ensuite il y a les opérateurs logiques. Ils appliquent tout simplement la logique booléenne à chaque bit d’un nombre avec chaque bit d’un autre nombre dont la position correspond. Par exemple :

Si je fais “1101 ET (représenté souvent par ‘&’) 110″, je vais obtenir :

[1][1][0][1]
 |  |  |  |
 &  &  &  &
 |  |  |  |
[ ][1][1][0]
 |  |  |  |
 v  v  v  v
 0  1  0  0

1 et rien => vrai ET faux ? => faux => 0
1 et 1 => vrai ET vrai ? => vrai => 1
0 et 1 => faux ET vrai ? => faux => 0
1 et 0 => faux ET vrai ? => faux => 0

C’est de la logique booléenne de base, vous pouvez la tester avec True, False, and et or dans votre shell si ça ne vous parle pas.

En code Python :

>>> bin(0b1101 & 0b100)
'0b100'

On l’utilise parfois pour faire ce qu’on appelle des “masques”, c’est à dire représenter une série d’états sous forme de grille de bits, et changer un état de cette grille en appliquant une opération logique avec une autre grille.

Je sais, ça fait flou comme ça. Un exemple peut-être ?

Les permissions d’un fichiers Unix sont Read (lire), Write (écrire) et Execute (exécuter). Soit “rwx”. Elles s’appliquent à User (utilisateur), Group (groupe), Other (autre), soit “ugo”.

Cela est peut être représenté par 3 groupes de 3 bits, soit 9 bits :

    U         G         O
[r][w][x] [r][w][x] [r][w][x]

1 veut dire que la permission est donnée, 0 veut dire qu’elle n’est pas donnée.

Ainsi :

[1][1][1] [1][0][1] [1][0][1]

Veut dire que l’utilisateur à le droit de lire, écrire et exécuter le fichier. Le groupe et les autres n’ont que le droit de le lire et exécuter le fichier.

Si vous mettez ça en base 10, ça donne 7/5/5 (et NON sept-cent-cinquante-cinq car il y a 3 valeurs). Cela explique le fameux chmod 755 que vous voyez dans tous les tutos bash.

Si vous faites :

chmod g+w fichier

Le programme va rajouter la permission d’écrire au groupe. On peut représenter cette opération par l’application d’une opération “OU” (représentée par ‘|’) :

En effet on a 101 pour les permissions du groupe et on veut obtenir 111. Il suffit d’appliquer le masque 010 (qui correspond pile poil à un 1 à la case de la permission voulue) :

>>> bin(0b101 | 0b010)
'0b111'

Représentation des nombres dans un ordinateur

Cette partie c’est vraiment pour vos beaux yeux hein, ne vous en faites pas si vous ne pigez pas tout. Je ne vais pas dans le détail car ça demanderait un autre article complet, plus un comparatif des archis, des notions, des systèmes de typages des langages, etc. Et j’ai vraiment pas envie de le faire.

Bon, déjà, la représentation des nombres dans un ordi, c’est une grande source de confusion : en effet, l’ordinateur ne stocke pas la représentation binaire directe d’un nombre.

On pourrait se dire : l’ordinateur manipule du binaire, on traduit nos nombres en binaire, on fout tout tel quel dedans, et yala.

Mais un ordinateur a des limitations techniques. Notamment, il possède des plages de mémoires d’un nombre de bits limité. Il faut donc faire tenir la représentation de la valeur sur cet espace limité.

Si votre espace de mémoire pour représenter une valeur est limité à 16 bits et que vous devez stocker un nombre entier dedans, il pourra être au maximum 2^16 – 1 = 65535.

C’est pour cela qu’en C on déclare le type d’une variable qui va contenir un nombre qu’on va manipuler. On dit clairement, “alloue moi cet espace mémoire, mon nombre ne sera jamais plus grand que ça”. En Python, c’est automatiquement et transparent.

(C’est aussi pour ça qu’on parle de processeur 16bits, 32bits, 64bits, etc. C’est la taille des jeux d’instructions qu’ils sont capables de traiter en un cycle.)

Mais il se rajoute une autre complexité : un entier peut avoir un signe plus ou un signe moins. Il faut bien le représenter quelque part. On peut le faire en utilisant le premier bit, mais aussi avec un format appelé “le complément à deux”. Comme cet article est déjà super long, je vais pas me lancer dans l’explication. J’ai mal aux doigts. Sachez juste qu’on utilise en quelque sorte “l’inverse” du nombre.

Encore une fois, en C, on déclare que l’on va utiliser un “signed int” ou un “unsigned int” à l’initialisation d’une variable.

Enfin, il y a les nombres à virgule, aussi appelés “flottants” (d’où le type “float” en Python).

On pourrait se dire qu’on utilise les puissances de deux négatives :

0.92 se lit en base 10 “0 x 1 + 9 x 10^-1 + 2 x 10^-2″

On garderait la logique des positions.

Donc :

0.11 se lit en base 2 “0 x 1 + 1 x 2^-1 + 1 x 2^-1 + 1 x 2^-2″

A priori on pourrait stocker le nombre en utilisant ce principe. Mais ça ne permet pas de présenter les nombres très grands (tendant vers l’infini) ou très petit (tendant vers zéro). Alors on utilise un autre principe : on représente un nombre avec la formule m x 2^n, très couramment sur 64 bits (ce que fait le type float Python, mais on peut avoir plus de choix de manoeuvre en utilisant numpy).

m est un nombre à virgule compris entre 1 et 2 (ce dernier étant exclus). On appelle ça la mantisse. Ce sera stocké sur 52 bits en utilisant une représentation binaire littérale.

n est l’exposant, c’est un nombre entier compris entre -1022 et 1023, stocké sur 11 bits.

On garde le premier bit pour le signe.

Et il y a des exceptions pour 0, l’infini et NaN.

(et je n’ai pas la moindre putain d’idée de comment sont représentés les complexes)

Si vous êtes en manque d’aspirine, tout ça est codifié dans la norme IEEE 754, que Python respecte scrupuleusement.

Mais ça vous fait une belle jambe pas vrai ?

Tout ça pour dire que même avec une belle précision, le nombre de chiffres stockés après la virgule est limité. Du coup, on a une valeur approximative stockée dans l’ordi, ce qui fait que les calculs se font sur des approximations :

>>> "{0:.35f}".format(0.9999999999999999999999999999999999999999999999999999999 + 0.000000000000000000001)
u'1.00000000000000000000000000000000000'

En Python on peut gagner en précision en utilisant le module decimal:

>>> from decimal import Decimal
>>> Decimal("0.9999999999999999999999999999999999999999999999999999999") + Decimal("0.000000000000000000001")
Decimal('1.000000000000000000001000000')

C’est plus lent, mais plus intuitif. Quand on manipule des sous, du temps, des unités de poids, de température, de longueur, etc, c’est utile.

Représentation du texte

Pour le texte, c’est encore autre chose. Et là je vous renvoie à l’article sur les encodings.

En résumé, le stockage du texte n’a rien à avoir avec l’arithmétique binaire, c’est juste qu’on fait correspondre un nombre (on montre souvent sa représentation binaire pour l’ASCII et sa représentation hexa pour l’unicode, mais ça reste un nombre, point) à un caractère. Il y a un grand tableau en mémoire qui fait cette correspondance de manière totalement arbitraire.

C’est une norme arbitraire de correspondance, c’est tout.

Donc quand on vous dit “ecrivez les mots ‘glory hole’ en binaire”, ça ne veut rien dire.

Une bonne consigne serait de dire : “donnez moi la suite de nombres, représentés sous forme binaire, qui corresponde aux caractères qui compose les mots ‘glory hole’ selon l’encoding ASCII”.

On peut obtenir la valeur numérique ASCII en utilisant ord() en Python :

>>> for x in 'glory hole':
    print(ord(x))
...
103
108
111
114
121
32
104
111
108
101

Après, c’est juste du formatage pour afficher le binaire :

>>> for x in 'glory hole':
...     print("{:b}".format(ord(x)))
...
1100111
1101100
1101111
1110010
1111001
100000
1101000
1101111
1101100
1100101
]]>
http://sametmax.com/la-fin-du-mystere-du-binaire-nananere/feed/ 52