Exchange two variable values ​​without using a third variable

Question

One of the very difficult questions asked in the interview.

Change the values ​​of two variables, such as a=10 and b=15 .

Usually, to replace two values ​​of variables, we need a third variable of the type:

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

Now the requirement is the swap values ​​of two variables without using a third variable.

Answer 1

Using xor swap algorithm

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

Why a test?

The test should ensure that x and y have different memory locations (and not different values). This is because (p xor p) = 0 , and if both x and y have the same memory location when set to 0, both values ​​are 0. When both * x and * y are 0, all other xor operations on * x and * y will be equal to 0 (just as they coincide), which means that the function will set both * x and * y to 0.

If they have the same values ​​but not the same memory location, everything works as expected

 *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 

Should this be used?

In general, no. The compiler optimizes the temporary variable and, considering that exchange is a general procedure, it should output the optimal machine code for your platform.

Take, for example, this quick test program written in 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; } 

Compiled using:

 gcc -Os main.c -o swap 

Xor version required

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

Where, as a version with a temporary variable takes:

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

Answer 2

general form:

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

however, you need to potentially monitor overflows, and not all operations have the opposite, which is well defined for all values ​​defined for the operation. e.g. * and / work until A or B is 0

xor is especially nice because it is specific to all ints and is its own inverse

Answer 3

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

Answer 4

No one suggested using std::swap .

 std::swap(a, b); 

I do not use temporary variables, and depending on the types a and b implementation may also have some specification. The implementation must be written, knowing whether the "trick" is suitable or not. There is no point trying to guess.

More generally, I would probably want to do something like this, as this will work for class types that allow ADLs to find the best overload, if possible.

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

Of course, the interviewer's reaction to this answer can say a lot about the vacancy.

Answer 5

As already noted in manu, the XOR algorithm is a popular one that works for all integer values ​​(including pointers, with some luck and casting). For completeness, I would like to mention another less powerful algorithm with addition / subtraction:

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

You should be careful with overflows / threads here, but otherwise it works just as well. You can even try this on float / doubles in case XOR is not allowed on them.

Answer 6

Silly questions deserve answers:

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

The only good use of the register keyword.

Answer 7

Have you seen the XOR exchange algorithm ?

Answer 8

 #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=ab; a=ab; cout<<"\n\na="<<a<<"\nb="<<b; getch(); } 

Answer 9

Here is another solution, but one risk.

the code:

 #include <iostream> #include <conio.h> void main() { int a =10 , b =45; *(&a+1 ) = a; a =b; b =*(&a +1); } 

any value at location a + 1 will be overridden.

Answer 10

Since the original solution:

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

You can do this with two liners using:

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

Then make it one liner using:

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

Answer 11

If you slightly change the question of two assembly registers instead of variables, you can also use the xchg operation as one parameter, and the stack operation as another.

Answer 12

Consider a=10 , b=15 :

Using addition and subtraction

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

Using division and multiplication

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

Answer 13

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

Update: In this we take the input of two integers from the user. Then we use the bitwise XOR operation to replace them.

Let's say we have two integers a=4 and b=9 , and then:

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

Answer 14

Of course, the C ++ answer should be std::swap .

However, the following swap implementation also lacks a third variable:

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

Or, as a one-liner:

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

Answer 15

Swap two numbers using the third variable, like this:

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

Exchange two numbers without using a third variable

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

Answer 16

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

Answer 17

what's the correct XOR replacement algorithm

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

you have to make sure that the memory locations are different, and also that the actual values ​​are different, since A XOR A = 0

Answer 18

You can do ... in a simple way ... within one line Logic

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

or

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

Answer 19

 public void swapnumber(int a,int b){ a = a+b-(b=a); System.out.println("a = "+a +" b= "+b); } 

Answer 20

Let's look at a simple example c to replace two numbers without using a third variable.

program 1:

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

Output:

Before replacing a = 10 b = 20 After replacing a = 20 b = 10

Program 2: Using * and /

Let's see another example to exchange two numbers with * and /.

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

Output:

Before replacing a = 10 b = 20 After replacing a = 20 b = 10

Program 3: Using the XOR Bitwise Operator:

The bitwise XOR operator can be used to replace two variables. XOR of two numbers x and y returns a number that has all bits as 1, where bits x and y are different. For example, XOR 10 (In Binary 1010) and 5 (In Binary 0101) are 1111, and XOR is 7 (0111) and 5 (0101) is (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; 

Output:

After replacing: x = 5, y = 10

Program 4:

No one suggested using std :: swap.

 std::swap(a, b); 

I do not use any temporary variables, and depending on the types a and b, the implementation may have a specialization that also does not. The implementation must be written, knowing whether the "trick" is suitable or not.

Problems with the above methods:

1) The approach based on multiplication and division does not work if one of the numbers is 0, when the product becomes 0 regardless of the other number.

2) Both arithmetic solutions can cause arithmetic overflow. If x and y are too large, addition and multiplication may fall outside the integer range.

3) When we use pointers to a variable and execute the swap function, all of the above methods fail when both pointers point to the same variable. Let's see what happens in this case, if both point to the same variable.

// XOR-based bit method

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

// Arithmetic method

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

Let's look at the next 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; } 

Exit

After replacing (& x, & x): x = 0

Switching a variable with itself may be required in many standard algorithms. For example, see This QuickSort implementation, where we can change the variable with ourselves. The above problem can be avoided by setting a condition before the replacement.

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

Exit

After replacing (& x, & x): x = 10

Answer 21

The best answer would be to use XOR, and use it on one line would be cool.

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

x, y are variables, and the comma between them introduces the points of the sequence, so it does not become dependent on the compiler. Hurrah!

Answer 22

Maybe off topic, but if you know that you are changing one variable between two different values, you can make the logic of the array. Each time this line of code is run, it changes the value between 1 and 2.

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

Answer 23

You could do:

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

Or use make_tuple when replacing more than two variables:

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

But I'm not sure if std :: tie internally uses a temporary variable or not!

Answer 24

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

Know the runtime: by running this code, I measured it.

 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 

As you can see, and as many have said, in-place replacement (xor) takes longer than another option with a temporary variable.

Answer 25

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

It is very simple, but may cause a warning.

Answer 26

single-line solution for replacing two values ​​in c.

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

Answer 27

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