In-place swap is a technique, which is used to swap a content of two distinct variables without any temporary storage variable.

XOR swap

The most common implementation of the in-place uses a binary XOR operation. More precisely it is based on its property (A \\oplus B) \\oplus A = B. The whole in-place swap schema for variables a and b is:


\\begin{array}{l|l}
        Operation & Meaning \\\\
        \\hline
        a = a \\oplus b & a = A \\oplus B\\\\
        b = b \\oplus a & b = B \\oplus ( A \\oplus B ) = A \\\\
        a = a \\oplus b & a = ( A \\oplus B ) \\oplus A = B
\\end{array}

Code

/**
 * Inplace swap using the XOR operation
 */
void xorSwap(int *a, int *b) {
    if (a != b) {
        *a ^= *b; // a = A XOR B
        *b ^= *a; // b = B XOR ( A XOR B ) = A 
        *a ^= *b; // a = ( A XOR B ) XOR A = B
    }
}

When using the XOR swap, we have to make sure that we are swapping distinct variables, otherwise the first step of the algorithm could erase the memory, which is being swapped.

Add swap

Another way to implement the in-place swap is to use addition and subtraction. Technically speaking, we can use any reversible binary operation.


\\begin{array}{l|l}
        Operation & Meaning \\\\
        \\hline
        a = a + b & a = A + B\\\\
        b = a - b & b = A + B - B = A \\\\
        a = a - b & a = A + B - A = B 
\\end{array}

Code

/**
 * Inplace swap using addition and subtraction
 */
void addSwap(int *a, int *b) {
    if(a != b){
        *a = *a + *b; // a = A + B
        *b = *a - *b; // b = A + B - B = A
        *a = *a - *b; // a = A + B - A = B  
    }
}

/**
 * Add Swap - swap of two variables without creating a temporary helper variable
 * @param $a
 * @param $b
 * @author Thomas (www.adamjak.net)
 */

function add_swap($a, $b) {
    $a = $a + $b;
    $b = $a - $b;
    $a = $a - $b;
    
}

Add swap can be used only in languages, in which the addition operation will never cause the integer overflow exception, but works in languages, where the numbers are added in a modular fashion (C, C++).

Drawbacks of the in-place swap

The need for the in-place swap is nowadays very limited. The first reason is that present compilers can optimize swap code using temporal variable in many ways, which can be even more effective than in-place swap – thus its usage is superfluous and might even confuse the compiler (and result in an inefficient machine code). Secondly the processors can manage the common approach with the helper variable in a more effective way. The third reason why not to use the in-place swap is that it can be only used to swap variables, whose content has the same length. Last but not least – the algorithm has a very low readability, which can result in a lower maintainability of the code.

Sources

  • XOR swap algorithm. In Wikipedia : the free encyclopedia [online]. St. Petersburg (Florida) : Wikipedia Foundation, 9 March 2009, last modified on 13 December 2010 [2010-12-14]. Available at WWW: <http://en.wikipedia.org/wiki/XOR_swap_algorithm>.







       
 

Place for your banner

Here is the position ready for our customer's banners.