-----------------------------------

gitoxa

Wed Nov 26, 2008 10:59 pm


xor

-----------------------------------

I saw this in a guy from my classes code while checking out his sorting algorithms

X := X xor Y
Y := Y xor X
X := Y xor X

How exactly does that swap work?


-----------------------------------

DemonWasp

Wed Nov 26, 2008 11:38 pm


RE:xor

-----------------------------------

Think it through, using X0 = A, Y0 = B

Then you have:
X = A xor B
Y = B xor (A xor B) = A
X = A xor (A xor B) = B
So X = B, Y = A.

It's also worth noting that this is useless unless you're on an EXTREMELY space-restricted machine (integrated computer). Generally it's faster to use the temps method, since a good compiler could do that in registers (whereas this requires a lot of computation relatively speaking).


-----------------------------------

Horus

Thu Nov 27, 2008 12:23 am


RE:xor

-----------------------------------

doesn't using
X := X xor Y
Y := Y xor X
X := Y xor X

save memory? at least like 1 byte of memory lol...

Not sure about speed though...


-----------------------------------

btiffin

Thu Nov 27, 2008 10:00 am


RE:xor

-----------------------------------

Dangerous trick;


int a = 10;
int b = 20;
int *x = &a;
int *y = &b;


The triple xor trick can swap a and b through dereference of x and y, yes, but if y happens to point to the same memory as x? 
int a = 10;
int b = 20;
int *x = &a;
int *y = &a;


The first assigned xor ends up zeroing out the contents of a.

That trick swap will crash the airplane, blow up the rocket, or send the world economy into a credit crunch tailspin.  ;)

Yes, it's cool, but also far too dangerous for common practise.

Cheers


-----------------------------------

Unforgiven

Thu Nov 27, 2008 1:26 pm


Re: RE:xor

-----------------------------------

Dangerous trick;


int a = 10;
int b = 20;
int *x = &a;
int *y = &b;


The triple xor trick can swap a and b through dereference of x and y, yes, but if y happens to point to the same memory as x? 
int a = 10;
int b = 20;
int *x = &a;
int *y = &a;


The first assigned xor ends up zeroing out the contents of a.

That trick swap will crash the airplane, blow up the rocket, or send the world economy into a credit crunch tailspin.  ;)

Yes, it's cool, but also far too dangerous for common practise.

Cheers

I had seen the "triple xor" trick before, but never considered the danger you describe here - thanks.


-----------------------------------

The_Bean

Thu Nov 27, 2008 1:37 pm


Re: xor

-----------------------------------

Convert both numers to binary.
Align them along the right.
Look at each column individauly.
if there both 1, or both 0 then xor produces a 0
if there different 0,1 or 1,0 xor produces 1
Then convert the new binary number to the decimal system you get the answer.


var a : int := 348
var b : int := 65
put intstr (a, 20, 2), " = ", a
put intstr (b, 20, 2), " = ", b
put "difference ", repeat ("-", 15)
put intstr (a xor b, 20, 2), " = ", a xor b


a xor b will make a new number c
c xor b will make a again
a xor b will make b again


-----------------------------------

btiffin

Thu Nov 27, 2008 3:55 pm


Re: RE:xor

-----------------------------------


I had seen the "triple xor" trick before, but never considered the danger you describe here - thanks.

Where XOR comes in very handy is moving graphics across a background.  When you XOR and image over an image you can XOR it back out again, and the original background shows up.   Unless your spaceship happens to move across a duplicate copy of itself, and the whole thing turns black.  ;)

So this swap trick should be considered taboo, unless the coder is willing to take the hit on the test of &x == &y and branch; which when measured against a copy to temp is usually far less efficient anyway.  If you are swapping large areas of ram, using the triple xor in a loop could be more efficient, but you'd have to experiment to find out the minimum number of bytes where the test and branch out performs the extra memory usage.

Cheers