How does the Xor Swap algorithm work?

Question

I was studying bit-by-bit operations and came across the Xor Swap algorithm. I understand what it does (exchange the value of two variables), but I don’t understand how it does it, at the level of calculation and coding.

Follows the algorithm in C:

void xorSwap( int *x, int *y ) {
        if ( x != y ) {
                *x ^= *y;
                *y ^= *x;
                *x ^= *y;

                /* Versão compacta: *x ^= *y ^= *x ^= *y; */
        }   
}

Answer 1

First, let’s remember some properties of XOR (exclusive-OR):

• A A = 0
• neutral element: A 0 = A
• commutative: A B = B A
• associative: (A B) C = A (B C)

The following is a retracted explanation from here:

The key to convince yourself that this works is to track the original values of x and y. Let A be the original value of x (that is, the value that x has before executing these three lines of code). Similarly, let B be the original value of y.

We can comment on each line of code to see what’s going on.

// x == A, y == B
x = x ^ y ;  
 // x == A ^ B, y == B
y = x ^ y ;  
 // x == A ^ B
 // y == (A ^ B) ^ B == A ^ (B ^ B)  (por associatividade)
 //   == A ^ 0  (devido à propriedade z ^ z == 0)
 //   == A      (devido à propriedade z ^ 0 == z)
x = x ^ y ;
 // x == ( A ^ B ) ^ A
 //   == ( A ^ A ) ^ B  (por associatividade/comutatividade)
 //   == 0 ^ B            (devido à propriedade z ^ z == 0)
 //   == B                (devido À propriedade z ^ 0 == z)
 // y == A

After the second statement executed, y = A. After the third statement, x = B.

Answer 2

It is used to exchange two values without the need for a temporary variable, using operations xor.

To understand it is only to look at the table of xor and analyze step-by-step the algorithm:

To x = 0b1010 and y = 0b0011:

x = 0b1010 xor 0b0011; // que resulta em x = 0b1001
y = 0b1001 xor 0b0011; // usando o novo valor de x, e y = 0b1010
x = 0b1001 xor 0b1010; // Finalizando com os valores trocados.

---

It should be considered that this practice is valid for old and low RAM systems and to optimize the use of registers. For current systems, the use of a temporary variable is more appropriate (or proper functions of the system in question). How is discussed here.

Answer 3

What the exclusive disjunction operation (XOR) does is this:

Let’s say we have a variable X and Y. When I do a XOR between X and Y, what happens is, when the values are different, returns a true bit, when they are equal returns a false bit.

In the XOR swap algorithm, what is done is:

1. Create a "negative" of variable X relative to Y;
2. Make a XOR of that negative with Y, which returns the value of X;
3. Make a XOR between the original value of X (now in Y) with the "negative" of X, which returns the original value of Y.

If the values are used as an example x = 12 and y = 10 (as in the link example), we will have:

x = 1100 / y = 1010
x = x XOR y
x = 0110 / y = 1010
y = y XOR x
x = 0110 / y = 1100
x = x XOR y
x = 1010 / y = 1100

Basically, this is one of the exclusive disjunction properties.