Cette sous-partie est pour ceux qui ne connaissent pas les puissances mathématiques ou qui veulent revoir ce sujet en détail (bouh les noobs :p ). Si vous connaissez ce sujet sur le bout des doigts, vous pouvez sans aucun problème passer cette sous-partie !
Une puissance s'écrit en mathématiques xy. Elle consiste a multiplier x par lui-même autant de fois que la valeur de y. Par exemple, 23 = 2 multiplié par lui-même 3 fois = 2 * 2 * 2 = 8 Le nombre est appelé la base de la puissance, et le nombre de fois qu'il faut le multiplier est appelé l'exposant.
Il existe également des puissances négatives, qui divisent le nombre 1 par la base autant de fois que le spécifie l'exposant. Par exemple, 2-3 = 1 / (2 multiplié par lui même 3 fois) = 1 / (2 * 2 * 2) = 1 / 8. A noter également que toute puissance dont l'exposant est 0 est égale à 1. C'est très important de retenir tout ça !
Avant toute chose, je vais vous expliquer comment fonctionne le système de base décimale, celui que nous utilisons !
Dans notre système, les nombres sont décrits avec des unités, des dizaines, des centaines, et caetera. Et si on le dit d'une autre façon : les nombres sont décrits avec des 100, 101, 102, et caetera.
En système de base binaire, c'est exactement la même chose sauf que les nombres sont décrits avec des 20, 21, 22, et caetera.
(et pour les nombres décimaux, on emploie des puissances négatives, mais ce n'est pas le sujet du tuto ^^ )
A cela il faut ajouter le fait que pour dire quelle quantité d'unités et Cie composent le nombre, on ne peut utiliser que des chiffres de 0 (inclus) au nombre de le base (exclus). Donc la base décimale, ou base 10, utilise des chiffres de 0 à 9, et la base binaire, ou base 2, utilise des chiffres de 0 à 1.
Voici, par exemple, la preuve que le nombre 13 en base binaire est 1101 :
1
1
0
1
1 * 23
1 * 22
0 * 21
1 * 20
8
4
0
1
Et 8 + 4 + 0 + 1 = 13 !
On retombe donc sur nos pattes.
Et maintenant la définition du mot bit en cadeau bonus : Un bit est un chiffre d'un nombre écrit en système de base binaire.
Par exemple, dans notre exemple avec 1101, les bits sont 1, 1, 0, et 1. Pas si compliqué hein ? :-°
Ah aussi, voici, en deuxième cadeau bonus, la méthode à employer pour convertir un nombre décimal en binaire :
On trouve d'abord la puissance dont la base (base de puissance, attention) est 2 qui est inférieure à ce nombre et on le note.
Ensuite on regarde la puissance dont l'exposant est le même que celui du chiffre précédent auquel on soustrait 1, et si on peut additionner le résultat de cette puissance au nombre précédent sans dépasser le nombre décimal, on le note.
On réitère l'étape précédente jusqu'à arriver à l'exposant -1.
Maintenant, comment transformer ce résultat en nombre binaire ? Comme ceci : on regarde l'exposant de la première puissance : c'est le nombre de bits du nombre binaire, on inscrit un 1 dans ce premier bit.
Ensuite, on regarde l'exposant de la puissance suivante, ça veut dire que le bit à la position nombre total de bits - cet exposant = 1
On réitère cette étape jusqu'à arriver à la fin des puissances notées.
Et on remplace les bits restants par 0.
Ça parait très compliqué comme ça, mais c'est pas possible de l'expliquer plus simplement, et une fois que vous aurez compris le principe, vous allez trouver ça très facile. :) (si vous ne comprenez pas, rassurez-vous, ce n'est pas tellement essentiel. ;) )
Bon, tu nous as toujours pas dis ce que c'était tes opérateurs bizarroïdes ...
Une fois un nombre traduit en binaire (c'est automatique dès que vous employez un opérateur bitwise donc pas besoin de la spécifier dans le code ;) ) vous pouvez effectuer des opérations qui comparent un à un leurs bits. Voici leur liste :
| qui renvoie 1 si un des deux bits comparés contient un 1 ou si les deux le contiennent. (on l'appelle le "ou inclusif") ^ qui renvoie 1 si et seulement si les deux bits sont différents. (on l'appelle le "ou exclusif") & qui renvoie 1 si les deux bits valent tous les deux 1. (on l'appelle le "et")
Quand ils ne renvoient pas 1, ils renvoient 0. Ne rigolez pas, ce n'est pas "logique", ils auraient très bien renvoyer une valeur du style de NULL.
Par exemple 2 ^ 3 va renvoyer 1 car :
2
^
3
--
10
^
11
= 01
--
--
--
= 1
Allez, un petit exemple d'utilisation pratique ?
if (i & 1)
{
printf("%i est impair.\n", i);
}
else
{
printf("%i est pair.\n", i);
}
Mais ce que je ne vous ai pas dit, c'est qu'il y a d'autres opérateurs bitwise !
>> qui décale les bits vers la droite. << qui décale les bits vers la gauche. >< qui fait un smiley bizarre.
3 << 1 veut dire "décaler les bits du nombre 3 (soit 11) de 1 bit vers la gauche", ce qui va donner le nombre 110, soit 6 dans notre bon vieux système décimal.
(en effet, les bits non utilisés sont remplis de 0)
On constate que x << y est égal à x * 2y. C'est le même principe avec >>, sauf que là le nombre est tronqué et que son équivalent décimal également !
Par exemple, pour multiplier un nombre par 2, on peut décaler ses bits de 1 vers la droite, soit effectuer l'instruction
C'est bien joli tout ça mais les opérateurs font tout le travail pour nous, c'est facile, et en plus je ne vois pas l'intérêt de tout ça ...
L'intérêt ? Bon ben je vais vous montrer quelques situations que vous ne pourriez résoudre sans les opérateurs bitwise ! Et comme je suis vicieux, ça servira aussi d'exercices :diable: !
Exercice 1
Arrondir un nombre entier stocké dans une variable non signée nommée n au nombre multiple de 8 inférieur, et ce en une ligne de code !
n = (n >> 3) << 3;
Il suffisait d'y penser, n >> 3 divise le nombre par huit et le tronque, il suffit de le remultiplier par huit et on obtient un nombre arrondi !
Exercice 2
Écrire une instruction qui affiche le reste de la division d'un nombre par 8 sans utiliser de modulo ou de division !
printf("%u", (nombre & 7));
Ça parait bizarre hein ? Eh bien non, c'est tout à fait logique : 7 s'écrit 111 en binaire. Donc ça va comparer les 3 derniers bits avec 1 chacun, et sachant que 1 & 1 = 1 et que 0 & 1 = 0, les bits demeurent inchangés et les autres deviennent tous 0 car ils sont comparés avec 0. Les 3 derniers bits étant équivalents au reste de la division par 8 (c'est logique vu qu'on garde seulement la précision après le 8), eh bien ... ça marche. Vous devez sûrement vous demander l'intérêt de ne pas utiliser le modulo ? Eh bien c'est tout simplement que le calcul est bien plus rapide, si vous faites un petit programme, ok on verra pas de différence, mais si vous le faites tourner sur un ordinosaure ou que vous faites plein de calculs en même temps, ça fait une énorme différence de performances !
Cependant, souvent, le compilateur peut réaliser de telles optimisations.
Exercice 3
Écrire une fonction qui renvoie le premier nombre pair qui est inférieur à un nombre impair passé en paramètre, si on envoie un nombre pair à la fonction, elle doit renvoyer ce nombre pair, et tout ça sans employer de condition et avec une seule instruction. Qui a dit "Il est sadique, c'est Mission Impossible" ? >_
Ah aussi, il y a deux solutions possibles ... je veux les deux ! :D
Solution 1
unsigned long pair-o-matic(unsigned long nombre)
{
return (nombre | 1) ^ 1;
}
Un peu d'aspirine ? :ange: nombre | 1 remplace le dernier bit du nombre par un 1, ce qui rend le nombre impair, ensuite le ^ 1 remplace le dernier bit par un 0 ce qui le rend pair. Qui a dit que c'était tiré par les cheveux ?
Solution 2
unsigned long pair-o-matic(unsigned long nombre)
{
return (nombre >> 1) << 1;
}
Dans cette deuxième solution, c'est tout simplement le même principe que dans l'exercice 1 !
unsigned long pair-o-matic(unsigned long nombre)
{
return (nombre | 1) ^ 1;
}
Un peu d'aspirine ? :ange: nombre | 1 remplace le dernier bit du nombre par un 1, ce qui rend le nombre impair, ensuite le ^ 1 remplace le dernier bit par un 0 ce qui le rend pair. Qui a dit que c'était tiré par les cheveux ?
Solution 2
unsigned long pair-o-matic(unsigned long nombre)
{
return (nombre >> 1) << 1;
}
Dans cette deuxième solution, c'est tout simplement le même principe que dans l'exercice 1 !
unsigned long pair-o-matic(unsigned long nombre)
{
return (nombre >> 1) << 1;
}
Dans cette deuxième solution, c'est tout simplement le même principe que dans l'exercice 1 !
Exercice 4
Ecrire une fonction qui renvoie le xième bit d'un nombre en partant de la droite (la position du bit à récupérer étant passée en paramètre).
unsigned int recupererBit(unsigned int position, unsigned long nombre)
{
unsigned int i = 0;
unsigned int puissanceDeDeux = 1;
for (i = 0; i < position; i++)
{
puissanceDeDeux = puissanceDeDeux << 1;
}
return (nombre & puissanceDeDeux) >> i;
}
Tout réside dans le fait que les puissances de base (base de puissance) 2 deviennent en binaire des nombres avec seulement un 1. Du coup, quand on le compare avec & à un nombre, seul un bit précis est retenu, les autres deviennent 0. Cependant, il ne faut pas oublier de supprimer tout ce qui se trouve après le 1, car sinon on aurait des 0 en trop qui agrandiraient le nombre. Ah aussi, attention avec cette fonction : les positions commencent à 0 !
On aurait pu écrire cette fonction de manière plus simple, optimisée et concise:
unsigned int recupererBit(unsigned int position, unsigned long nombre)
{
return ((1 << position) & nombre) >> position;
}
Si vous vous y connaissez en électronique, les opérateurs |, &, et ^ ont du vous rappeler quelque chose ... En effet, ils sont utilisés pour décrire certains circuits électriques, et il est même possible de faire des calculs avec pour déterminer si le courant passe ou ne passe pas. Pour plus d'informations, un excellent lien de Wikipédia : L'algèbre de Boole. On notera aussi que ce p'tit malin de Boole a donné son nom à un type de données : le type Booléen.
Ah aussi, une petite astuce qui n'a rien à voir avec Boole mais que je savais pas où mettre de toutes façons >_ :
Il est possible d'écrire un nombre directement en hexadécimal en le préfixant de 0x, l'hexadécimal est en fait un système de base 16 qui emploie les chiffres (dans l'ordre croissant) 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. Bien qu'on ne puisse pas écrire un nombre directement en binaire en C, l'hexadécimal est quand même bien pratique. ;)
Par exemple :
0x
1
A
-
1 * 161
A * 160
-
16
10
Donc 0x1A = 10 + 16 = 26 !
Vous connaissez maintenant les opérateurs bitwise en détail ! Bravo ! Cela peut par exemple vous servir à vous la péter devant vos copains créer un système de flags comme expliqué ici, faire du cryptage avec l'opérateur « ou exclusif », ou ce que vous voulez. ;)
PS : L'auteur de ce tuto n'est en aucun cas responsable des suicides ou des overdoses d'aspirine pouvant êtres causées par l'exercice 3.