Austauschen zweier Variablenwerte ohne Verwendung der dritten Variablen

Eine der sehr kniffligen Fragen, die in einem Interview gestellt wurden.

Tausche die Werte zweier Variablen wie a=10 und b=15 .

Um zwei Variablenwerte zu vertauschen, benötigen wir eine dritte Variable wie:

 temp=a; a=b; b=temp; 

Jetzt ist die Anforderung, Werte von zwei Variablen zu tauschen, ohne die dritte Variable zu verwenden.

   

Verwenden des Xor-Swap-Algorithmus

 void xorSwap (int* x, int* y) { if (x != y) { //ensure that memory locations are different *x ^= *y; *y ^= *x; *x ^= *y; } } 

Warum der Test?

Der Test soll sicherstellen, dass x und y unterschiedliche Speicherplätze haben (anstatt unterschiedliche Werte). Dies liegt daran, dass (p xor p) = 0 x oder (p xor p) = 0 und beide, wenn x und y denselben Speicherplatz haben, auf 0 gesetzt sind, wenn beide auf 0 gesetzt sind. Wenn sowohl * x als auch * y 0 sind, werden alle anderen xor-Operationen ausgeführt * x und * y sind gleich 0 (da sie gleich sind), was bedeutet, dass die function sowohl * x als auch * y auf 0 setzt.

Wenn sie dieselben Werte aber nicht denselben Speicherort haben, funktioniert alles wie erwartet

 *x = 0011 *y = 0011 //Note, x and y do not share an address. x != y *x = *x xor *y //*x = 0011 xor 0011 //So *x is 0000 *y = *x xor *y //*y = 0000 xor 0011 //So *y is 0011 *x = *x xor *y //*x = 0000 xor 0011 //So *x is 0011 

Soll das verwendet werden?

In den meisten Fällen, nein. Der Compiler optimiert die temporäre Variable und da Swapping ein gängiges Verfahren ist, sollte er den optimalen Maschinencode für Ihre Plattform ausgeben.

Nehmen Sie zum Beispiel dieses in C geschriebene Schnelltestprogramm.

 #include  #include  #define USE_XOR void xorSwap(int* x, int *y){ if ( x != y ){ *x ^= *y; *y ^= *x; *x ^= *y; } } void tempSwap(int* x, int* y){ int t; t = *y; *y = *x; *x = t; } int main(int argc, char* argv[]){ int x = 4; int y = 5; int z = pow(2,28); while ( z-- ){ # ifdef USE_XOR xorSwap(&x,&y); # else tempSwap(&x, &y); # endif } return x + y; } 

Zusammengestellt mit:

 gcc -Os main.c -o swap 

Die Xor-Version dauert

 real 0m2.068s user 0m2.048s sys 0m0.000s 

Wo wie die Version mit der temporären Variable dauert:

 real 0m0.543s user 0m0.540s sys 0m0.000s 

Die allgemeine Form ist:

 A = A operation B B = A inverse-operation B A = A inverse-operation B 

Sie müssen jedoch möglicherweise auf Überläufe achten, und außerdem haben nicht alle Operationen eine Umkehrung, die für alle Werte, für die die Operation definiert ist, genau definiert ist. zB * und / arbeiten, bis A oder B 0 ist

xor ist besonders erfreulich, da es für alle Ints definiert ist und eine eigene Inverse ist

 a = a + b b = a - b // b = a a = a - b 

Noch niemand hat vorgeschlagen, std::swap .

 std::swap(a, b); 

Ich verwende keine temporären Variablen und abhängig von der Art von a und b die Implementierung eine Spezifizierung haben, die dies auch nicht tut. Die Implementierung sollte geschrieben werden, ob ein “Trick” angebracht ist oder nicht. Es hat keinen Sinn zu versuchen, zu raten.

Allgemeiner würde ich wahrscheinlich so etwas tun wollen, da es für classnarten funktionieren würde, die es ADL ermöglichen würden, wenn möglich eine bessere Überladung zu finden.

 using std::swap; swap(a, b); 

Natürlich kann die Reaktion des Interviewers auf diese Antwort viel über die offene Stelle sagen.

Wie bereits von manu angemerkt, ist der XOR-Algorithmus ein populärer Algorithmus, der für alle Ganzzahlwerte funktioniert (also pointers mit etwas Glück und Casting). Der Vollständigkeit halber möchte ich noch einen weniger leistungsfähigen Algorithmus mit Addition / Subtraktion erwähnen:

 A = A + B B = A - B A = A - B 

Hier muss man auf Überläufe / Unterläufe achten, ansonsten funktioniert es genauso gut. Sie können dies sogar auf Floats / Doubles versuchen, falls XOR auf diesen nicht erlaubt ist.

Dumme Fragen verdienen angemessene Antworten:

 void sw2ap(int& a, int& b) { register int temp = a; // ! a = b; b = temp; } 

Die einzige gute Verwendung des Schlüsselwortes register .

Haben Sie sich den XOR-Swap-Algorithmus angesehen ?

 #include #include void main() { int a,b; clrscr(); cout< <"\n==========Vikas=========="; cout<<"\n\nEnter the two no=:"; cin>>a>>b; cout< <"\na"<
		      	

Da die ursprüngliche Lösung ist:

 temp = x; y = x; x = temp; 

Sie können es zu einem zwei Liner machen mit:

 temp = x; y = y + temp -(x=y); 

Dann machen Sie es zu einem einzigen Liner mit:

 x = x + y -(y=x); 

Hier ist eine weitere Lösung, aber ein einzelnes Risiko.

Code:

 #include  #include  void main() { int a =10 , b =45; *(&a+1 ) = a; a =b; b =*(&a +1); } 

Jeder Wert an der Position a + 1 wird überschrieben.

Wenn Sie ein wenig die Frage ändern, um 2 Assembly-Register anstelle von Variablen zu fragen, können Sie auch die xchg Operation als eine Option und die xchg als eine andere verwenden.

Betrachte a=10 , b=15 :

Verwenden von Addition und Subtraktion

 a = a + b //a=25 b = a - b //b=10 a = a - b //a=15 

Mit Division und Multiplikation

 a = a * b //a=150 b = a / b //b=10 a = a / b //a=15 
 #include  int main() { int a, b; printf("Enter A :"); scanf("%d",&a); printf("Enter B :"); scanf("%d",&b); a ^= b; b ^= a; a ^= b; printf("\nValue of A=%d B=%d ",a,b); return 1; } 

das ist der richtige XOR-Swap-Algorithmus

 void xorSwap (int* x, int* y) { if (x != y) { //ensure that memory locations are different if (*x != *y) { //ensure that values are different *x ^= *y; *y ^= *x; *x ^= *y; } } } 

Sie müssen sicherstellen, dass die Speicherorte unterschiedlich sind und dass die tatsächlichen Werte unterschiedlich sind, da A XOR A = 0 ist

Sie können … auf einfache Weise … innerhalb einer Zeile Logic

 #include  int main() { int a, b; printf("Enter A :"); scanf("%d",&a); printf("Enter B :"); scanf("%d",&b); int a = 1,b = 2; a=a^b^(b=a); printf("\nValue of A=%d B=%d ",a,b); return 1; } 

oder

 #include  int main() { int a, b; printf("Enter A :"); scanf("%d",&a); printf("Enter B :"); scanf("%d",&b); int a = 1,b = 2; a=a+b-(b=a); printf("\nValue of A=%d B=%d ",a,b); return 1; } 
 public void swapnumber(int a,int b){ a = a+b-(b=a); System.out.println("a = "+a +" b= "+b); } 

Die beste Antwort wäre, XOR zu verwenden und es in einer Zeile zu verwenden wäre cool.

  (x ^= y), (y ^= x), (x ^= y); 

x, y sind Variablen und das Komma zwischen ihnen führt die Sequenzpunkte ein, so dass es nicht kompilerabhängig wird. Prost!

Sehen wir uns ein einfaches Beispiel an, um zwei Zahlen zu vertauschen, ohne die dritte Variable zu verwenden.

Programm 1:

 #include #include main() { int a=10, b=20; clrscr(); printf("Before swap a=%db=%d",a,b); a=a+b;//a=30 (10+20) b=ab;//b=10 (30-20) a=ab;//a=20 (30-10) printf("\nAfter swap a=%db=%d",a,b); getch(); } 

Ausgabe:

Vor dem Tausch a = 10 b = 20 Nach dem Tausch a = 20 b = 10

Programm 2: Verwenden von * und /

Sehen wir uns ein anderes Beispiel an, um zwei Zahlen mit * und / zu vertauschen.

 #include #include main() { int a=10, b=20; clrscr(); printf("Before swap a=%db=%d",a,b); a=a*b;//a=200 (10*20) b=a/b;//b=10 (200/20) a=a/b;//a=20 (200/10) printf("\nAfter swap a=%db=%d",a,b); getch(); } 

Ausgabe:

Vor dem Tausch a = 10 b = 20 Nach dem Tausch a = 20 b = 10

Programm 3: Verwendung des bitweisen XOR-Operators:

Der bitweise XOR-Operator kann verwendet werden, um zwei Variablen zu vertauschen. Das XOR von zwei Zahlen x und y gibt eine Zahl zurück, die alle Bits als 1 hat, wo immer sich Bits von x und y unterscheiden. Zum Beispiel ist XOR von 10 (In Binary 1010) und 5 (In Binary 0101) 1111 und XOR von 7 (0111) und 5 (0101) ist (0010).

 #include  int main() { int x = 10, y = 5; // Code to swap 'x' (1010) and 'y' (0101) x = x ^ y; // x now becomes 15 (1111) y = x ^ y; // y becomes 10 (1010) x = x ^ y; // x becomes 5 (0101) printf("After Swapping: x = %d, y = %d", x, y); return 0; 

Ausgabe:

Nach dem Austausch: x = 5, y = 10

Programm 4:

Noch niemand hat vorgeschlagen, std :: swap zu verwenden.

 std::swap(a, b); 

Ich verwende keine temporären Variablen und je nach Typ von a und b kann die Implementierung auch eine Spezialisierung haben, die dies nicht tut. Die Implementierung sollte geschrieben werden, ob ein “Trick” angebracht ist oder nicht.

Probleme mit obigen Methoden:

1) Der Multiplikations- und Divisionsbasierte Ansatz funktioniert nicht, wenn eine der Zahlen 0 ist, da das Produkt unabhängig von der anderen Zahl 0 wird.

2) Beide arithmetischen Lösungen können arithmetischen Überlauf verursachen. Wenn x und y zu groß sind, können Addition und Multiplikation außerhalb des ganzzahligen Bereichs liegen.

3) Wenn wir pointers auf eine Variable verwenden und einen functionswap ausführen, schlagen alle oben genannten Methoden fehl, wenn beide pointers auf dieselbe Variable zeigen. Werfen wir einen Blick darauf, was in diesem Fall passieren wird, wenn beide auf dieselbe Variable zeigen.

// Bitweise XOR-basierte Methode

 x = x ^ x; // x becomes 0 x = x ^ x; // x remains 0 x = x ^ x; // x remains 0 

// Arithmetisch basierte Methode

 x = x + x; // x becomes 2x x = x – x; // x becomes 0 x = x – x; // x remains 0 

Lassen Sie uns das folgende Programm sehen.

 #include  void swap(int *xp, int *yp) { *xp = *xp ^ *yp; *yp = *xp ^ *yp; *xp = *xp ^ *yp; } int main() { int x = 10; swap(&x, &x); printf("After swap(&x, &x): x = %d", x); return 0; } 

Ausgabe :

Nach dem Austausch (& x, & x): x = 0

Der Austausch einer Variablen mit sich selbst kann in vielen Standardalgorithmen erforderlich sein. Sehen Sie sich beispielsweise diese Implementierung von QuickSort an, in der wir eine Variable mit sich selbst austauschen können. Das obige Problem kann vermieden werden, indem eine Bedingung vor dem Austausch gestellt wird.

 #include  void swap(int *xp, int *yp) { if (xp == yp) // Check if the two addresses are same return; *xp = *xp + *yp; *yp = *xp - *yp; *xp = *xp - *yp; } int main() { int x = 10; swap(&x, &x); printf("After swap(&x, &x): x = %d", x); return 0; } 

Ausgabe :

Nach dem Austausch (& x, & x): x = 10

Tauschen Sie zwei Zahlen mit der dritten Variable wie folgt aus:

 int temp; int a=10; int b=20; temp = a; a = b; b = temp; printf ("Value of a", %a); printf ("Value of b", %b); 

Tausche zwei Zahlen ohne die dritte Variable zu verwenden

 int a = 10; int b = 20; a = a+b; b = ab; a = ab; printf ("value of a=", %a); printf ("value of b=", %b); 

Vielleicht außerhalb des Themas, aber wenn Sie wissen, was Sie eine einzelne Variable zwischen zwei verschiedenen Werten austauschen, können Sie Array-Logik möglicherweise tun. Jedes Mal, wenn diese Codezeile ausgeführt wird, wird der Wert zwischen 1 und 2 ausgetauscht.

 n = [2, 1][n - 1] 
 a = a + b - (b=a); 

Es ist sehr einfach, aber es kann eine Warnung auslösen.

Einzeilige Lösung für den Austausch von zwei Werten in der Sprache c.

 a=(b=(a=a+b,ab),ab); 
 second_value -= first_value; first_value += second_value; second_value -= first_value; second_value *= -1;