# How does the Xor Swap algorithm work?

12

I was studying bitwise operations and came across the Xor Swap algorithm. I understand what it does (it exchanges the value of two variables), but I do not understand how it does it, at the computation and coding level.

Follow 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; */
}
}
``````

asked by anonymous 17.03.2014 / 01:27

6

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

To understand it, just look at the `xor` table and analyze the algorithm step-by-step: For`x=0b1010`and`y=0b0011`:

``x=0b1010xor0b0011;//queresultaemx=0b1001y=0b1001xor0b0011;//usandoonovovalordex,ey=0b1010x=0b1001xor0b1010;//Finalizandocomosvalorestrocados.``

Itshouldbeconsideredthatthispracticeisvalidforoldsystemsand\orwithlittleRAMandtooptimizetheuseoftheregisters.Forcurrentsystems,theuseofatemporaryvariableismoreappropriate(orfunctionsofthesysteminquestion).Asdiscussed here.

17.03.2014 / 01:58
5

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

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

Here's an explanation taken from here :

The key to convincing yourself that this works is to keep track of the original values of x and y. Let A be the original value of x (that is, the value 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 happening.

``````// 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
//   == 0 ^ B            (devido à propriedade z ^ z == 0)
//   == B                (devido À propriedade z ^ 0 == z)
// y == A
``````

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

17.03.2014 / 01:44
3

What the exclusive disjunction (XOR) operation is as follows:

Let's say that we have a variable X and Y. When I make a `XOR` between X and Y, what happens is, when the values are different, it returns a true bit, when they are equal a bit is returned false.

In the XOR swap algorithm , what you do is:

• Create a "negative" of variable X relative to Y;
• Make an XOR of this negative with Y, which returns the value of X;
• Make an XOR between the original value of X (now in Y) with the "negative" of X, which returns the original value of Y.
• If you use the values `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
``````

This is one of exclusive disjunction properties .

17.03.2014 / 01:56