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.

Solution 1

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

This is simple yet effective....

Solution 2

Why not use the std libs?

std::swap(a,b);

Solution 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.

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

Solution 5

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.

View more solutions

Comments

[Vishwanath Dalvi]

thanks for XOR .. bt XOR operation is very slower any other method to solve this problem ?

[Oliver Charlesworth]

@mr_eclair: On any typical platform, you're not going to get any faster than KennyTM's suggestion up at the top.

[Martin York]

To make it even less readable you could use the comma operator: a^=b, b^=a, a^=b;

[Sandeepan Nath]

I think the asker wants a solution involving the lower level details here, not just calling a ready made function/library.

[Martin York]

@sandeepan: It is not for me or you to interpret what the question is. We should answer the question stated with the best solution to the problem (if it is not what the OP requires then we will not get a check-mark). But I stand by this being the best solution to the question being asked (even the OP is actually playing with silly interview type questions).

[GManNickG]

@mr_eclair: What do you mean it's slower? The method is to use a damn temporary variable. (Use std::swap.) That's it. What's the point of this question? Do you have an actual problem?

[Sandeepan Nath]

@Martin I disagree, we should interpret and understand well before answering and keep thinking whether we interpreted correctly. This question is not about an optimised/best solution, it is just about a different solution.

[Chuck]

Well, the obvious reason not to use this library function would be that it doesn't work in 2/3 of the languages being asked about.

[Martin York]

@Chunk: 1/3 (it should work on objective-C (well objective-C++))

[Martin York]

@sandeeoan: The thing is I do understand the question and what he wants. But I "gave him what he needs not what he wants" and as such he should become a better developer for it.

[Bo Persson]

Seems like it contains a few arithmetic operators though.

[Martin York]

@Foo Bah: True. But the question is marked C++ so they must expect C++ answers.

[Martin York]

@Foo Bah: Yes. But so what. It is marked C++ so you must expect a C++ answer. No answer will be optimal for multiple languages. XOR swap (is fun as trivial stupid example) but silly for C/C++ and objective C. Sure you can write your own swap_tmp() this is fine for C/objective-C but silly for C++ (as it is already defined with a more optimal version in C++)

[Foo Bah]

@Martin there is no indication in your reply that this is C++ specific. The XOR swap, for example, works everywhere. But there is no equivalent to the c++ swap in C standard library.

[Martin York]

@Foo Bah: The XOR example is a pointless toy example that would never be used in real life (in any language (If you think it is feel free to ask it as a question on SO)). My answer is a practical solution to the question which is the prefect answer for C++. There is no point explicitly stating it is C++ that is obvious from the context.

[Foo Bah]

@Martin it is not obvious from context, unless you knew C and objective C, that the solution only applies to C++. It would help if you explicitly wrote that.

[Martin York]

@Foo Bah: If you don't know C/Objective-C or C++ you are not going to be reading the question!

[Mikhail]

This is also overflow prone, unlike the xor example.

[Tim]

To make this even worse: a ^= b ^= a ^= b (or, even worse, a^=b^(b=a))

[displayName]

@Mikhail: The overflow will take place at a=a+b. Then two underflows will take place at b=a-b and a=a-b resulting in both variables correctly swapping the values.

[Slava]

@mr_eclair actually on hardware level summation is much slower than xor

[Jeff Grigg]

At the hardware level, xor is a simpler operation than add or subtract. There is good reason to think that it could be faster. It was faster on old hardware, but performance may be indistinguishable on modern hardware.

[SMBiggs]

I don't think a variable has to reside on the stack to be considered a temporary variable.

[alx]

@displayName correctly? I wouldn't use that word after 3 consecutive Undefined Behaviours.

[Jean-François Fabre]

not closing the file after writing to it doesn't work on all systems. And it's overkill!