Author |
Topic: CS: REGISTER VALUE SWAP (Read 2734 times) |
|
S. Owen
Full Member
Gender: 
Posts: 221
|
 |
CS: REGISTER VALUE SWAP
« on: Jul 27th, 2002, 1:05pm » |
 Quote  Modify
|
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
|
| « Last Edit: Jul 27th, 2002, 1:45pm by S. Owen » |
 IP Logged |
|
|
|
-D-
Guest
|
|
Re: CS: REGISTER VALUE SWAP
« Reply #1 on: Jul 27th, 2002, 1:37pm » |
Quote Modify
 Remove
|
Yup, that's the trick. Except in C, the ^ is the XOR operator.
these CS problems are fun.
-D-
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: CS: REGISTER VALUE SWAP
« Reply #2 on: Jul 27th, 2002, 1:44pm » |
Quote Modify
|
Oh boy, oops - yes, that's right. I'll fix the original post if I can...
|
|
IP Logged |
|
|
|
Misha Kruk
Guest
|
|
Re: CS: REGISTER VALUE SWAP
« Reply #3 on: Aug 1st, 2002, 8:31pm » |
Quote Modify
Remove
|
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.
|
|
IP Logged |
|
|
|
Captain_Segfault
Newbie
Posts: 2
|
|
Re: CS: REGISTER VALUE SWAP
« Reply #4 on: Aug 23rd, 2002, 11:14pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
MessedUpGuy
Guest
|
|
Re: CS: REGISTER VALUE SWAP
« Reply #5 on: May 16th, 2003, 8:51am » |
Quote Modify
Remove
|
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.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: CS: REGISTER VALUE SWAP
« Reply #6 on: May 16th, 2003, 12:57pm » |
Quote Modify
|
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!
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: CS: REGISTER VALUE SWAP
« Reply #7 on: May 21st, 2003, 8:41pm » |
Quote Modify
|
on Aug 1st, 2002, 8:31pm, 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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: CS: REGISTER VALUE SWAP
« Reply #8 on: May 21st, 2003, 10:58pm » |
Quote Modify
|
there are more ways to make it into one statement though..
|
| « Last Edit: May 21st, 2003, 11:14pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: CS: REGISTER VALUE SWAP
« Reply #9 on: May 22nd, 2003, 6:30am » |
Quote Modify
|
on May 21st, 2003, 10:58pm, 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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: CS: REGISTER VALUE SWAP
« Reply #10 on: May 22nd, 2003, 11:12am » |
Quote Modify
|
well, there are && and || and parentheses as well
btw,
a ^= b ^= a ^= b compiles and works fine here with gcc
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: CS: REGISTER VALUE SWAP
« Reply #11 on: May 22nd, 2003, 12:16pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: CS: REGISTER VALUE SWAP
« Reply #12 on: May 22nd, 2003, 2:07pm » |
Quote Modify
|
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..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: CS: REGISTER VALUE SWAP
« Reply #13 on: May 22nd, 2003, 2:58pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: CS: REGISTER VALUE SWAP
« Reply #14 on: May 28th, 2003, 7:58pm » |
Quote Modify
|
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;
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print