Vous aimez ce que vous lisez sur ce blog ?
Envie d'aller plus loin avec véritable formation d'expertise en Java ?
Venez suivre ma formation Masterclasse Expertise Java !

"Même un développeur experimenté a besoin de continuer à apprendre. Et dans cette formation... j'ai appris beaucoup !" - A.G., Java Champion

Sessions intra-entreprises sur demande : contact[at]mokatech.net.
Inscrivez-vous vite !

Introduction au binaire, avec des vrais bouts de Java

Vous savez ce qu'on dit : "Il existe 10 types de personnes - ceux qui comprennent le binaire, et..."

Dans cet article, je rappellerai quelques principes basiques sur la représentation des nombres en binaire, les opérations associées, ainsi que les techniques de manipulation bas niveau des bits. Rien de méchant, mais il existe certaines API en Java dont l'usage nécessite une certaine connaissance de ces mécanismes, alors autant être préparé.

Représentation des nombres en binaire

Principe général

Chaque nombre entier peut être représenté sous forme binaire, c'est-à-dire avec plein de 0 et de 1, exactement comme quand Neo hacke la Matrice... Mais en moins verdâtre.

Alors, comment ça marche ? En fait, c'est très simple, dès lors qu'on sait que le binaire se lit et s'écrit de droite à gauche.
Dans la notation binaire, chaque bit (0 ou 1) représente une certaine puissance de 2, qui dépend de sa position. S'il vaut 1, on ajoute cette puissance de 2 à la valeur totale ; s'il est à 0, il ne se passe rien.
Le premier bit en partant de la droite ("bit de poids faible") représente 2^0 (=1), le second 2^1 (=2), le troisième 2^2 (=4), etc.

Par exemple, le décimal 42 est équivalent au binaire 101010b. En partant de la droite, on calcule
0 + 2^1 + 0 + 2^3 + 0 + 2^5 = 0 + 2 + 0 + 8 + 0 + 32 = 42.
Facile.

Le problème en revanche, c'est que si l'on accole plusieurs nombres dans un flux binaire, il est difficile de savoir où finit un nombre et où commence le suivant. Pour remédier à cela, le plus simple est que le producteur et le consommateur du flux se mettent d'accord pour encoder chaque nombre sur une taille fixe : 8, 16, 32, 64 bits...

Notre nombre 42 est ainsi représenté par 00101010b sur 8 bits, et 0000000000101010b sur 16 bits.

Bornes et nombres négatifs

En appliquant le système présenté ci-dessus, on s'aperçoit que 8 bits permettent de représenter des nombres entre 0 (0000000b) et 255 (11111111b = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 = 255). Avec 16 bits, on peut monter à 65535, et jusqu'à 4294967295 avec 32 bits.

Mais alors, comment coder les nombres négatifs ?
Jusqu'ici, on considérait que tous les bits disponibles servaient à encoder la valeur numérique. Mais pour représenter l'information supplémentaire du signe, il a été nécessaire d'en sacrifier, et c'est le bit de poids fort (le plus à gauche) qui a été désigné volontaire : à 0 il désigne un nombre positif, et à 1 un nombre négatif.
Sur 8 bits, on pourra alors toujours représenter 256 valeurs, mais désormais, la moitié d'entre elles seront négatives, ce qui correspond à une fourchette de -128 à +127 (zéro empiétant sur les valeurs positives).

Comme je vous sens impatients de mettre tout ça en oeuvre, tentons de représenter, sur 8 bits, le nombre -42 en mettant le bit de poids fort à 1 :

00101010b = +42d
10101010b = -42d ?

Oups, nous n'obtenons pas -42 mais +170. Un bug dans la matrice ?

En réalité, ce système simpliste ne fonctionne pas bien, ne serait-ce que parce que le nombre 0 aurait deux représentations (00000000b et 10000000b). On a donc dû inventer un autre mécanisme, un peu plus rusé, pour calculer l'opposé[1] d'un nombre : le "complément à 2". OK, ça fait peur dit comme ça, mais en pratique, ça consiste juste à inverser tous les bits ("complément à 1") du nombre initial, puis à ajouter 1 (00000001b) au résultat. Et là, tout fonctionne bien.

Deuxième essai ;

00101010b : 42d
11010101b : Comp2(42d)
11010110b : Comp2(42d) + 1 = -42d

Ce n'est quand même pas très intuitif, alors vérifions : 00101010b + 11010110b = 00000000b.
Bon, ça a l'air de marcher.

Manipulation des nombres binaires

Les opérateurs

Il existe différents opérateurs, unaires ou binaires, applicables aux représentations binaires. Les plus utiles sont :

  • AND : opérateur binaire qui renvoie 1 si les deux bits opérandes sont à 1, et 0 dans le cas contraire.
  • OR : opérateur binaire également, qui renvoie 1 si au moins l'un des bits opérandes est à 1. Dans le cas contraire, renvoie 0.
  • NOT : opérateur unaire ayant l'esprit de contradiction. Il remplace les 1 par des 0, et réciproquement.

Par exemple :

    00111100         00111100        
AND 01100110      OR 01100110      NOT 00111100
------------      -----------      ------------
  = 00100100       = 01111110        = 11000011

Java dispose d'opérateurs natifs pour réaliser ces opérations :

  • AND est représenté par l'opérateur & (esperluette[2]),
  • OR par | (pipe),
  • NOT par ~ (tilde).

On peut ainsi écrire :

int i = 42 & 26;

Question : à votre avis, combien vaut i après cette opération ? Et que vaut 42+27 ? Pourquoi ?

Notez que le résultat d'une opération binaire est toujours un int, il vous faudra donc "caster" le résultat si vous souhaitez opérer sur des variables de type byte, short ou char.

Manipulation individuelle des bits

Ce qui saute aux yeux quand on regarde un nombre binaire, c'est tous ces petits 0 et 1 alignés, bien rangés les uns à côté des autres de manière compacte, comme autant de petits flags qui seraient activés (1) ou non (0)...

Et si, justement, on se servait de chaque bit comme d'un booléen ? Cela permettrait, dans un simple octet (byte), de stocker 8 booléens distincts ! Compression x8, mieux que les Parisiens dans le métro !

En fait, de nombreuses API utilisent déjà cette astuce pour minimiser la consommation mémoire et transporter facilement, en un seul bloc, de multiples flags ayant un lien logique.

Par exemple, la classe java.lang.reflect.Modifier déclare les différents modificateurs applicables aux champs et méthodes de la façon suivante (en réalité, les valeurs sont en hexadécimal dans le code source, car Java 6 ne permet pas d'écrire directement des notations binaires, mais je vous les ai traduits en binaire ci-dessous - on ne recule devant aucun effort sur ce blog) :

public static final int PUBLIC     = 00000001;
public static final int PRIVATE    = 00000010;  
public static final int PROTECTED  = 00000100;  
public static final int STATIC     = 00001000;   
(...)

Ainsi, l'entier représentant une méthode publique et statique aura ses bits 1 et 4 actifs ; sa représentation binaire se terminera donc par 1001.

Pour pouvoir manipuler de telles structures et activer, désactiver ou tester un flag particulier, il faut être capable de manipuler les bits individuellement. Les opérations AND, OR et NOT vues plus haut vont justement nous y aider.

Activer un bit

Pour activer un bit particulier, il nous faut trouver une opération qui positionnerait systématiquement à 1 le bit cible, quel que soit son état précédent, et qui serait neutre pour tous les autres.
L'opération OR possède justement ces propriétés : elle renvoie automatiquement 1 si on applique un masque à 1, et conserve la valeur courante si on lui applique un masque à 0.

//Etat initial des flags
int modifiers = 42; 
 
// Maintenant le bit correspondant au flag PROTECTED est actif
modifiers = modifiers | Modifier.PROTECTED; 
 
// Opérateur composite. Oui, c'est moche.
modifiers |= Modifier.PROTECTED;

C'est encore plus parlant en binaire :

   00101010
OR 00000100
-----------
 = 00101110   
Désactiver un bit

Pour désactiver un bit particulier, il faut trouver une opération aux propriétés inverses de celles du OR. En particulier, il faut qu'elle puisse renvoyer systématiquement 0 pour le bit cible, et ne pas toucher aux autres.
L'opération AND permet cela : un AND 0 renvoie toujours 0, et un AND 1 renvoie la valeur préexistante.

Il faut donc constituer un masque où tous les bits sont à 1, sauf le bit cible qui est à 0. Le problème, c'est que nos flags représentent exactement l'inverse :

int PRIVATE  = 00000010; // Flag
               11111101  // Masque souhaité

Il nous faudra donc penser à inverser le masque du flag à l'aide de l'opérateur NOT (~) avant de l'appliquer.

//Etat initial des flags
int modifiers = 42; 
 
// Maintenant le bit correspondant au flag PRIVATE est inactif
modifiers = modifiers & ~Modifier.PRIVATE;

Revoyons la scène au ralenti en binaire :

    00101010
AND 11111101
------------
  = 00101000

Nous savons donc activer ou désactiver un bit à la demande.

Tester un bit

Pour finir, voyons comment tester si un flag particulier est actif.

La méthode habituelle consiste à effectuer une opération AND avec un masque dont seul le bit ciblé est activé. Cela a pour effet d'effacer (mettre à 0) tous les bits, sauf celui qui nous intéresse, qui conserve sa valeur. Le résultat est ensuite simple à analyser : si le flag était inactif, tous les bits sont à 0, ce qui représente le nombre décimal zéro ; dans le cas contraire, le nombre obtenu est différent de zéro.

Testons donc les modificateurs appliqués à notre classe :

    00101010 // Modificateurs à tester
AND 00000010 // Masque pour PRIVATE
------------
  = 00000010 // Le flag "PRIVATE" était actif
  
  
    00101010 // Modificateurs à tester
AND 00000100 // Masque pour PROTECTED
------------
  = 00000000 // Le flag "PROTECTED" était inactif

En Java :

//Etat initial des flags
int modifiers = 42; 
 
// Maintenant le bit correspondant au flag PROTECTED est actif
boolean isProtected = (modifier & Modifiers.PROTECTED) != 0

Conclusion

Il est important de connaître un minimum la façon dont sont codés les nombres dans les systèmes informatiques en général, et dans votre langage de programmation favori en particulier. Cela explique beaucoup de choses, comme la taille maximale autorisée pour les nombres, les problèmes d'overflow, les erreur d'arrondi...

De plus, certaines API requièrent une bonne maîtrise de la manipulation low-level des bits. La page listant les constantes du JDK en donne une bonne indication.

Notes

[1] Vous vous rappelez vos cours de maths au collège ? L'opposé de x, c'est -x : on change de signe. L'inverse de x, c'est 1/x.

[2] Le très sérieux Robert pense que son nom pourrait venir du latin perna, « jambe, cuisse, jambonneau ». Ce jour-là, Robert avait dû fumer.


Commentaires

1. Le mercredi 7 décembre 2011, 05:35 par Kyoku57

Le métier d'informaticien peut être vulgairement assimilé au statut péjoratif de "manipulateur de bits".

Par contre, moi qui découvre Java au fur et à mesure, un truc vient de me décevoir et que j'ignorais : "Java 6 ne permet pas d'écrire directement des notations binaires". J'ai envie de demander "bah pourquoi ??". Après tout, il y a bien les opérateurs pour faire des décalages de bits à gauche et à droite, et c'est pas un type de déclaration en plus qui aurait mis la zone :/ ... étrange.

NOTE : pour rappel décaler des bits vers la droite permet de diviser par deux rapidement et par la gauche, de multiplier par deux.

2. Le mercredi 7 décembre 2011, 09:11 par Brice

"Vous vous rappelez vos cours de maths au collège ? L'opposé de x, c'est -x : on change de signe. L'inverse de x, c'est 1/x."

Hallelujah !

Ca me rapelle mes premiers cours de logique binaire. Pour Java tu devrais parler des opérateurs de shift <<, >> et >>> aussi avec certaines de leurs astuces.

3. Le mercredi 7 décembre 2011, 10:15 par Olivier Croisier

@Kyoku57
La notation binaire est autorisée depuis Java7 :
http://docs.oracle.com/javase/7/doc...

@Brice et @Kyoku57
J'ai volontairement laissé de côté les opérateurs de décalage, ainsi que la classe java.util.BitSet. Ce n'était pas tout à fait l'objet du billet, mais leur mention dans les commentaires est un bon complément :)

4. Le mercredi 7 décembre 2011, 13:06 par HollyDays

«Cela explique beaucoup de choses, comme la taille maximale autorisée pour les nombres, les problèmes d'overflow, les erreur d'arrondi...»

Cela explique aussi le problème soulevé par le quiz Java n°2 de ce blog ! (http://thecodersbreakfast.net/index... )

--
«Alors, comment ça marche ? En fait, c'est très simple, dès lors qu'on sait que le binaire se lit et s'écrit de droite à gauche. »

Ben... pile poil comme nos bons vieux nombres décimaux, en fait. La seule différence, c'est que les nombres binaires, ou nombres en base 2, s'écrivent avec 2 signes possibles seulement (deux chiffres, si vous préférez), alors que les nombres décimaux, ou nombres en base 10, s'écrivent avec 10 signes possibles (les 10 chiffres).

De la même manière qu'en binaire, 1011b = 1 * 2^3 + 0 * 2^ 2 + 1 * 2^1 + 1 * 2^0 , en décimal 425d = 4 * 10^2 + 2 * 10^1 + 5 * 10^0.

--
@Kyoku57

Pourquoi Java (avant Java7) ne supporte pas l'écriture des nombres en binaire ? La réponse est simple : parce que Java hérite sa syntaxe du langage C, et que C ne permet pas d'écrire les nombres en binaire.

Ce qui mène à une seconde question : pourquoi C, qui pourtant est un langage de programmation système (avec lequel on développe les systèmes d'exploitation et les drivers, tout de même !), ne permet pas d'écrire les nombres directement en binaire ?

Là encore, la réponse est très simple : parce que C permet d'écrire les nombres en hexadécimal (alias en base 16), ce qui, pour un humain, est infiniment plus lisible que le binaire, et que passer de la base 2 à la base 16 et inversement est d'une facilité déconcertante (chaque chiffre en base 16 correspond toujours à un paquet de 4 chiffres consécutifs en base 2). Et évidemment, Java a hérité de cette facilité.

Conclusion : pouvoir écrire directement les nombres en base 2 est inutile. L'écriture hexadécimale remplit parfaitement cet office, et de manière beaucoup plus lisible.

5. Le mercredi 7 décembre 2011, 13:34 par Olivier Croisier

Oh, un revenant :)
L'hexa est plus lisible dans la plupart des cas, c'est vrai, mais pas quand on bricole des bitmasks...

6. Le jeudi 8 décembre 2011, 09:43 par Kyoku57

@Olivier
Merci pour la précision concernant sa prise en compte dans Java 7.

@HollyDays
Les extensions du langage C gèrent cette représentation (http://gcc.gnu.org/onlinedocs/gcc/B...). Java aurait pu suivre cette évolution et le fait maintenant. Je ne suis pas d'accord sur le terme "inutile" : d'un point de vue pédagogique, la notation binaire est intéressante. Quand je programme sur un µC 8 bits (ou plus) et que je dois jouer avec des registres, je trouve la notation binaire bien plus lisible que la notation hexadécimale.

Exemple avec un registre de sortie d'un µC :
0b01010011 => tu vois tout de suite quelles sont les PINs actives
0x53 => ce n'est pas aussi évident (même si je te l'accorde : c'est facile aussi)

Ajouter un commentaire

Le code HTML est affiché comme du texte et les adresses web sont automatiquement transformées.