wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> CS: REGISTER VALUE SWAP
        
(Message started by: srowen on Jul 27^th, 2002, 1:05pm)

Title: CS: REGISTER VALUE SWAP
Post by srowen on Jul 27^th, 2002, 1:05pm

This is just a neat trick.
Here's a C example that would be equally effective in assembly (and on registers of any size):

int a, b;
a = a ^ b;
b = a ^ b;
a = a ^ b;
("^" is bitwise exclusive-or)

Note that for any x, x ^ x = 0, and x ^ 0 = x.
After step 1:
a = a ^ b
b = b
After step 2:
a = a ^ b
b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a
After step 3:
a = a ^ b ^ a = b ^ (a ^ a) = b ^ 0 = b
b = a

Title: Re: CS: REGISTER VALUE SWAP
Post by -D- on Jul 27^th, 2002, 1:37pm

Yup, that's the trick. Except in C, the ^ is the XOR operator.
these CS problems are fun.
-D-

Title: Re: CS: REGISTER VALUE SWAP
Post by srowen on Jul 27^th, 2002, 1:44pm

Oh boy, oops - yes, that's right. I'll fix the original post if I can...

Title: Re: CS: REGISTER VALUE SWAP
Post by Misha Kruk on Aug 1^st, 2002, 8:31pm

The same also works for addition:

a = a + b
b = a - b
a = a - b

I also remember swap from above (using XOR) written as a one statement in C. That was scary.

Title: Re: CS: REGISTER VALUE SWAP
Post by Captain_Segfault on Aug 23^rd, 2002, 11:14pm

Although, of course, the addition trick (when I first heard this problem a year or so back, that was the solution I came up with) has the problem of overflow and possibly (?) loss of precision if dealing with floats/doubles; the xor solution doesn't depend at all on the data involved.

Title: Re: CS: REGISTER VALUE SWAP
Post by MessedUpGuy on May 16^th, 2003, 8:51am

Can some one pl. explain me with an example, I do understand the swapping by addition but, not the XOR swapping. I do understand the XOR swap but not able to relate it with an example. :-[ Appreciate it.

Title: Re: CS: REGISTER VALUE SWAP
Post by James Fingas on May 16^th, 2003, 12:57pm

The swap routine computes the value X^Y, which has the interesting property that it turns X into Y and turns Y into X.

So you compute X^Y in register A, use it to convert the register B from Y to X, then use it to convert X in register B to Y, storing the result in register A.

Before
A: 1001 0111 = X
B: 0100 0101 = Y

Step 1: A = A^B
A: 1101 0010 = X^Y
B: 0100 0101 = Y

Step 2: B = A^B
A: 1101 0010 = X^Y
B: 1001 0111 = X

Step 3: A = A^B
A: 0100 0101 = Y
B: 1001 0111 = X

They're swapped now!

Title: Re: CS: REGISTER VALUE SWAP
Post by Leonid Broukhis on May 21^st, 2003, 8:41pm

on 08/01/02 at 20:31:20, Misha Kruk wrote:

I also remember swap from above (using XOR) written as a one statement in C. That was scary.

"a ^= b ^= a ^= b" is illegal in C because there are two assignments to 'a' without intervening sequence points. Despite the fact that the expression tree manipulator is obligated to make sure that the values are computed right-to-left, it is free to pick any of the two requests to update 'a' in the storage.

Title: Re: CS: REGISTER VALUE SWAP
Post by towr on May 21^st, 2003, 10:58pm

there are more ways to make it into one statement though..

Title: Re: CS: REGISTER VALUE SWAP
Post by Leonid Broukhis on May 22^nd, 2003, 6:30am

on 05/21/03 at 22:58:45, towr wrote:

there are more ways to make it into one statement though..

I can only think of using comma operator, which is neither interesting nor scary.

Title: Re: CS: REGISTER VALUE SWAP
Post by towr on May 22^nd, 2003, 11:12am

well, there are && and || and parentheses as well

btw,
a ^= b ^= a ^= b compiles and works fine here with gcc

Title: Re: CS: REGISTER VALUE SWAP
Post by Leonid Broukhis on May 22^nd, 2003, 12:16pm

towr,

I'd like to see what you mean by using &&, || and parentheses.

And the fact that some piece of code with undefined behavior according to the standard works as intended when compiled by a particular compiler does not mean anything.

Title: Re: CS: REGISTER VALUE SWAP
Post by towr on May 22^nd, 2003, 2:07pm

well, it means it works.. But you're right, if it's not defined in the standard it's independable and shouldn't be used.. (it might give variable results in different compilers)

I think you can use
((a ^=b) || 1) && ((b ^=1) || 1) && ((a ^=b) || 1);
to do it all in one statement, and if you know a, b, a^b are all non-zero it can even be compressed to
(a ^=b) && (b ^=a) && (a ^=b) ;

There's no reason I can think of to want to do it here, but it works (costing 2 extra operations).

I like using || as a simple test, for instance if I want to give a variable (initialized at 0) a value only if it is still zero.
so you get
a || (a = value);
which I like slightly better than
if(!a)
a=value;

I think it is also slightly faster, but I might be wrong.. (It hasn't yet mattered enough to make me care to find out)

I also thought you could use a^= (b ^= (a ^=b) ) safely, but to be honest it's been a while. And it wasn't really a focus in the course to begin with..

Title: Re: CS: REGISTER VALUE SWAP
Post by Leonid Broukhis on May 22^nd, 2003, 2:58pm

Well, all these tricks with && and || are effectively comma operators: although potentially scary to the eyes, they are not scary to the mind. :) And, alas, parentheses do not introduce sequence points, so writing a ^= (b ^= (a ^= b)) does not help, it is still undefined.

Title: Re: CS: REGISTER VALUE SWAP
Post by Leonid Broukhis on May 28^th, 2003, 7:58pm

Newsflash!

There is a defect report 222 (being drafted) for the C++ standard that proposes adding

There is a sequence point between assigning the new value to the left operand and yielding the result of the assignment expression.

to the definition of assignment operators. So, in te future, it will be legal to write a ^= b ^= a ^= b;