Swapping two variables without using a temporary in C or C++

Author: Paul J Herring
Original source: This article is obtained from the files section of c-prog Yahoo group. The orignial (updated) version can be found in the files section of c-prog at: http://tech.groups.yahoo.com/group/c-prog/files/html/swapnotemp.html

Nearly everyone has their opinion on the 'best' way of swapping two variables (of any type) without using a third. Sadly, some of these tricks, while they may work in some languages, will not necessarily work in either C or C++.

Assembler XOR 'trick'
Assembler arithmetic 'trick'
Attempting to swap directly using XOR in C and C++
Attempting to swap using XOR by reference in C and C++
Attempting to swap using use arithmetic in C and C++

Assembler XOR 'trick'

Historically swapping values without a temporary was useful in assembler to save on registers/memory, and someone came up with a way of using XOR do this. Essentially, all you need to do is:

a = a xor b
b = a xor b
a = a xor b

As an example:

let a = 0x55   (0b01010101)
let b = 0xAA   (ob10101010)

a = a xor b    a == 0x55    0b01010101
               b == 0xaa    0b10101010
           xor(a) = 0xff    0b11111111 

b = a xor b    a == 0x55    0b11111111
               b == 0xaa    0b10101010
           xor(b) = 0xff    0b01010101

a = a xor b    a == 0x55    0b11111111
               b == 0xaa    0b01010101
           xor(a) = 0xff    0b10101010

Since assembler tends to accees memory on a byte by byte or word by word basis without any regard as to what those values represent or how they should be interpreted, this will always work, no matter what values a and b have, nor how 'wide' they are (bytes, words or doublewords).
There is a 'cute' way of writing this:- if you assume that the ^ operator means 'bitwise xor' (as it does in C and C++) and that
x ^= y
is equivilant to
x = x ^ y
then the above series of expressions could be written as:

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

And if you're allowed to chain expressions, this can even be made even 'cuter' by doing:
a ^= b ^= a ^= b
Not exactly self documenting code as you can see. Also note that this last is not allowed in C or C++.

Assembler arithmetic 'trick'

Another similar method relies on addition and subtraction:


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

Similar example (presuming twos complement):

let a = 0x55   (0b01010101)
let b = 0xAA   (ob10101010)

a = a + b      a == 0x55    0b01010101
               b == 0xaa    0b10101010
           a+b(a) = 0xff    0b11111111 (with a carry)

b = a - b      a == 0xff    0b11111111
              -b == 0x56    0b01010110
          a+-b(b) = 0x55    0b01010101 (with carry)
         
a = a - b      a == 0xff    0b11111111
              -b == 0xab    0b10101011
          a+-b(a) = 0x55    0b10101010 (with carry)

Again - it doesn't matter what these numbers represent, or how they should be interpreted since they are just 'raw bits' from the point of view of assembler.

Attempting to swap directly using XOR in C and C++

Unfortunately, some people see the above two tricks on the web without taking note of what language it applies to. While the two above tricks can be used in C and C++, there are reasons on why they cannot be used in all circumstances.

The XOR trick can only be used in C and C++ if the the variable is of type int. (This includes long, char and any type that is a typedef of these.)
This means that if any of the variables are of type float, a pointer to anything or anything that isn't an int, attempting to use an XOR in an expression results in undefined behaviour (i.e anything can happen, including what you think to be the right answer, however it isn't guaranteed.) This is because of the following section in The Standard:

ISOIEC9899-1999

6.5.11 Bitwise exclusive OR operator
Syntax
1: exclusive-OR-expression:
AND-expression
exclusive-OR-expression ^ AND-expression
Constraints
2: Each of the operands shall have integer type.
Semantics
3: The usual arithmetic conversions are performed on the operands.
4: The result of the ^ operator is the bitwise exclusive OR of the operands (that is, each bit in the result is set if and only if exactly one of the corresponding bits in the converted operands is set).
I've highlighted the relevant points in red. Note that floats are converted into integers, then XOR'd; this clearly will not do what you want. Pointers likewise are converted into ints, and this is implementation defined (i.e. what happens on your compiler is fixed, but may be different from the result of a different compiler):

ISOIEC9899-1999

6.3.2.3 Pointers
1 A pointer to void may be converted to or from a pointer to any incomplete or object type. A pointer to any incomplete or object type may be converted to a pointer to void and back again; the result shall compare equal to the original pointer.
2 For any qualifier q, a pointer to a non-q-qualified type may be converted to a pointer to the q-qualified version of the type; the values stored in the original and converted pointers shall compare equal.
3 An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant.55) If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function.
4 Conversion of a null pointer to another pointer type yields a null pointer of that type. Any two null pointers shall compare equal.
5 An integer may be converted to any pointer type. Except as previously specified, the result is implementation-defined, might not be correctly aligned, might not point to an entity of the referenced type, and might be a trap representation.

Attempting to swap using XOR by reference in C and C++

Another method using XOR that is seen in the context of C and C++ is when you pass by reference to a function called swap (this is written using pointers in C, but the same principle holds for C++ and the reference operator). Note that the caveats mentioned above hold - namely that the parameters to this function must be of integer type:


void swap(int* a, int *b){
  *a = *a ^ *b;
  *b = *a ^ *b;
  *a = *a ^ *b;
}

While this will work for two different variables, it breaks when you pass in the same variable twice:


int x = 10;
swap(&x, &x);

The first statement translates to:
x = 10 ^ 10;
which equals zero (any number XOR'd with itself returns zero.) This results in the 2nd and 3rd expression also resulting in zero, rendering the whole function useless. Checking for 'the same reference' negates the whole point of using this idiom, and still doesn't take into account 'overlaps' of the two variables.

Attempting to swap using use arithmetic in C and C++

Arithmetic fares no better, although in some circumstances it can be used in more places than the XOR tick above, namely if the types of the two variables are pointers, then a valid swap may be made, and floats are also amenable to this, but see below.
With (signed) integers, then the following algorithm fails under certain conditions. Here is the code again:


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

When the sum of a and b exceeds MAX_INT (or whatever the maximum for the datatype is), the behaviour is undefined:

ISOIEC9899-1999

3.4.3 1 undefined behavior
behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements
2 NOTE Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).
3 EXAMPLE An example of undefined behavior is the behavior on integer overflow.

A similar problem could arise if using pointers.

A different problem occurs when using floating point data types. If one of the numbers is very large and the other is very small, then the small number will become zero because generally, there is no way to store the result of the addition in the first step:

double a = 1e-100;
double b = 1e+100;

The first line (a+b) results in the number: 1000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000.00000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000001 Which ANSI/IEEE 754-1985 (IEEE Standard for Binary Floating-Point Arithmetic) cannot store in 32 bits, so it truncates it back to 1e100

Summary

In C and C++ there is no fool-proof way of easily swapping two variables without a temporary. Indeed, attempting to is more than likely to produce more inefficient code (which is the usual reason for wanting to do this):

From: Dik T. Winter
Subject: Re: swap two numbers
Newsgroups: comp.lang.c
Date: 2004-10-16 17:30:17 PST

In article  "Malcolm"  writes:
 > "Nils O. Selåsdal"
 > > What if a+b overflows ?
 > > And is there any point to do "smart" tricks like this ? If one
 > > needs to swap variables, do it the right way. If there is
 > > anything to gain, trust your compiler to optimize it.
 > >

 > You're basically right, but not about trusting the compiler. Let's say that
 > the XOR hack saves a cycle over use of a temporary, due to the architecture
 > of the instruction set. Seeing that assignment to a temporary is only for
 > the purposes of swapping is the sort of thing compilers tend not to be good
 > at,

Compilers tend to be very good at just that.  Using the tmp variable
will much more likely get the optimal sequence:
   load a to r1
   load b to r2
   store r2 to a
   store r1 to b
on most machines.  Using the xor trick (or whatever) may very well lead
to:
   load a to r1
   load b to r2
   set r1 to r1 ^ r2
   set r2 to r2 ^ r1
   set r1 to r1 ^ r2
   store r1 to a
   store r2 to b
on the same machines.