How to swap two numbers without using temp variables or arithmetic operations?

Question

This equation swaps two numbers without a temporary variable, but uses arithmetic operations:

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

How can I do it without arithmetic operations? I was thinking about XOR.

Answer 1

a=a+b;
b=a-b;
a=a-b;

This is simple yet effective....

Answer 2

Why not use the std libs?

std::swap(a,b);

Answer 3

In C this should work:

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

OR a cooler/geekier looking:

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

For more details look into this. XOR is a very powerful operation that has many interesting usages cropping up here and there.

Answer 4

The best way to swap two numbers without using any temporary storage or arithmetic operations is to load both variables into registers, and then use the registers the other way around!

You can't do that directly from C, but the compiler is probably quite capable of working it out for you (at least, if optimisation is enabled) - if you write simple, obvious code, such as that which KennyTM suggested in his comment.

e.g.

void swap_tmp(unsigned int *p)
{
  unsigned int tmp;

  tmp = p[0];
  p[0] = p[1];
  p[1] = tmp;
}

compiled with gcc 4.3.2 with the -O2 optimisation flag gives:

swap_tmp:
        pushl   %ebp               ;  (prologue)
        movl    %esp, %ebp         ;  (prologue)
        movl    8(%ebp), %eax      ; EAX = p
        movl    (%eax), %ecx       ; ECX = p[0]
        movl    4(%eax), %edx      ; EDX = p[1]
        movl    %ecx, 4(%eax)      ; p[1] = ECX
        movl    %edx, (%eax)       ; p[0] = EDX
        popl    %ebp               ;  (epilogue)
        ret                        ;  (epilogue)

Answer 5

I haven't seen this C solution before, but I'm sure someone has thought of it. And perhaps had more posting self-control than I do.

fprintf(fopen("temp.txt", "w"), "%d", a);
a = b;
fscanf(fopen("temp.txt", "r"), "%d", &b);

No extra variables!

It works for me, but depending on the stdio implementation you may have to do something about output buffering.

Answer 6

Using XOR,

void swap(int &a, int &b)
{
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

One liner with XOR,

void swap(int &a, int &b)
{
    a ^= b ^= a ^= b;
}

These methods appear to be clean, because they don't fail for any test-case, but again since (as in method 2) value of variable is modified twice within the same sequence point, it is said to be having undefined behavior declared by ANSI C.

Answer 7

C++11 allows to:

• Swap values:

  std::swap(a, b);
  

• Swap ranges:

  std::swap_ranges(a.begin(), a.end(), b.begin());
  

• Create LValue tuple with tie:

  std::tie(b, a) = std::make_tuple(a, b);
  
  std::tie(c, b, a) = std::make_tuple(a, b, c);
  

Answer 8

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

Answer 9

In addition to the above solutions for a case where if one of the value is out of range for a signed integer, the two variables values can be swapped in this way

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

Answer 10

Multiplication and division can also be used.

 int x = 10, y = 5;

 // Code to swap 'x' and 'y'
 x = x * y;  // x now becomes 50
 y = x / y;  // y becomes 10
 x = x / y;  // x becomes 5