Swapping two integer numbers with no temporary variable

Question

I tried to swap 2 integer numbers without using an additional variable as a traditional swap.

Is it legal in C++? My VC compiler doesn't complain nor gives any warning about it. If so, how can I improve this script?

#include <iostream>
int main()
{
 int a = 20;
 int b = 66;
 // before swapping
 std::cout << a << ' ' << b << '\n';
 // swap
 a ^= b ^= a ^= b;
 // after swapping
 std::cout << a << ' ' << b << '\n';
}

For this code:

int a = 20;
int b = 66;
a ^= b ^= a ^= b;

Assembler output for VC++ 2013:

_b$ = -20 ; size = 4
_a$ = -8 ; size = 4
mov DWORD PTR _a$[ebp], 20 ; 00000014H
mov DWORD PTR _b$[ebp], 66 ; 00000042H
mov eax, DWORD PTR _a$[ebp]
xor eax, DWORD PTR _b$[ebp]
mov DWORD PTR _a$[ebp], eax
mov ecx, DWORD PTR _b$[ebp]
xor ecx, DWORD PTR _a$[ebp]
mov DWORD PTR _b$[ebp], ecx
mov edx, DWORD PTR _a$[ebp]
xor edx, DWORD PTR _b$[ebp]
mov DWORD PTR _a$[ebp], edx

For this code:

int a = 20;
int b = 66;
int t = a;
a = b;
b = t;

Assembler output for VC++ 2013:

_t$ = -32 ; size = 4
_b$ = -20 ; size = 4
_a$ = -8 ; size = 4
mov DWORD PTR _a$[ebp], 20 ; 00000014H
mov DWORD PTR _b$[ebp], 66 ; 00000042H
mov eax, DWORD PTR _a$[ebp]
mov DWORD PTR _t$[ebp], eax
mov eax, DWORD PTR _b$[ebp]
mov DWORD PTR _a$[ebp], eax
mov eax, DWORD PTR _t$[ebp]
mov DWORD PTR _b$[ebp], eax

• CodesInChaos: You can improve it by introducing a temporary variable or using std::swap.
• glampert: Yes, it is legal and valid code. This is a know hack called the XOR swap algorithm.
• Loki Astari: Does not work for all values. Also its silly and non readable NEVER do this. Swapping two value may involve zero instructions in real code which is a much better optimization.
• Clément: @Riking This is incorrect. It will fail if the variables are aliases of one another (i.e. point to the same location), not if the numbers are the same.
• T.C.: This is plainly UB pre-C++11, since you modify a twice between two adjacent sequence points. Though the rules are more complicated, it's UB post-C++11 as well; it's analogous to i += ++i (which is equivalent to i += (i += 1). Clang also issues a warning on your code.

Answer 1

You make assumptions which may not be true. Why do you believe that

int tmp = a;
a = b;
b = tmp; 

actually is compiled down to using an actual variable? It is likely just a register used on the CPU.

Have you inspected it?

Further, why do you assume that:

a ^= b ^= a ^= b;

uses fewer registers than a swap?

Really, what you should do is:

#include <algorithm>
#include <iostream>
int main() {
 int a = 20;
 int b = 66;
 // before swapping
 std::cout << a << ' ' << b << '\n';
 // swap
 std::swap(a,b);
 // after swapping
 std::cout << a << ' ' << b << '\n';
}

Which is also a reminder that having the a ^= b ^= a ^= b; 'naked' in your code is not good practice. Something like that should be embedded in a function, not directly in the main method.

Update - assembler output

For the code:

int a = 20;
int b = 66;
int t = a;
a = b;
b = t;
return a;

you get the assembler output:

movl 20,ドル -12(%rbp)
movl 66,ドル -8(%rbp)
movl -12(%rbp), %eax
movl %eax, -4(%rbp)
movl -8(%rbp), %eax
movl %eax, -12(%rbp)
movl -4(%rbp), %eax
movl %eax, -8(%rbp)
movl -12(%rbp), %eax
popq %rbp

For the code:

int a = 20;
int b = 66;
a ^= b ^= a ^= b;
return a;

you get

movl 20,ドル -8(%rbp)
movl 66,ドル -4(%rbp)
movl -4(%rbp), %eax
xorl %eax, -8(%rbp)
movl -8(%rbp), %eax
xorl %eax, -4(%rbp)
movl -4(%rbp), %eax
xorl %eax, -8(%rbp)
movl -8(%rbp), %eax
popq %rbp

What does that show?

• It shows that both systems run in 12 instructions, including the copy to the stack (%rbp)
• that both systems use the single register %eax
• both systems use the stack as a temp store for the result (the XOR reuses -8 and -4 offsets in the stack, the tmp uses -12(%rbp)

Net result? Both systems use less than 16 bytes of the stack, they both use 1 register in addition to the stack, and they both have the same number of instructions.

I know which one is more readable....

Of course, with the above code, if I add -O2 to the optimization, I get the assembler:

movl 66,ドル %eax
ret

which, as you can imagine, is fast.

• MORTAL: my attention was to find any way to swap 2 int without temp. i have been told that it can be achieved by XOR. i wrote this script base on that it wasn't in my mind the CPU registers that time. but isn't it assembly stuff?
• rolfl: Updated to include assembler output. Note that, for these trivial examples, -O2 optimization wipes out any actual work....
• ratchet freak: for optimize without elimination is could be movl -12(%rbp), %eax; movl -8(%rbp), %ebx; movl %eax, -8(%rbp); movl %ebx, -12(%rbp); (using an extra register and eliminating the stack variable)

Answer 2

This is not valid C++, unless you consider code that allows a conforming compiler to wipe your hard drive, conjure nasal demons and make your cat pregnant to be valid C++.

This statement

a ^= b ^= a ^= b;

invokes undefined behavior. Pre-C++11, it modifies a twice without an intervening sequence point, which causes undefined behavior. Post-C++11, the rules are more complex, but the result is the same. I'm not really inclined to write a full analysis since the subject has been beaten to death multiple times on StackOverflow, but it is essentially identical to the analysis for i += ++i + 1; in this SO answer.

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

This would be valid C++, and the well-known XOR swap trick. However, it generally is not a performance improvement, and decreases the readability of your code.

• Rakete1111: Post-C++17 the statement is equivalent to the long form :)

Answer 3

Assuming that a+b is less than the maximum size of an integer on your system, why not try a simpler solution?

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

For example

Initial
a = 2
b = 4
a = a + b
a = 2 + 4
a = 6
b = a - b
b = 6 - 4
b = 2
a = a - b
a = 6 - 2
a = 4
Final
a = 4
b = 2

• Brythan: This can have problems if a+b is larger than can be held in an int. I.e. it doesn't meet the requirement that you be able to swap without using extra space. The bitwise exclusive-or solution will work for all values of a and b if they are of the same integer type. And I'm not sure that I'd describe addition and subtraction as simpler than bitwise exclusive-or. In computer terms, an add is implemented by multiple bitwise operations, so bitwise exclusive-or is simpler than addition/subtraction. Addition and subtraction are more familiar operations, not simpler ones.
• Jon Story: A good point about a+b needing to be smaller than the maximum size of an integer. Perhaps familiar is a better word, but I was thinking "simpler" in terms of "simpler to understand".
• L. F.: This solution doesn't work either when a and b alias ...

Answer 4

You tried to swap two integers without using a temporary variable. In some languages there is an obvious method to do this, for example in Swift you would write

(x, y) = (y, x)

In C++ your code may or may not have undefined or unspecified behaviour. Once we state "it may have undefined behaviour", that makes the code unacceptable. Even if you arm yourself with a copy of the C++ Standard and prove that your code is correct, it is still unacceptable.

And what for? To avoid a temporary variable? Using a temporary variable, the code is trivial, obvious, easily readable, and will work for any type of variable, like floating point numbers, pointers, structs. Or you could use the standard library.

Answer 5

Here's a slightly different take on this question. Here is an example of the two different swap operations being used in a more-or-less real-world context.

This code:

namespace {
void swapint1(int &a, int &b)
{
 a = a^b;
 b = a^b;
 a = a^b;
}
void swapint2(int &a, int &b)
{
 const int tmp = a;
 a = b;
 b = tmp;
}
}
void bubsort1(int vals[], int size)
{
 for (int i = size - 1; i > 0; --i)
 {
 for (int o = 0; o < i; ++o) {
 if (vals[o] > vals[o + 1]) {
 swapint1(vals[o], vals[o + 1]);
 }
 }
 }
}
void bubsort2(int vals[], int size)
{
 for (int i = size - 1; i > 0; --i)
 {
 for (int o = 0; o < i; ++o) {
 if (vals[o] > vals[o + 1]) {
 swapint2(vals[o], vals[o + 1]);
 }
 }
 }
}

Generates this relevant assembly output with gcc -Ofast:

bubsort1(int*, int):
 sub esi, 1
 test esi, esi
 jle .L1
.L5:
 xor eax, eax
.L4:
 mov ecx, DWORD PTR [rdi+rax*4]
 mov edx, DWORD PTR [rdi+4+rax*4]
 cmp ecx, edx
 jle .L3
 mov DWORD PTR [rdi+4+rax*4], ecx
 mov DWORD PTR [rdi+rax*4], edx
.L3:
 add rax, 1
 cmp esi, eax
 jg .L4
 sub esi, 1
 jne .L5
.L1:
 rep ret
bubsort2(int*, int):
 sub esi, 1
 test esi, esi
 jle .L9
.L13:
 xor eax, eax
.L12:
 mov edx, DWORD PTR [rdi+rax*4]
 mov ecx, DWORD PTR [rdi+4+rax*4]
 cmp edx, ecx
 jle .L11
 mov DWORD PTR [rdi+rax*4], ecx
 mov DWORD PTR [rdi+4+rax*4], edx
.L11:
 add rax, 1
 cmp esi, eax
 jg .L12
 sub esi, 1
 jne .L13
.L9:
 rep ret

Notice how the two different functions generate identical assembly output? Notice which swap is easier for a human being to understand?

Don't use stupid tricks like the xor trick. They're novelties and amusing for all that, but they rarely make a difference in the real world. About the only place where there's even a tiny chance that the xor trick is a good way to swap two integers is on some embedded system with no free registers.

And, your formulation of the xor trick is undefined behavior anyway. The fact that it worked is a pure accident, and while perhaps the fact that it didn't cause your computer to explode is less of an accident, that would also be a permitted result of running it.