Il est donc possible de permuter les valeurs de deux variables sans passer par une variable intermédiaire.
Il suffit pour cela d'utiliser le code suivant :
<?php // soit $x et $y deux variables // pour permuter leurs valeurs, il suffit de faire : $x = $x ^ $y; $y = $y ^ $x; $x = $x ^ $y; ?>
Pour ceux qui se poserait la question, l'opérateur ^ correspond au ou exclusif
de la logique booléenne.
Évidemment, pour que la magie opère, il y a une contrainte.
Il faut en effet impérativement que les deux variables soient stockées sur le même nombre de bits.
En clair, cela fonctionne, dans le cas de PHP, uniquement pour les entiers et les chaînes de caractères de même longueur.
Je sais d'avance que certains vont s'interroger sur les performances de cette astuce et je vais donc répondre immédiatement à cette interrogation.
Les performances de cette astuce, du moins en PHP, sont tout bonnement lamentable, puisqu'elle est sur ma machine 2.5 fois plus lente que la permutation traditionnelle à l'aide d'une variable temporaire !
Pourquoi en parler alors ?
Comme je l'ai dis en introduction, pour l'esthétique de la chose, et également pour faire triper Ivan !
Et pour ceux qui se poserait la question, j'ai découvert cette astuce dans Hacker's delight
, véritable mine d'or de trucs et astuces de la même veine que celui-ci pour amateur d'algèbre de Boole et de nœuds au cerveau.
15 réactions
1 De Ivan Enderlin - 13/12/2011, 14:08
Hey :-),
Hehe, je connaissais cette astuce pour les entiers et booléens, mais pas pour les chaînes de caractères.
La contrainte « même taille » est forte par contre :-/, dommage !
Récemment j'ai twitté ceci :
J'aime bien le
$x == ($x & -$x), c'est astucieux, et pour le coup, les performances sont démentes ;-).C'est Jérôme Renard (@jeromerenard) qui m'avait donné la référence du livre dont tu parles, il va falloir que j'y jette un œil ;-).
Merci pour le clin d'œil !
2 De Savageman - 13/12/2011, 14:14
Moi je faisais list($x, $y) = array($y, $x); Mais ton truc est sans doute plus efficace pour les entiers.
3 De mageekguy - 13/12/2011, 14:28
@Savageman : Ce n'est même pas une question d'efficacité, ton
array($x, $y)équivaut à une variable temporaire, auquel il faut ajouter les dépilages/empilages liés aux appels de fonction.Bref, ça ne joue pas dans la même catégorie vu que l'idée est de faire une permutation en consommant le minimum de ressource possible.
4 De Savageman - 13/12/2011, 14:43
@mageekguy: List n'est pas une fonction. Mais je pensais bon de le mentionner parce que c'est une one-liner assez élégant quand même.
5 De mageekguy - 13/12/2011, 15:02
@Savageman : List() a beau ne pas être une fonction mais une construction du langage, il faut bien tout de même empiler/dépiler ses arguments quelque part dans la mémoire ;).
6 De Pascal MARTIN - 13/12/2011, 18:49
Et si tu veux obtenir une syntaxe "encore plus marrante", tu peux écrire le tout sur une ligne :
$a ^= $b ^= $a ^= $b;
Il ne me semble jamais avoir vu ça dans du code "réel", en plus de 5 ans de vie pro... Mais ça m'avait moi aussi fait sourire, quand j'avais découvert ça ^^
(c'était en C, à l'époque ; mais ça fonctionne aussi en PHP)
7 De Nami-Doc - 13/12/2011, 21:39
Tu peux faire pareil sans utiliser ^, en fait :).
$b = $a - $b + ($a = $b);
8 De Matthieu - 13/12/2011, 23:20
@Nami-Doc : Ingénieux !
9 De joey - 14/12/2011, 00:37
Au lieu de vous prendre la tête sur des petits trucs insignifiants (et gourmands, en plus), vous feriez mieux de vous concentrer sur les trucs vraiment novateurs et super performants.
Cet algorithme de tri révolutionnaire, par exemple :
http://www.dangermouse.net/esoteric...
Ça, vous voyez, ÇA c'est du temps bien utilisé
10 De mageekguy - 14/12/2011, 08:55
@joey : Que ce genre de choses ne soit pas ton truc ou que tu trouves cela inutile, je peux le comprendre (d'ailleurs, je précise bien dans le billet que ça l'est).
Par contre, que tu le dises sur ce ton et de cette façon m'a beaucoup dérangé et du coup, j'ai vraiment hésité à publier ton commentaire.
Ton lien étant intéressant, je t'ai tout de même publié, mais à l'avenir, un peu plus de respect serait le bienvenu.
Chacun voit midi à sa porte.
11 De francois - 14/12/2011, 12:06
@joey, le lien est intéressant mais dit clairement que cet algorithme n'est pas vraiment plus efficace, puisqu'il a la particularité d'être un "lossy algorithm". cela peut être acceptable comme algorithme, mais tout dépend du besoin. Et que je sache, il existe déjà des algorithmes en O(n) qui ne nécessitent pas ce risque de pertes.
Ensuite, la partie "amusante" de ce billet sont justement les astuces du calcul booléen. J'aime beaucoup ce billet pour cela et j'avoue que le petit algo pour voir si on a une puissance de 2 est vraiment sympathique et ultra performant.
Ca me rappelle un cours qu'on avait eu sur les micro-controleurs pour lesquels on avait dû faire du reverse bit à bit. Bon billet mageekguy.
12 De joey - 14/12/2011, 12:51
bah fallait pas le prendre mal : je l'ai lu l'article c'est bien que ça m'a amusé comme toi cette petite astuce booléenne. mais le Dropsort c'est drôle surtout que parce que c'est présenté de manière arrogante. mon intro c'était juste pour préparer le terrain de ce magnifique algorithme (qui date un peu d'ailleurs. j'ai l'impression qu'il a /réellement/ été utilisé dans la finance depuis).
et puis je pensais que la dernière phrase était assez ironique pour déminer le début. dans le doute j'ai même ajouté un smiley mais peut-être que c'était trop trash d'entrée de jeu. mes excuses.
13 De Matthieu - 15/12/2011, 14:19
@joey : Ton commentaire m'a bien fait rire. Enfin l'ironie sur internet, il vaut mieux en faire trop que pas assez pour être sur d'être compris
14 De francois.m - 16/12/2011, 00:50
Ca me rappelle vaguement des trucs qu'on faisait en assembleur il y a une pelletée d'années :
XOR AX, BX
XOR BX, AX
XOR AX, BX
Mais là, c'était performant puisque forcément sur des variables de même alignement.
15 De JB - 26/12/2011, 17:19
Tiens je suis étonné que tu ne connaissais pas cette méthode. Même moi qui suis une quiche en programmation j'étais tombé dessus plusieurs fois.
C'est le genre d'astuces que j'adore. De la vraie geekerie.