Zamiana wartości dwóch zmiennych bez użycia trzeciej zmiennej

Jedno z bardzo trudnych pytań zadawanych w wywiadzie.

Zamień wartości dwóch zmiennych, takich jak a=10i b=15.

Generalnie, aby zamienić wartości dwóch zmiennych, potrzebujemy trzeciej zmiennej, takiej jak:

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

Teraz wymaganiem jest, zamień wartości dwóch zmiennych bez używania trzeciej zmiennej.

Korzystanie z algorytmu wymiany xor

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

Dlaczego test?

Test ma na celu upewnienie się, że x i y mają różne lokalizacje pamięci (zamiast różnych wartości). Dzieje się tak, ponieważ (p xor p) = 0i jeśli oba x i y mają tę samą lokalizację pamięci, gdy jeden jest ustawiony na 0, oba są ustawione na 0. Gdy oba * x i * y mają wartość 0, wszystkie inne operacje xor na * x i * y będą równe 0 (ponieważ są takie same), co oznacza, że ​​funkcja ustawi zarówno * x, jak i * y na 0.

Jeśli mają te same wartości, ale nie to samo miejsce w pamięci, wszystko działa zgodnie z oczekiwaniami

*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

Czy powinno to być używane?

W ogólnych przypadkach nie. Kompilator zoptymalizuje zmienną tymczasową i biorąc pod uwagę, że zamiana jest powszechną procedurą, powinien wypisać optymalny kod maszynowy dla twojej platformy.

Weźmy na przykład ten szybki program testowy napisany w C.

#include <stdlib.h>
#include <math.h>

#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;    
}

Skompilowano przy użyciu:

gcc -Os main.c -o swap

Wersja xor trwa

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

Gdzie jako wersja ze zmienną tymczasową przyjmuje:

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

ogólna forma to:

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

jednak trzeba potencjalnie uważać na przepełnienia, a także nie wszystkie operacje mają odwrotność, która jest dobrze zdefiniowana dla wszystkich wartości, które są zdefiniowane. np. * i / działa, aż A lub B będzie równe 0

xor jest szczególnie przyjemny, ponieważ jest zdefiniowany dla wszystkich int i jest jego własną odwrotnością

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

Nikt jeszcze nie zasugerował używania std::swap.

std::swap(a, b);

Nie używam żadnych zmiennych tymczasowych iw zależności od typu ai bimplementacji może mieć specjalizację, która też nie. Implementację należy napisać, wiedząc, czy „sztuczka” jest odpowiednia, czy nie. Nie ma sensu próbować odgadnąć.

Mówiąc bardziej ogólnie, prawdopodobnie chciałbym zrobić coś takiego, ponieważ zadziałałoby to dla typów klas umożliwiających ADL znalezienie lepszego przeciążenia, jeśli to możliwe.

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

Oczywiście reakcja ankietera na tę odpowiedź może wiele powiedzieć o wakacie.

Jak już zauważył manu, algorytm XOR jest popularnym algorytmem, który działa dla wszystkich wartości całkowitych (które zawierają wtedy wskaźniki, przy odrobinie szczęścia i rzutowaniu). Ze względu na kompletność chciałbym wspomnieć o innym mniej wydajnym algorytmie z dodawaniem / odejmowaniem:

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

Tutaj musisz uważać na przepełnienia / niedomiary, ale poza tym działa równie dobrze. Możesz nawet spróbować tego na pływakach / podwójnych w przypadku, gdy XOR nie jest na nich dozwolony.

Głupie pytania zasługują na odpowiednie odpowiedzi:

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

Jedyne dobre użycie registersłowa kluczowego.

Zamiana dwóch liczb za pomocą trzeciej zmiennej wygląda tak:

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

Zamiana dwóch liczb bez użycia trzeciej zmiennej

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

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

cout<<"\n\na="<<a<<"\nb="<<b;
getch();
}

Ponieważ oryginalne rozwiązanie to:

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

Możesz zrobić z niego dwie wkładki, używając:

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

Następnie zrób z tego jedną wkładkę, używając:

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

Jeśli zmienisz trochę pytanie, aby zadać pytanie o 2 rejestry asemblerowe zamiast zmiennych, możesz użyć xchgoperacji jako jednej opcji, a operacji na stosie jako innej.

Rozważmy a=10, b=15:

Korzystanie z dodawania i odejmowania

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

Dzielenie i mnożenie

a = a * b //a=150
b = a / b //b=10
a = a / b //a=15

#include <iostream>
using namespace std;
int main(void)
{   
 int a,b;
 cout<<"Enter a integer" <<endl;
 cin>>a;
 cout<<"\n Enter b integer"<<endl;
 cin>>b;

  a = a^b;
  b = a^b;
  a = a^b;

  cout<<" a= "<<a <<"   b="<<b<<endl;
  return 0;
}

Aktualizacja: W tym przypadku pobieramy dane wejściowe z dwóch liczb całkowitych od użytkownika. Następnie używamy bitowej operacji XOR , aby je zamienić.

Że mamy dwie liczby całkowite a=4i b=9, a następnie:

a=a^b --> 13=4^9 
b=a^b --> 4=13^9 
a=a^b --> 9=13^9

Oto jeszcze jedno rozwiązanie, ale jedno ryzyko.

kod:

#include <iostream>
#include <conio.h>
void main()
{

int a =10 , b =45;
*(&a+1 ) = a;
a =b;
b =*(&a +1);
}

każda wartość w lokalizacji a + 1 zostanie nadpisana.

Oczywiście odpowiedź C ++ powinna brzmieć std::swap.

Jednak nie ma również trzeciej zmiennej w następującej implementacji swap:

template <typename T>
void swap (T &a, T &b) {
    std::pair<T &, T &>(a, b) = std::make_pair(b, a);
}

Lub jako jednowierszowe:

std::make_pair(std::ref(a), std::ref(b)) = std::make_pair(b, a);

#include <stdio.h>

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;
}

to jest poprawny algorytm wymiany XOR

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;
      }
   }
}

musisz upewnić się, że lokalizacje pamięci są różne, a także, że rzeczywiste wartości są różne, ponieważ A XOR A = 0

Możesz to zrobić… w prosty sposób… w ramach jednej linii Logiki

#include <stdio.h>

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;
}

lub

#include <stdio.h>

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);
}

Najlepszą odpowiedzią byłoby użycie XOR i użycie go w jednej linii byłoby fajne.

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

x, y to zmienne, a przecinek między nimi wprowadza punkty sekwencji, więc nie zależy od kompilatora. Twoje zdrowie!

Zobaczmy prosty przykład w c, aby zamienić dwie liczby bez użycia trzeciej zmiennej.

program 1:

#include<stdio.h>
#include<conio.h>
main()
{
int a=10, b=20;
clrscr();
printf("Before swap a=%d b=%d",a,b);
a=a+b;//a=30 (10+20)
b=a-b;//b=10 (30-20)
a=a-b;//a=20 (30-10)
printf("\nAfter swap a=%d b=%d",a,b);
getch();
}

Wynik:

Przed zamianą a = 10 b = 20 Po zamianie a = 20 b = 10

Program 2: Używanie * i /

Zobaczmy inny przykład zamiany dwóch liczb za pomocą * i /.

#include<stdio.h>
#include<conio.h>
main()
{
int a=10, b=20;
clrscr();
printf("Before swap a=%d b=%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=%d b=%d",a,b);
getch();
}

Wynik:

Przed zamianą a = 10 b = 20 Po zamianie a = 20 b = 10

Program 3: Wykorzystanie bitowego operatora XOR:

Bitowy operator XOR może służyć do zamiany dwóch zmiennych. XOR dwóch liczb xiy zwraca liczbę, która ma wszystkie bity jako 1, gdziekolwiek bity x i y różnią się. Na przykład XOR z 10 (binarnie 1010) i 5 (binarnie 0101) to 1111, a XOR z 7 (0111) i 5 (0101) to (0010).

#include <stdio.h>
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;

Wynik:

Po zamianie: x = 5, y = 10

Program 4:

Nikt jeszcze nie zasugerował używania std :: swap.

std::swap(a, b);

Nie używam żadnych zmiennych tymczasowych iw zależności od typu aib implementacja może mieć specjalizację, która też nie. Implementację należy napisać, wiedząc, czy „sztuczka” jest odpowiednia, czy nie.

Problemy z powyższymi metodami:

1) Podejście oparte na mnożeniu i dzieleniu nie działa, jeśli jedna z liczb jest równa 0, ponieważ iloczyn staje się 0 niezależnie od drugiej liczby.

2) Oba rozwiązania arytmetyczne mogą powodować przepełnienie arytmetyczne. Jeśli x i y są zbyt duże, dodawanie i mnożenie może wyjść poza zakres liczb całkowitych.

3) Kiedy używamy wskaźników do zmiennej i dokonujemy zamiany funkcji, wszystkie powyższe metody zawodzą, gdy oba wskaźniki wskazują na tę samą zmienną. Zobaczmy, co się stanie w tym przypadku, jeśli oba wskazują na tę samą zmienną.

// Metoda oparta na bitowym XOR

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

// Metoda oparta na arytmetyce

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

Zobaczmy następujący program.

#include <stdio.h>
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;
}

Wyjście :

Po zamianie (& x, & x): x = 0

Zamiana zmiennej może być potrzebna w wielu standardowych algorytmach. Na przykład zobacz tę implementację QuickSort, w której możemy zamienić zmienną ze sobą. Powyższego problemu można uniknąć, stawiając warunek przed zamianą.

#include <stdio.h>
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;
}

Wyjście :

Po zamianie (& x, & x): x = 10

Może nie na temat, ale jeśli wiesz, co zamieniasz pojedynczą zmienną między dwiema różnymi wartościami, możesz być w stanie wykonać logikę tablicową. Za każdym razem, gdy ten wiersz kodu zostanie uruchomiony, zamieni on wartość między 1 a 2.

n = [2, 1][n - 1]

Mógłbyś:

std::tie(x, y) = std::make_pair(y, x);

Lub użyj make_tuple podczas zamiany więcej niż dwóch zmiennych:

std::tie(x, y, z) = std::make_tuple(y, z, x);

Ale nie jestem pewien, czy wewnętrznie std :: tie używa zmiennej tymczasowej, czy nie!

W javascript:

function swapInPlace(obj) {
    obj.x ^= obj.y
    obj.y ^= obj.x
    obj.x ^= obj.y
}

function swap(obj) {
    let temp = obj.x
    obj.x = obj.y
    obj.y = temp
}

Zwróć uwagę na czas wykonania obu opcji.

Po uruchomieniu tego kodu zmierzyłem go.

console.time('swapInPlace')
swapInPlace({x:1, y:2})
console.timeEnd('swapInPlace') // swapInPlace: 0.056884765625ms

console.time('swap')
swap({x:3, y:6})
console.timeEnd('swap')        // swap: 0.01416015625ms

Jak widać (i jak wielu powiedziało), zamiana na miejscu (xor) zajmuje dużo czasu niż inna opcja wykorzystująca zmienną temp.

R brakuje równoczesnego przypisania, jak zaproponował Edsger W. Dijkstra w A Discipline of Programming , 1976, rozdz. 4, s. 29. Pozwoliłoby to na eleganckie rozwiązanie:

a, b    <- b, a         # swap
a, b, c <- c, a, b      # rotate right

a = a + b - (b=a);

To bardzo proste, ale może budzić ostrzeżenie.

jednoliniowe rozwiązanie do zamiany dwóch wartości w języku c.

a=(b=(a=a+b,a-b),a-b);

second_value -= first_value;
first_value +=  second_value;
second_value -= first_value;
second_value *= -1;