xor

[gitoxa]

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

code:

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

How exactly does that swap work?

[DemonWasp]

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]

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]

Dangerous trick;

code:

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?

code:

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]

btiffin @ Thu Nov 27, 2008 10:00 am wrote:

Dangerous trick;

code:

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?

code:

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]

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.

Turing:

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]

Unforgiven @ Thu Nov 27, 2008 1:26 pm wrote:

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