J'ai entendu dire par un de mes amis que le meilleur algorithme pour l'échange est "(a^= b^= a^= b)" où a et b sont deux entiers à échanger. mais lorsque j'ai appliqué cela en utilisant le langage c, il s'est écrasé. quelqu'un d'entre vous peut-il expliquer la raison possible? s'il vous plaît suggérer le meilleur algorithme pour l'échange. merci !!!! les gars, je voudrais savoir la raison de s'écraser.meilleur algorithme pour l'échange?
ce tour de passe-passe est parfois dangereux, j'ai vu un mauvais programme quicksort utilisant ce swap génère des résultats erronés. Mais un échange habituel génère un programme correct. En ce qui concerne la vitesse, le compilateur génère parfois un code plus rapide si nous utilisons une variable tmp.
utilisation tmp = a; a = b; b = tmp;
merci @yin je voudrais savoir pourquoi mon tour est très dangereux? –
XOR swap ('a^= b^= a^= b') ne fonctionnera que sur les entiers (et les pointeurs). XOR swap changera à la fois 'a' et' b' à 0 s'ils sont égaux. – LiraNuna
Supposons que 'a' et' b' sont des pointeurs qui pointent vers la même chose. Alors '(* a)^= (* b)^= (* a)^= (* b)' mettra à zéro la valeur. En C++, si ce sont des références, vous pouvez le faire sans le déréférencement. Mais la véritable raison d'utiliser ce que suggère @Yin Zhu est que votre code devrait être clair, et vous ne devriez pas vous inquiéter d'une micro-optimisation comme celle-ci. – rlbond
Utilisez cette logique pour les valeurs numériques:
int a = 10, b =5 ;
a = a-b;
b = b+a ; // b gets the original value of a
a = b - a; // a gets the original value of b
printf ("value : %d %d \n",a ,b) ;
Que se passe-t-il lorsque 'a' est' INT_MAX', et 'b' est' INT_MIN'? En d'autres termes, 'a-b' peut déborder/déborder. –
@Alok: Malgré le débordement, il donnera toujours la bonne réponse avec l'arithmétique enveloppante. – dan04
@ dan04: l'encapsulation n'est pas garantie - en cas de dépassement d'entier C/C++, UB. –
Voir http://en.wikipedia.org/wiki/Swap_(computer_science). L'utilisation d'une variable temporaire génère plus de frais généraux, mais est plus stable que l'algorithme d'échange XOR et l'informatique parallèle le rend plus rapide que l'échange XOR.
Voir le premier exemple de code de http://www.ibm.com/developerworks/linux/library/l-metaprog1.html pour une implémentation solide de l'utilisation d'une variable temporaire pour l'échange.
pourquoi est générer plus de frais généraux pour la solution variable temporaire? Le swap XOR crée également plus de frais généraux de calcul. – phoxis
a^=b^=a^=b; se bloque probablement parce qu'il invoque le redouté comportement non défini. La règle qu'il casse est qu'il modifie a deux fois sans un point de séquence intermédiaire. Il peut être fixé en insérant des points de séquence - par exemple, avec l'opérateur virgule:
a ^= (b ^= a ^= b, b);`
Ou en le brisant en de multiples déclarations:
b ^= a ^= b; a ^= b;
Il est encore, cependant, le plus souvent une mauvaise méthode pour échanger des variables - plusieurs des autres réponses et commentaires ont correctement expliqué pourquoi.
Ecrivez ce code qui est plus rapide à lire par l'être humain. Et faites confiance aux compilateurs pour générer un meilleur code la plupart du temps. Faites un profilage pour voir si c'est le seul endroit pour améliorer la vitesse. Ensuite, appliquez les solutions XOR énumérées plusieurs fois ci-dessus, cela peut ne pas fonctionner partout.
Je ne peux pas croire que c'est même une question sur SO. Quel est le problème avec 'std :: swap'? –
@BillyONeal: puisque std :: swap est C++ et que cette question est tagguée avec C. – LiraNuna
OK - Désolé - Permettez-moi de changer cela en "Quel est le problème avec l'implémentation simple simple typique de' std :: swap'? 'T temp = un, un = deux; deux = temp; '? Sérieusement - si swap est un limiteur de vitesse de votre programme, alors vous avez un problème que j'aimerais bien avoir: –