In-place swap, in C

In-place swap, in C

swap content withou define a temporary variable

In-place swap is just a logic trick used to swap a content of two distinct variables without any temporary storage variable.

XOR swap

The most common way of in-place swap uses XOR operation. It’s based on the XOR property: (AB)A=B(A \oplus B) \oplus A = B. For variables a and b, the XOR swap process is like follows:

  1. a=aba = a \oplus b
  2. b=ba=b(ab)=ab = b \oplus a = b \oplus (a \oplus b) = a
  3. a=ab=(ab)a=ba = a \oplus b = (a \oplus b) \oplus a = b
void xorSwap(int *a, int *b) {
    if (a !=b ) {
        *a = *a ^ *b; // a = a XOR b
        *b = *b ^ *a; // b = b XOR (a XOR b) = a
        *a = *a ^ *b; // a = (a XOR b) XOR a = b
    }
}

When using the XOR swap, we have to make sure the variables are distinct, otherwise the first step of the algorithm could erase the memory, as AA=0A \oplus A = 0.

Add swap

Another way of in-place swap uses simple addition and subtraction:

  1. a=a+ba = a + b
  2. b=ab=(a+b)b=ab = a - b = (a + b) - b = a
  3. a=ab=(a+b)a=ba = a - b = (a + b) - a = b
void addSwap(int *a, int *b) {
    if (a != b) {
        *a = *a + *b; // a = a + b
        *b = *a - *b; // b = a - b = (a + b) - b = a
        *a = *a - *b; // a = a - b = (a + b) - a = b
    }
}

Add swap can be used only in certain languages, in which the addition operation will never cause the integer overflow exception.

Computation details

How does this work on CPU-level?

The computer actually has an implicit “temp” variable that stores intermediate results before writing them back to a register. For example add 3 to a register:

ADD 3 A // add 3 to register A, in machine-language pseudocode

The ALU is actually executes the instruction 3 + A. It takes the inputs and creates a result, which the CPU then stores back into A’s original register. So, we used the ALU as temporary scratch space before we had the final answer. In a similar way, the ALU can return the intermediate result of the XOR in the case of a = a ^ b, then the CPU stores it into a’s original register.

Would you really use this?

This is a cool trick, but don’t write this as an actual swap function, it doesn’t boost the performance and has a very low readability.

林宏

Frank Lin

Hey, there! This is Frank Lin (@flinhong), one of the 1.4 billion 🇨🇳. This 'inDev. Journal' site holds the exploration of my quirky thoughts and random adventures through life. Hope you enjoy reading and perusing my posts.

YOU MAY ALSO LIKE

Using Liquid in Jekyll - Live with Demos

Web Notes

2016.08.20

Using Liquid in Jekyll - Live with Demos

Liquid is a simple templating language that Jekyll uses to process pages on your site. With Liquid you can output an modify variables, have logic statements inside your pages and loop over content.

Practising closures in JavaScript

JavaScript Notes

2018.12.17

Practising closures in JavaScript

JavaScript is a very function-oriented language. As we know, functions are first class objects and can be easily assigned to variables, passed as arguments, returned from another function invocation, or stored into data structures. A function can access variable outside of it. But what happens when an outer variable changes? Does a function get the most recent value or the one that existed when the function was created? Also, what happens when a function invoked in another place - does it get access to the outer variables of the new place?

TOC / 目录

TRENDING