5
\$\begingroup\$

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
\$\endgroup\$
  • 11
    \$\begingroup\$ You can improve it by introducing a temporary variable or using std::swap. \$\endgroup\$ – CodesInChaos Jan 8 '15 at 15:40
  • 3
    \$\begingroup\$ Yes, it is legal and valid code. This is a know hack called the XOR swap algorithm. \$\endgroup\$ – glampert Jan 8 '15 at 17:03
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Martin York Jan 8 '15 at 20:05
  • 3
    \$\begingroup\$ @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. \$\endgroup\$ – Clément Jan 9 '15 at 2:43
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – T.C. Jan 9 '15 at 9:05
21
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – MORTAL Jan 8 '15 at 15:14
  • \$\begingroup\$ Updated to include assembler output. Note that, for these trivial examples, -O2 optimization wipes out any actual work.... \$\endgroup\$ – rolfl Jan 8 '15 at 15:39
  • \$\begingroup\$ 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) \$\endgroup\$ – ratchet freak Jan 8 '15 at 15:55
11
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Post-C++17 the statement is equivalent to the long form :) \$\endgroup\$ – Rakete1111 Aug 14 '18 at 3:12
3
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Brythan Jan 8 '15 at 16:59
  • \$\begingroup\$ 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". \$\endgroup\$ – Jon Story Jan 8 '15 at 17:02
  • \$\begingroup\$ This solution doesn't work either when a and b alias ... \$\endgroup\$ – L. F. Jul 23 at 0:23
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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