In-place swap, in C

In-place swap, in C

swap content without 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 property1:

(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/sub 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 ALU2 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.

  1. XOR, exclusive or, Wikipedia. 

  2. An arithmetic-logic unit (ALU) is the part of a computer processor (CPU) that carries out arithmetic and logic operations on the operands in computer instruction words. In some processors, the ALU is divided into two units, an arithmetic unit (AU) and a logic unit (LU). Link

Ads by Google


Frank Lin

Hey, there! This is Frank Lin (@flinhong), one of the 1.41 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.


Using Liquid in Jekyll - Live with Demos

Web Notes


Using Liquid in Jekyll - Live with Demos

Liquid is a simple template language that Jekyll uses to process pages for your site. With Liquid you can output complex contents without additional plugins.

Practising closures in JavaScript

JavaScript Notes


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?

Understanding Nginx location directive



Understanding Nginx location directive

Location directives are essential when working with Nginx. They can be located within server blocks or other location blocks. Understanding how location directives are used to process the URI of client request can help make the request handling less unpredictable.


Ads by Google