Swap two values

Code
01: void swapXor(int& a, int& b)
02: {
03:   a ^= b;
04:   b ^= a;
05:   a ^= b;
06: }
07:
08: void swapTemp(int& a, int& b)
09: {
10:   int temp = a;
11:   a = b;
12:   b = temp;
13: }
 bits.stephan-brumme.com

Explanation For several years, the XOR swap trick served as a common example of bit twiddling.
Nowadays, its performance advantage is completely gone, nevertheless, the clever idea behind it remains worth looking at.

Let's review XOR:

0 XOR 0 → 0
0 XOR 1 → 1
1 XOR 0 → 1
1 XOR 1 → 0

That means XORing any bit with itself always gives zero: y XOR y → 0.
Moreover, XORing any bit with zero always keeps the bit in its current state: y XOR 0 → 0 XOR y → y.
Now it follows: a XOR b XOR a → b.

Line 3, line 4 and line 5 produce the following equations:

line 3: anew = a XOR b
line 4: bswapped = b XOR anew = b XOR (a XOR b) = a
line 5: aswapped = anew XOR bswapped = (a XOR b) XOR a = b

In the end, aswapped = b and bswapped = a.

The XOR swap algorithm became very popular because it does not need any additional registers.
Modern CPUs perform the more obvious code of swapTemp much slower than the XOR trick, on my computer twice as fast.
If there is no free register available then XOR might be the winner again.

Restrictions • integers only
• with proper aliasing to an integer values, float can be swapped, too
• must not be used with same variable twice, e.g., swapXor(a,a)

These ads
help me to pay
my server bills

Performance • constant time, data independent

+ Intel® Pentium™ D:
• swapXor: ≈ 3.0 cycles per number
• swapTemp: ≈ 1.5 cycles per number

+ Intel® Core™ 2:
• swapXor: ≈ 3.0 cycles per number
• swapTemp: ≈ 2.0 cycles per number

+ Intel® Core™ i7:
• swapXor: ≈ 3.0 cycles per number
• swapTemp: ≈ 2.25 cycles per number
Performance Chart
CPU cycles
(full optimization,
lower values are better)

Assembler Output
swapXor:
01:   xor eax, edx
02:   xor edx, eax
03:   xor eax, edx

swapTemp:
01:   mov ebx, eax
02:   mov eax, edx
03:   mov edx, ebx
 bits.stephan-brumme.com

Download The full source code including a test program is available for download.

References none

More Twiddled Bits
  1. Absolute value of a float
  2. Absolute value of an integer
  3. Approximative inverse of a float
  4. Bit manipulation basics
  5. Bit mask of lowest bit not set
  6. Count bits set in parallel a.k.a. Population Count
  7. Detects zero bytes inside a 32 bit integer
  8. Endianess
  9. Extend bit width
  10. Float inverse square root approximation
  11. Float square root approximation
  12. Is power of two
  13. Minimum / maximum of integers
  14. Parity
  15. Position of lowest bit set
  16. Round up to the next power of two
  17. Sign comparison
  18. Sign of a 32 bit integer
  19. Swap two values
Extra: Javascript bit manipulator

... or go to the index