How does the Xor Swap algorithm work?

Question

How does the Xor Swap algorithm work?

Navigation

#1 by (6 votes)
#2 by (5 votes)
#3 by (3 votes)

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

c algoritmo

asked by anonymous 17.03.2014 / 01:27

3 answers

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
 //   == ( 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 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

All keys work as enter Is it better to parameterize your PreparedStatement even if the value is fixed?

score 6 · Accepted Answer

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:

Forx=0b1010andy=0b0011:

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

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