 # In-place swap, in C

swap content without define a temporary variable

2017.12.14

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:

$(A \oplus B) \oplus A = B$

For variables a and b, the XOR swap process is like follows:

1. $a = a \oplus b$
2. $b = b \oplus a = b \oplus (a \oplus b) = a$
3. $a = 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 $A \oplus A = 0$.

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

1. $a = a + b$
2. $b = a - b = (a + b) - b = a$
3. $a = 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. 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

THE END ## 林宏

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.

## YOU MAY ALSO LIKE 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? Tools

2020.09.12

### 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.