Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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
share|improve this question
9  
You can improve it by introducing a temporary variable or using std::swap. –  CodesInChaos Jan 8 at 15:40
3  
Yes, it is legal and valid code. This is a know hack called the XOR swap algorithm. –  glampert Jan 8 at 17:03
3  
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. –  Loki Astari Jan 8 at 20:05
1  
If this was a good idea the C++ compiler would automatically do it. It's not too hard to pattern-match on swapping two variables. –  usr Jan 8 at 21:54
3  
@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. –  Clément Jan 9 at 2:43

4 Answers 4

up vote 20 down vote accepted

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.

share|improve this answer
    
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? –  MORTAL Jan 8 at 15:14
    
Updated to include assembler output. Note that, for these trivial examples, -O2 optimization wipes out any actual work.... –  rolfl Jan 8 at 15:39
    
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) –  ratchet freak Jan 8 at 15:55

This is valid C++. You can also write

a ^= b ^= a ^= b;

as

a ^= (b ^= (a ^= b));

or

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

In C++, an assignment always returns the result. So in general,

i = 1
use(i);

can always be replaced with

use(i = 1);

where use is some expression using i singly (i.e. not something like i*i).

A reason not to write it that way though is that it is somewhat harder to read. It's usually easier to read multiple statements rather than try to crowd everything into one expression. It's very rare these days for source code size to matter, and it is generally better to optimize for ease of reading rather than speed of writing. In practice, you will find that you read code more often than you write it.

Note: as rolfl noted, this trivial application is unnecessary. I'm ignoring that and assuming that you have a reason to implement it this way. The only question that I'm addressing is how it should be written.

The fastest way to do this would be

int main()
{
    int a = 20;
    int b = 66;

    // before swapping
    std::cout << a  << ' ' << b  << '\n';

    // after swapping
    std::cout << b << ' ' << a << '\n';
}

Of course, that relies on the fact that you never use the variables again. However, a good compiler might well compile the std::swap version into the same code as that. It's unlikely that even a good compiler will compile out a ^= b ^= a ^= b; even though in this example it is just as unnecessary.

share|improve this answer

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.

share|improve this answer

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
share|improve this answer
2  
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. –  Brythan Jan 8 at 16:59
    
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". –  Jon Story Jan 8 at 17:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.