Quatre façons d'échanger les valeurs de deux variables sans utiliser la troisième variable

Habituellement, ce que nous faisons (surtout au stade de l'apprentissage) c'est : définir une nouvelle variable et l'utiliser pour compléter l'échange. Le code est le suivant :

int a,b;
a=10; b=15;int t;
t=a; a=b; b=t;

Cet algorithme est facile à comprendre et est particulièrement adapté pour aider les débutants à comprendre les caractéristiques des programmes informatiques. déclarations d'affectation. Dans le développement logiciel réel, cet algorithme est simple et clair, ne provoque pas d'ambiguïté et facilite la communication entre les programmeurs. Dans des circonstances normales, cet algorithme (ci-après appelé algorithme standard) doit être utilisé lorsque l'on rencontre le problème de l'échange de valeurs variables.

Le plus gros inconvénient de l'algorithme ci-dessus est qu'il nécessite l'utilisation d'une variable temporaire. Alors, l’échange peut-il être réalisé sans l’aide de variables temporaires ? La réponse est oui ! Ici, nous pouvons utiliser trois algorithmes pour implémenter : 1) les opérations arithmétiques ; 2) les opérations d’adresse de pointeur 3) les opérations sur les bits ; 4) l’implémentation de la pile ;

1) Opérations arithmétiques

int a,b;
a=10;b=12;
a=b-a; //a=2;b=12b=b-a; //a=2;b=10a=b+a; //a=10;b=10

Le principe est : traiter a et b comme des points sur l'axe des nombres, autour de la distance entre les deux points pour effectuer des calculs.

Le processus spécifique : la première phrase "a=b-a" trouve la distance entre deux points ab, et l'enregistre dans a ; la deuxième phrase "b=b-a" trouve la distance de a au distance d'origine (la différence entre la distance entre b et l'origine et la distance entre ab et ab), et enregistrez-la dans b ; la troisième phrase "a=b+a" trouve la distance entre b et l'origine (la distance entre a et l'origine et la distance entre ab et ab) distance) et enregistrez-le dans a. Terminez l'échange.
Par rapport à l'algorithme standard, cet algorithme comporte trois processus de calcul supplémentaires, mais n'utilise pas de variables temporaires. (Ci-après dénommés algorithmes arithmétiques)

Inconvénient : il ne peut être utilisé que pour les types numériques, pas pour les chaînes, etc. a+b peut déborder (au-delà de la plage de int). Le débordement est relatif. Si + déborde, - ira bien si - revient donc peu importe s'il déborde ou non, c'est tout simplement dangereux.

2) Opération d'adresse de pointeur
Parce que l'opération d'adresse effectue en fait des opérations sur des entiers, par exemple : soustraire deux adresses pour obtenir un entier, indiquant que les emplacements de stockage des deux variables dans la mémoire sont séparés . Combien d'octets ; l'adresse est ajoutée à un entier, c'est-à-dire que "a+10" représente l'adresse des 10 unités de données de classe a après a avec a comme adresse de base. Par conséquent, en théorie, l'échange d'adresses peut être effectué par des opérations similaires aux algorithmes arithmétiques, atteignant ainsi l'objectif d'échange de variables. C'est-à-dire :

int *a,*b; //假设*a=new int(10);*b=new int(20); //&a=0x00001000h,&b=0x00001200ha=(int*)(b-a); //&a=0x00000200h,&b=0x00001200hb=(int*)(b-a); //&a=0x00000200h,&b=0x00001000ha=(int*)(b+int(a)); //&a=0x00001200h,&b=0x00001000h

Grâce à l'opération ci-dessus, les adresses de a et b ont réellement été échangées, et a pointe vers la valeur initialement pointée par b, et b pointe vers la valeur initialement indiquée par a. Le code ci-dessus peut être compilé, mais les résultats d'exécution sont incroyables ! Pourquoi?

Tout d'abord, vous devez comprendre que le système d'exploitation divise la mémoire en plusieurs zones : zone de code/données système, zone de code/données d'application, zone de pile, zone de données globales, etc. Lors de la compilation du programme source, les constantes, les variables globales, etc. sont placées dans la zone de données globales, et les variables locales et dynamiques sont placées dans la zone de pile. De cette façon, lorsque l'algorithme est exécuté sur "a=(int*)(b-a)", la valeur de a n'est pas 0x00000200h, mais l'adresse de base de la zone mémoire où se trouve la variable a. Le résultat réel est : 0x008f0200h. , où 0x008f est L'adresse de base, 0200, est le déplacement de a dans la zone mémoire. Il est ajouté automatiquement par le compilateur. En conséquence, les calculs d'adresses futures sont incorrects, ce qui fait que a et b pointent vers d'autres unités de mémoire dans la zone. Troisièmement, les nombres négatifs ne peuvent pas apparaître dans les opérations d'adresse, c'est-à-dire que lorsque l'adresse de a est supérieure à l'adresse de b, b-aY a-t-il une solution ? certainement! Voici l'algorithme amélioré :

if(a<b)
{
a=(int*)(b-a);
b=(int*)(b-(int(a)&0x0000ffff));
a=(int*)(b+(int(a)&0x0000ffff));
}else{
b=(int*)(a-b);
a=(int*)(a-(int(b)&0x0000ffff));
b=(int*)(a+(int(b)&0x0000ffff));
}

La plus grande amélioration de l'algorithme consiste à utiliser l'opération ET "int(a)&0x0000ffff" dans l'opération sur les bits, car les 16 supérieurs Les bits de l'adresse sont l'adresse du segment, les 16 derniers bits sont l'adresse de déplacement. Après l'avoir effectuée avec 0x0000ffff, l'adresse du segment est masquée et seule l'adresse de déplacement est conservée. Cela correspond à l'algorithme d'origine et obtient le résultat correct.

Cet algorithme complète également l'échange de valeurs sans utiliser de troisième variable. Par rapport aux algorithmes arithmétiques, il est difficile à comprendre, mais il a son avantage, c'est-à-dire que lors de l'échange de types de données volumineux, sa vitesse d'exécution est plus rapide. que l'arithmétique. L'algorithme est rapide. Parce qu'il échange l'adresse, la valeur de la variable n'a pas été déplacée en mémoire. (Ci-après dénommé l'algorithme d'adresse)

3) Opérations sur les bits

int a=10,b=12; //a=1010^b=1100;a=a^b; //a=0110^b=1100;b=a^b; //a=0110^b=1010;a=a^b; //a=1100=12;b=1010;

La réalisation de cet algorithme est déterminée par les caractéristiques de l'opération XOR. peut inverser certains bits des données et laisser les autres bits inchangés. Cela signifie que tout nombre et toute valeur donnée sont XORed deux fois de suite et que la valeur reste inchangée.

4) Implémentation de la pile. Aucune autre explication n'est nécessaire, la pile et les définitions des fonctions associées sont omises.

int exchange(int x,int y) 
{ 
     stack S; 
     push(S,x); 
     push(S,y); 
     x=pop(S); 
     y=pop(S); 
}

Les algorithmes ci-dessus réalisent tous l'échange de deux valeurs variables sans l'aide d'autres variables. En comparaison, l'algorithme arithmétique et l'algorithme binaire ont la même quantité de. calcul. Le calcul dans l'algorithme d'adresse Il est plus complexe, mais il peut facilement réaliser l'échange de grands types (tels que des classes ou des structures personnalisées), alors que les deux premiers ne peuvent échanger que des données entières (en théorie, surcharger le "^" l'opérateur peut également réaliser toute structure d'échange).

L'introduction de ces trois algorithmes n'est pas destinée à être appliquée dans la pratique, mais à discuter de technologie et à démontrer le charme de la programmation. Il ressort de cela que de petites compétences en mathématiques ont une influence considérable sur la programmation et, si elles sont utilisées correctement, elles auront des effets magiques inattendus. Du point de vue du développement logiciel réel, l’algorithme standard est sans aucun doute le meilleur et peut résoudre tout type de problème d’échange.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!