
Swap two values 

Code  
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: a_{new} = a XOR b line 4: b_{swapped} = b XOR a_{new} = b XOR (a XOR b) = a line 5: a_{swapped} = a_{new} XOR b_{swapped} = (a XOR b) XOR a = b In the end, a_{swapped} = b and b_{swapped} = 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 CPU cycles (full optimization, lower values are better) 
Assembler Output  
Download  The full source code including a test program is available for download. 
References 
none 
More Twiddled Bits 
... or go to the index 