"How do I swap two variables without using a temporary variable?" is one of the dumber programming questions. Please tell me you don't use this in interviews. There's the sensible way, the way using XOR that everybody "clever" knows, and an even worse implementation that relies upon undefined behavior.
What do these versions actually compile to? Let's use the Compiler Explorer to find out.
Source code, using C++ references:
void swap( int &a, int &b ) {
int t = a;
a = b;
b = t;
}
void farTooCleverSwap( int &a, int &b ) {
a ^= b;
b ^= a;
a ^= b;
}
void stupidSwap( int &a, int &b) {
a = a + b;
b = a - b;
a = a - b;
}
When we compile these under GCC 8.2 with the -O3 flag, we get
As promised, the versions without temporaries use one fewer register. The downside is that they now have less instruction-level parallelism, because each instruction depends on the one immediately before... and the code is larger, too. That edx register is caller-saved, so the calling function can't make use of the fact that it's unused anyway.
OK, you might argue, what about when the function is inlined? Then register pressure might be relevant, and the XORs could be more efficient than spilling a register to memory.
Good luck finding such a case. In fact, both GCC and clang are smart enough to know that all three functions are swaps and eliminate them altogether if possible.
Here's a test function:
int testFunc( int a, int b ) {
printf( "%d %d\n", a, b );
swap( a, b );
printf( "%d %d\n", a, b );
farTooCleverSwap( a, b );
printf( "%d %d\n", a, b );
stupidSwap( a, b );
printf( "%d %d\n", a, b );
}
and the compiler output from clang 6.0.0, with -O3
testFunc(int, int): # testFunc(int, int)
push rbp
push rbx
push rax
mov ebx, esi
mov ebp, edi
mov edi, offset .L.str
xor eax, eax
mov esi, ebp
mov edx, ebx
call printf
mov edi, offset .L.str
xor eax, eax
mov esi, ebx
mov edx, ebp
call printf
mov edi, offset .L.str
xor eax, eax
mov esi, ebp
mov edx, ebx
call printf
mov edi, offset .L.str
xor eax, eax
mov esi, ebx
mov edx, ebp
call printf
.L.str:
.asciz "%d %d\n"
What happened here? The compiler stashed a and b in the ebx and ebp registers. Then it just pulls them out in whatever order are necessary to call printf. All your clever work to avoid introducing an extra register use, and the compiler went with two temporaries! Well, they were probably necessary anyway to save the arguments across the function call, but that just shows how useless trying to optimize away register usage is, when we're starting from C. Let the compiler worry about its register usage.
In fact, an earlier attempt to do a demonstration failed because I used constants to initialize a and b and the compiler just chose to load them new each time:
testFunc(): # @testFunc()
push rax
mov edi, offset .L.str
mov esi, 3
mov edx, 5
xor eax, eax
call printf
mov edi, offset .L.str
mov esi, 5
mov edx, 3
xor eax, eax
call printf
...
Inspiration: https://www.quora.com/Can-I-swap-without-any-extra-variable-in-C/answer/Sergey-Zubkov-1 (and a later answer of his which did more or less the same thing.)
In Python (or other languages with decent tuple support) the matter doesn't arise. Simply do
x,y = y,x
Is there a C++ version of this? std::pair has an inline swap method and of course the function template std::swap is better than writing your own--- it has specializations for all the containers you might think of swapping. Let's look at an example of that, here's a C++ function that swaps two vectors:
and here's the compiled version (color-coded so you can see that the green part is the 'if' statement and the white part is the swap.