[Tutoriel] Les opérateurs binaires

Dernière édition par onilink_ le Mer 28 Nov 2012 - 16:15, édité 11 fois

Les opérateurs binaires

Sommaire

Introduction aux opérateurs binaires
Bases et conversion (facultatif)
Calculs avec les opérateurs binaires
Règles binaires
Opérateurs de décalage << et >>
Opérateur de complément ~
Le système hexadécimal
Utilité de ces opérateurs
Lire/Ecrire en binaire

Ce tutoriel auras pour but d'expliquer le fonctionnement des opérateurs binaires (bitwise), qui sont croyez moi très utiles bien qu'assez obscur au premier abord. La partie 8 est la partie la plus intéressante car elle montre leurs utilité.

1- Introduction aux opérateurs binaires

Il existe en tout 6 opérateurs binaires :

Le et (and) noté &
Le ou inclusif (or) noté |
Le ou exclusif (xor) noté ^
Le décalage a droite >>
Le décalage a gauche <<
L'opérateur de complément ~

Les trois premiers opérateurs se présentent sous deux formes, avec l'une qui permettra de calculer avec des nombres, et l'autre pour calculer des booléens entre eux.
-Le et peut s'écrire : & , && , and
-Le ou inclusif peut s'écrire : | , || , or
-Le ou exclusif peut s'écrire : ^ , ^^ , xor

Un bit peut avoir seulement deux valeurs (étant de base 2), 0 ou 1.
En informatique généralement 1 et 0 correspondent a vrai et faux.

Les opérateurs binaires sont des opérateurs logiques :
Par exemple si on vous dit qu'une information est vraie et qu'une autre information l'est aussi, on pourras considérer que l'information totale est vraie. Or si une des deux informations est erronée, l'information globale seras alors elle aussi erronée.
C'est tout simplement comme ça que fonctionne l'opérateur and.

Si on remplace vrai par 1 et faux par 0, on a alors :
1 and 1 = 1
1 and 0 = 0, de même 0 and 1 = 0
0 and 0 = 0
Voila donc le fonctionnement du and.
J'avais dit précédemment que and, && et & n'avaient pas tous la même utilité.
En fait le && est la syntaxe réduite du and, donc ils s'utilisent de la même manière, mais ne servent eux qu'a comparer seulement deux booléens entre eux.
Le & sert a comparer deux nombres entre eux.

Pour comparer deux nombres il faut tout d'abord les écrire en base 2, s'ils sont en base 10.
Nous fonctionnons (nous les humains) en base décimale, certainement car nous possédons dix doigts, mais les machines elles fonctionnent en base binaire.

2- Bases et conversion (facultatif)

Cette partie est facultative puisque la conversion base 10 <=> base 2 peut se faire avec la calculatrice de Windows bien que rien ne vous empêche d'apprendre ce mécanisme si vous ne savez pas déjà le faire.

Nous possédons donc 10 chiffres permettant d'écrire tous nos nombres :
0, 1, 2, 3, 4, 5, 6, 7, 8, et 9.
Pour la base 2 on a juste 0 et 1.

Exemple de nombres en base 10 puis en base 2 :
666 <=> 1010011010
23 <=> 10111
13 <=> 1101
2012 <=> 11111011100

a) Conversion base 2 vers base 10

Pour convertir un nombre de base 2 en un nombre de base 10 rien de plus simple, il suffit en partant de la droite de multiplier chaque chiffre par 2 puissance sa position.
Exemple, avec ^ signifiant puissance et pas xor, et * signifiant multiplier :
10111 base 2 = 1*2^0 + 1*2^1 + 1*2^2 + 0*2^3 + 1*2^4 = 1 + 2 + 4 + 0 + 16 = 23

b) Conversion base 10 vers base 2

Pour passer de la base 10 à la base 2 c'est un peu plus compliqué.
Une méthode simple consiste a imaginer notre nombre de base 10 sous forme de billes par exemple, puis d'imaginer des boites pouvant contenir un certain nombre de billes. Nos boites seront classées de cette manière, dans un ordre décroissant du nombre de billes qu'elles peuvent contenir.
Si on a 123 à convertir en base 2, il suffit de ce dire que l'on possède 123 billes.
Ensuite il faut chercher une puissance de 2 supérieure a notre nombre de billes.
Ici pour 123 on auras donc 2^7 = 128
Nos boites sont donc disposées de cette manière (les [] signifient boite et le nombre a l'intérieur est le nombre de bille que peut contenir la boite, de plus on commence à 2^(7-1) soit 2^6 ) :
[2^6] [2^5] [2^4 ] [2^3] [2^2] [2^1] [2^0] soit
[64] [32] [16] [8] [4] [2] [1]
Maintenant nous allons remplir nos boites de billes avec une règle simple, il faut remplir entièrement une boite de bille (1) ou la laisser vide et passer a la suivante si on n'a pas assez de billes (0).
Ce qui nous donne :
[64] : 1, on peut la remplir entièrement, il nous reste donc 123-64 billes, soit 59.
[32] : 1, il nous reste 59-32 = 27 billes.
[16] : 1, il nous reste 11 billes.
[8] : 1, il nous reste 3 billes.
[4] : 0, on ne peut pas remplir entièrement notre boite, on passe à la suivante.
[2] : 1, il nous reste une bille.
[1] : 1, on a remplis toutes les boites.

123 s'écrit donc en base 2 : 1111011.

Astuce : pour trouver la puissance de la dernière boite on peut faire un log de base 2 de notre nombre de base 10 et tronquer. Ici on aurait log2(123) = 6,94 et des poussières, donc 6 si on tronque, or 2^6 = 64, ce qui est bien la contenance de notre première boite.
Si vous ne possédez pas le log2 il suffit de faire log(x)/log(2) et le résultat est le même.

3- Calculs avec les opérateurs binaires

Nous avons donc vu le and, et le &&, qui ne permettent que de faire des calculs entre deux bits.
Le & sert comme les autres opérateurs mathématiques a faire des calculs entre deux nombres.
Pour calculer nombre1 & nombre2 il faut convertir nombre1 et nombres1 en base 2. Ensuite on a plus qu'a comparer chaque bits des deux nombres entres eux.

Exemple :
549 & 320 = 10 0010 0101 & 01 0100 0000 (base 2)
Ensuite il suffit de calculer les bits des deux nombres entre eux selon les règles de and :

1 & 0 = 0
0 & 1 = 0
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
0 & 0 = 0
0 & 0 = 0
1 & 0 = 0
0 & 0 = 0
1 & 0 = 0

donc 549 & 320 = 0 , et l'on vois donc que 549 et 320 n'ont pas un seul bit en commun;

Les opérateurs or et xor fonctionnent selon le même principe.
|| et or servent à calculer deux bits entre eux et | deux nombres.
^^ et xor de même deux bits et ^ deux nombres.

4- Règles binaires

Voici donc les règles pour les opérateurs &, | et ^

&	0	1
0	0	0
1	0	1

\|	0	1
0	0	1
1	1	1

^	0	1
0	0	1
1	1	0

5- Opérateurs de décalage

Les opérateurs << et >> sont des opérateurs de décalage des bits
<< décale les bits à gauche, donc pour un nombre xxxx de base 2, alors xxxx<<3 = xxxx000
>> fonctionne de la même manière mais décale les bits a droite.
<< 1 reviens donc à multiplier par 2, et << 2 par 4, soit << x a multiplier par 2 puissance x.

Exemples :
125 << 2 = 1111101 << 2 = 111110100 = 500
92 >> 3 = 1011 100>> 3 = 1011 = 11

6- Opérateur de complément ~

L'opérateur ~ sert a inverser les bits d'un nombre. Il faut faire attention car selon le type de variables les valeurs ne sont pas les mêmes.
Pour un unsigned char (un entier tenant sur octet non signé), ~12 = 243 car
12 = 00001100 base 2 donc ~12 = 11110011 base 2 = 243
Sous Game Maker ~x seras égal à -x-1.

7- Le système hexadécimal

Le système hexadécimal est un système très intéressant car il est très simple de faire passer un nombre de base 2 à base 16 (de hexa).
Le système hexadécimal étant un système de base 16 il utilise donc les premières lettres de l'alphabet en complément des chiffres traditionnels :
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.

Pour convertir un nombre de base 2 codé sur un octet il suffit de le couper en deux paquets, puis calculer a quoi correspondent chaque paquet puis remplacer par les symboles correspondants.
Par exemple :
10011101 = 9D base 16 car
1001 = 9 base 10 donc 9 base 16 et
1101 = 13 base 10 soit D en hexa

Sous GM il est possible de noter un nombre en hexadécimal. Pour cela il suffit de mettre $ devant. Exemple : $FF0000 , qui est égal a c_blue

8- Utilité de ces opérateurs

Ces opérateur sont d'une utilité incroyable lorsque l'on programme et surtout lorsque l'on commence à ce rapprocher de la machine. Je vais montrer de nombreux exemples à travers lesquels vous verrais toute la puissance des opérateur bitwise.

Exemple 1 : Les couleurs
Les couleurs sont la plupart du temps codés sur 24bits, avec un octet pour le rouge, un autre pour le vert et le dernier pour le bleu, soit 8bits pour chaque couleurs, c'est le format RGB (pour Red Green Blue).
Une couleur est donc composée de rouge, de vert et de bleu avec chacune de ces couleurs primaires allant de 0 à 255.
En hexadécimal on a donc toutes les valeurs possibles du noir 000000 au blanc FFFFFF soit 16777216 couleurs possibles !
Sous GM le rouge est codé sur le premier octet a droite, le vert sur l'octet du milieu et le bleu l'octet a gauche.
Couleur : [Bleu][Vert][Rouge]

Donc pour créer une couleur avec du rouge, du vert et du bleu il faut remplir le premier octet a droite avec le rouge, le second avec le vert et le dernier avec le bleu.
Soit : couleur = (bleu<< 2 octets) + (vert << 1 octet) + (rouge << 0 octet)
ce qui donne : couleur = bleu<<16 | vert<<8 | rouge
Faire << 8 revient a multiplier par 256 mais les opérateurs binaire sont plus rapides donc il vaut mieux les utiliser, de plus c'est plus propre et plus compréhensible.

Code:: //make_color_rgb(red, green, blue)
return argument2<<16|argument1<<8|argument0

Maintenant si l'on veut récupérer la tonalité de bleu d'une couleur il va falloir tout simplement récupérer le premier octet de celle-ci.
Par exemple pour la couleur 94F388 la tonalité de bleu est 94.
Il suffit de décaler les bits a droite jusqu'à qu'il ne reste que l'octet qui nous intéresse soit le premier en partant de la gauche. On a donc :
bleu = couleur >> 16

Code:: //color_get_blue(color)
return argument0>>16

Pour récupérer le vert on va procéder de la même manière :
vert = couleur >> 8
Mais ensuite comment fait-on ? Il reste l'octet codant le vert mais aussi celui qui code le bleu : [bleu][vert], on a réussit a virer l'octet codant le rouge mais il faut aussi virer celui qui code le bleu.
C'est la qu'intervient l'opérateur &. En fait il va nous permettre de récupérer notre octet :
vert = (couleur >> 8 ) & FF
Explication (x est un bit) : comme 0 & x est toujours égal à 0, et que 1 & x est toujours égal à x, faire XXYY & FF signifie donc faire XXYY & 00FF or comme on l'a vu juste avant XX & 00 seras donc égal à 0 et FF (hexa) étant donc 11111111 (base 2), YY & FF seras donc égal à YY.

Code:: //color_get_green(color)
return (argument0 >> 8) & $FF

Donc pour récupérer le rouge :
Le rouge étant dans [XX][YY][ZZ] à la troisième position, il suffit donc de faire [XX][YY][ZZ] & FF car on ne garderas que le premier octet de droite. On a donc :
rouge = couleur & FF

Code:: //color_get_red(color)
return argument0 & $FF

Exemple 2 : Modifier un octet bit a bit
Si [XX] est un octet, soit [abcdefgh] en base 2 avec abcdefgh des bits, comment récupérer un des bits ou même le modifier ?
En fait c'est très simple, et les seuls opérateurs dont on auras besoin vous l'avez compris c'est & , << et >>.

Récupérer c :
Pour récupérer c, il va falloir détruire tous les autres bits, on va donc utiliser & pour ça :
[abcdefgh] & [00100000] = [00c00000]
Maintenant pour isoler c il faut le décaler pour qu'il soit en première position a droite :
[00c00000]>>5 = c

Récupérer un bit en général :
pour récupérer un bit en général dans un nombre on utilise d'abord & puis on décale. La seule infos dont on à besoin c'est la position du bit dans le nombre (ici ^ signifie puissance).
Bit = ( nombre & 2^position ) >> position , soit
Bit = ( nombre & (1<<position) ) >> position

Code:: //get_bit(nbr, position)
argument1 -= 1
return (argument0 & (1<<argument1))>>argument1

Exemple 3 : xor et la cryptographie

^ est très intéressant car il nous permet de crypter des bits avec d'autres bits.
Ce qu'il y a de très pratique avec ^, c'est cette propriété :
a ^ b = c
c ^ b = a
De cette manière on peut faire :
Cryptage =>
[octet secret] ^ [octet clé] = [octet crypté]
<= Décryptage
[octet crypté] ^ [octet clé] = [octet secret]

A vous de faire un petit algorithme de cryptage pour vous entraîner.
->Par contre il faut savoir qu'un simple cryptage xor agis comme une substitution de caractères.
Il est donc très facile a casser. En revanche si vous utilisez une clé a plusieurs caractères il deviens plus efficace, mais il existe toujours de nombreuses méthodes pas très compliquées pour casser la clé, si elle est plus petite que la taille de la chaîne a crypter et/ou que vous l'utilisez plusieurs fois.
Ne comptez donc pas sur xor si vous devez faire un algorithme de cryptage sécurisé.

8 - Lire/Ecrire en binaire

En informatique les caractères aussi sont codés en binaire.
Le représentation la plus courante utiliseras un octet par caractère.
C'est le code ASCII. La table ASCII contient donc 256 caractères possibles.

En binaire les codes ASCII de
000 00000 à 000 11111 représentent les caractères de contrôle comme NULL, TAB...
001 00000 à 001 01111 les caractères spéciaux comme espace, +, - ...
001 10000 à 001 11001 les nombres de 0 à 9
010 00001 à 010 11010 les lettres majuscules de A à Z
011 00001 à 011 11010 les lettres minuscules de a à z
etc..

Pour lire et écrire en binaire il suffit donc de connaitre au moins les majuscules, les minuscules, et le caractère espace.
Le caractère espace est très simple a retenir, c'est le premier caractère spécial: 001 00000
Pour ce qui est des lettres rien de compliqué non plus.
Un code binaire commençant par 010 est en général une majuscule, et 011 une minuscule.
Il suffit ensuite de regarder le code binaire qui suis ces 3 bits, et il donne la position de la lettre dans l'alphabet.

Donc pour A qui est la première lettre de l'alphabet, en majuscule, on auras:
010 00001, et en minuscule 011 00001.
Pour le Z qui est la 26ième lettre, on convertis 26 en binaire. Cela fait de tête 16+8+2, soit 11010.
Z s'écrit donc 010 11010 et z 011 11010.

Sympa pour ceux qui ne connaissent pas awesome

Sinon, oni, en ce moment, t'es a fond sur les tutos :nezrouge:

Jerry, tu viens de résumer une session voir 2 d'informatique à mon école.
Je sens que va y'en a voir au chomage noel

Bref chapeau, c'est du très bon boulot super

tu pourrias pas me fiare un tuto sur la prochaine année?

merci les gars, et sinon Alpha t'en fait pas , j'en ai prévu encore 2 ou 3 pour les jours qui suivent noel

. Maintenant que le BAC est passé, je vais me lâcher complètement, en espérant aider, et surtout être assez clair pour tout le monde.

à quand la division et multiplication binaire? heheh

par masque et décalage bien sur :nezrouge:

Excellent tuto (comme les autres), c'est bien expliqué et clair, et très intéressant. Perso je connaissais pas le décalage.
Vivement d'autres tutos.

(d'aileurs, même si on est censés changer bientôt de site, tous tes tutos auraient très bien leur place sur le site)

Utilisateur confirmé: Rang ***** Messages : 2232

moi qui devais réviser pour ma rentrée, ben je sais déjà par où commencer. merci oni

Sujet: Re: [Tutoriel] Les opérateurs binaires Lun 6 Sep 2010 - 21:04

bien vu

Sujet: Re: [Tutoriel] Les opérateurs binaires Lun 6 Sep 2010 - 22:44

T'est en quelle année de licence info Chulien ?

Sujet: Re: [Tutoriel] Les opérateurs binaires Lun 6 Sep 2010 - 22:57

Pas faire mon intelligent de service, mais j'ai cru qu'on allait comprendre a quoi sert les opérateur binaires, et arrivé a la fin du tuto j'ai pas compris en quoi sa allait être utile de récupéré une couleur W.W

[Tutoriel] Les opérateurs binaires Gniah

[Tutoriel] Les opérateurs binaires Gniah

Sujet: Re: [Tutoriel] Les opérateurs binaires Lun 6 Sep 2010 - 23:03

Bah deja y a 3 exemples mais je peut en rajouter d'autres, comme la gestion de la mémoire (avec les types de variables) mais bon la c'est surtout pour ceux qui font du C / C++

Utilisateur confirmé: Rang ***** Messages : 2232

ne ris pas, je rentre en master.

Sujet: Re: [Tutoriel] Les opérateurs binaires Jeu 19 Jan 2012 - 18:52

Citation :: b) Conversion base 10 vers base 2

Pour passer de la base 2 à la base 10 c'est un peu plus compliqué.

Sujet: Re: [Tutoriel] Les opérateurs binaires Jeu 19 Jan 2012 - 19:07

Ah merci, je corrige ça.

» Enigmes binaires
» [Tutoriel] GML vs D&D
» Atelier GML 2 - Conditions, opérateurs booléens et scripts
» Tutoriel : Les fichier ini
» [Tutoriel] Ftp Dll