Swapping two variable value without using third variable

Question

One of the very tricky questions asked in an interview.

Swap the values of two variables like a=10 and b=15.

Generally to swap two variables values, we need 3rd variable like:

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

Now the requirement is, swap values of two variables without using 3rd variable.

Answer 1

Using the 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 the test?

The test is to ensure that x and y have different memory locations (rather than different values). This is because (p xor p) = 0 and if both x and y share the same memory location, when one is set to 0, both are set to 0. When both *x and *y are 0, all other xor operations on *x and *y will equal 0 (as they are the same), which means that the function will set both *x and *y set 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 cases, no. The compiler will optimize away the temporary variable and given that swapping is a common procedure it should output the optimum 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

The xor version takes

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

Where as the version with the temporary variable takes:

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

Answer 2

the general form is:

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

however you have to potentially watch out for overflows and also not all operations have an inverse that is well defined for all values that the operation is defined. e.g. * and / work until A or B is 0

xor is particularly pleasing as it is defined for all ints and is its own inverse

Answer 3

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

Answer 4

No-one has suggested using std::swap, yet.

std::swap(a, b);

I don't use any temporary variables and depending on the type of a and b the implementation may have a specalization that doesn't either. The implementation should be written knowing whether a 'trick' is appropriate or not. There's no point in trying to second guess.

More generally, I'd probably want to do something like this, as it would work for class types enabling ADL to find a better overload if possible.

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

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

Answer 5

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

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

Here you have to be careful of overflows/underflows, but otherwise it works just as fine. You might even try this on floats/doubles in the case XOR isn't allowed on those.

Answer 6

Stupid questions deserve appropriate 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

Swapping two numbers using third variable be 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);

Swapping two numbers without using third variable

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

Answer 8

Since the original solution is:

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

You can make it a two liner by using:

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

Then make it a one liner by using:

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

Answer 9

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

Answer 10

Here is one more solution but a single risk.

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 11

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 12

#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 are taking input of two integers from user. Then we are using the bitwise XOR operation to swap them.

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 13

If you change a little the question to ask about 2 assembly registers instead of variables, you can use also the xchg operation as one option, and the stack operation as another one.

Answer 14

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

However, there is also no third variable in the following implementation of swap:

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

that's the correct XOR swap 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 ensure that memory locations are different and also that the actual values are different because A XOR A = 0

Answer 16

You may do....in easy 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 17

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

Answer 18

Let's see a simple c example to swap two numbers without using the third variable.

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

Output:

Before swap a=10 b=20 After swap a=20 b=10

Program 2: Using * and /

Let's see another example to swap two numbers using * and /.

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

Output:

Before swap a=10 b=20 After swap a=20 b=10

Program 3: Making use of bitwise XOR operator:

The bitwise XOR operator can be used to swap two variables. The XOR of two numbers x and y returns a number which has all the bits as 1 wherever bits of x and y differ. For example, XOR of 10 (In Binary 1010) and 5 (In Binary 0101) is 1111 and XOR of 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 Swapping: x = 5, y = 10

Program 4:

No-one has suggested using std::swap, yet.

std::swap(a, b);

I don't use any temporary variables and depending on the type of a and b the implementation may have a specialization that doesn't either. The implementation should be written knowing whether a 'trick' is appropriate or not.

Problems with above methods:

1) The multiplication and division based approach doesn’ work if one of the numbers is 0 as the product becomes 0 irrespective of the other number.

2) Both Arithmetic solutions may cause arithmetic overflow. If x and y are too large, addition and multiplication may go out of integer range.

3) When we use pointers to a variable and make a function swap, all of the above methods fail when both pointers point to the same variable. Let’s take a look what will happen in this case if both are pointing to the same variable.

// Bitwise XOR based method

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

// Arithmetic based method

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

Let us see the following 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;
}

Output:

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

Swapping a variable with itself may be needed in many standard algorithms. For example, see this implementation of QuickSort where we may swap a variable with itself. The above problem can be avoided by putting a condition before the swapping.

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

Output:

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

Answer 19

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

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

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

Answer 20

#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 21

Maybe off topic, but if you know what you are swapping a single variable between two different values, you may be able to do array logic. Each time this line of code is run, it will swap the value between 1 and 2.

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

Answer 22

You could do:

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

Or use make_tuple when swapping more than two variables:

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

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

Answer 23

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
}

Be aware to execution time of both options.

By run 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 said), swap in place (xor) take alot time than the other option using temp variable.

Answer 24

R is missing a concurrent assignment as proposed by Edsger W. Dijkstra in A Discipline of Programming, 1976, ch.4, p.29. This would allow for an elegant solution:

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

Answer 25

How about,If we do with parallel processing with "GO" lang..

var x = 100; var y = 200;

swap1 := func(var i) { x = i } swap2 := func(var y) { y = i } Parallelize(swap1, swap2)

Answer 26

In awk, without needing a temp variable, a temp array, an external function call, substring-ing their values out of one another, XOR operations, or even any math operations of any sort,

this trick works for whether their values are numeric, string, or even arbitrary bytes that aren't UTF8-compliant, nor do the types of the 2 variables even need to match :

      gawk/mawk/nawk '{ 
                       a = (b) \
          substr("", ( b = (a) )^"")
      }'

Even in Unicode-locale, gawk unicode mode could swap the values of arbitrary non-UTF8 bytes without any error messages.

No need to use C or POSIX locale.

Why it works is that in the process of this concatenation, the original value of b has already been placed in some system-internal staging ground, so the sub-sequent assignment of b's value into a does not have any impact into what's being assigned into a

The second half of it is taking a substring of an empty string, so of course nothing comes out, and doesn't affect the first half.

After b = a, I immediately take the zero-th power of it, which always returns a 1 in awk

so the latter portion becomes

  # in awk, string indices start from 1 not 0
  
  substr(EMPTY_STRING, STARTING-POSITION-OF-ONE) 
  

of course nothing comes out of it, which is the desired effect, so the clean original value of b could be assigned into a.

This isn't taking a substring of a's or b's value. It's taking advantage of dynamic typing properties of awk.

A XOR-based approach, which clean, still require 3 operations, plus a safety check against being memory position (for C). And for gnu-awk, its xor() function only works with non-negative numeric inputs.

This one-liner approach circumvents all the common issues with value swapping.

Either a or b, or even both, being an array cell, regardless of single or multi-dimensional, e.g.

arr[ _pos_idx_a_ ]

works exactly the same with this one-liner approach. The only limitation I could think of is that this approach cannot directly swap full contents of an entire array with another array.

I thought of adding a check for a==b to avoid a double assignment, but then realized the internal system resources needed to perform such a check is not worth the minuscule amount of time saved.

Answer 27

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

It's very simple, but it may raise a warning.

Answer 28

single line solution for swapping two values in c language.

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

Answer 29

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