|
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: 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 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 |