Swapping content of 2 vars 1

[bitplayer]

Not sure whether to put this in the C++ forum or here. But I seem to remember one time being very impressed when I read somewhere of a slick way to swap 2 variables without the use of a temporary var. I wanted to use this in a bubble sort I am writing for a class in Java. Here is the dumb obvious way you swap 2 vars:
temp = n1;
n1 = n2;
n2 = temp;

Now, I looked this idea up on the internet and found this

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

This does switch 2 vars without an intermediary, which is cool, but I remember something really short and sweet. I can do this in one line (definitely want it all on one line), but it looks pretty gross:

a=(a-(b=(a=a+b)-b));

or as I discovered I needed to do because of order of operations:

a = -((b=(a=a+b)-b)-a);

and here's how it looks in my bubble sort:

n=-((n[i+1]=(n+=n[i+1])-n[i+1])-n);

Like I said, pretty gross (and just try to figure it out!). So I wonder if anyone knows what I am thinking of. By the way, here's something else I came up with, but it still doesn't excite me:

n = n[i+1] + (n[i+1]=n)*0;

It seems to work, but its kind of scary since once again it is very dependent on in what order the statement is evaluated.

 

[prosper]

It is amazing that you can swap without using a temporary variable.
But It seems to me that swapping those variables is faster than doing those calcuation.

I wonder if there will be loss in precision when doing those calcuation.

 

[bitplayer]

Yes, you are right that doing it this way is probably going to be more processor-intensive and since this is a sorting routine, you certainly don't want to have to do more processing than necessary. But it does point out a definite shortcoming of Java, doesn't it. I mean, I was thinking what might be just as nice would be a separate swap() function (or as it is called in Java, method). But how do you do that in Java? In C++, if I want to write a function to swap 2 vars I do this

void Swap(int* a, int* b) { int t = *a; *a = *b; *b = t };

and to call it, you just do Swap(&n, &m); to send the addresses of the two variables you want to swap. You can also use references:

void Swap(int& a, int& b) ( int t = a; a = b; b = t );

with this you don't even have to pass the addresses, you just call it like this:

Swap(n, m);

and that will swap the contents of the 2 variables. But how do you do something like this in Java? Java is only pass-by-value. I am just learning Java, but from what I know there is no way to have a general swap() routine in Java, where you can pass it 2 variables and it can swap them. Ah well, I guess I'll just have to use the clunky method, sigh.

 

[stefanwagner]

a) You can swap variables when they are in an array or in a list, which is mostly the case anyway, when you need a swap.

b) If you use bubblesort, your opportunity to think about performance is already gone.

c) A one-liner which is readable, but only works for builtin numerics:

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

d) With integers, you might get an over- or underrun, but no precision problems.

e) In c++ you may swap a piece of strawberrycake with an int - maybe that's not the greateest advantage. Google for 'exploit'.




don't visit my homepage:

http://home.arcor.de/hirnstrom/minis/index.html

 

[Diancecht]

So you are concerned about performance and you want to add a swap method to the stack. No matter what you try, internally the VM will do the same as you do in C++, use a temp pointer to swap references.

I like that funny wat of swapping integers, but I wouldn't like to be the one to maintain that piece of code.

Cheers,
Dian

 

[stevexff]

From my assembler days, you can swap two variables of any kind provided they have the same length (memory footprint)

A = B'10000001'
B = B'10101010'

A xor B

A = B'00101011'
B = B'10101010'

B xor A

A = B'00101011'
B = B'10000001'

A xor B

A = B'10101010'
B = B'10000001'

Thank you, I'll be here all week...

But why you'd bother to do this in a high level language is beyond me. Do it with a temporary variable, and run it through a profiler. If you've actually got a problem, fix it. But as stefanwagner says, if you are using a bubble sort, you have a performance problem already. There are other much better algorithms (like quicksort) you could use before worrying about the overhead of a temporary variable...

Steve

[small]"Every program can be reduced by one instruction, and every program has at least one bug. Therefore, any program can be reduced to one instruction which doesn't work." (Object:erlDesignPatterns)[/small]

 

[snitin78]

I think you should probably have a look at the java.util.Collections class, specifically the sort() and swap() methods provided by this class.

Nitin

 

[bitplayer]

stevexff - Hahaha! Just yesterday morning, before I had read your post, I had kept thinking, I remember from way back that if you Xor 2 variables, the result is a variable that, if you Xor that variable with either of the original 2 variables, it results in the other original variable. So for example, if x = a Xor b, then x Xor a == b and x Xor b == a. But I thought, what are the chances that Java actually has a bit-level operator like Xor. For my class I have a 987 page text book that never mentions such an operator. But, my sister had given me this book called "Teach Yourself JAVA" and in there I discovered there IS an Xor operator in Java! And I was trying to think, would Xor be able to do what the + and - does in the formula I already posted. A=A+B; B=A-B; A=A-B; and I finally got it! Yes, an Xor can do just the same thing, you can substitute the + and - with Xor and the same thing will happen. So in Java, you can use a=a^b; b=a^b; a=a^b; to swap 2 variables, so I was wondering if there was some way I could take advantage of this. Well one very nice thing is, unlike with -, Xor is commutative, so for the 2nd step, instead of b=a^b; I can use b=b^a; Well, this line of thinking eventually lead to the Holy Grail as you can see below:

[small][COLOR=green]
                    // a=a+b
                    // b=a-b
                    // a=a-b
                    // a=a+b;b=a-b;a=a+b;
                    // a=(a-(b=(a=a+b)-b));
//                    n[i]=-((n[i+1]=(n[i]+=n[i+1])-n[i+1])-n[i]);
                    // a+=b;b-=b-a;a-=b;
                    [COLOR=blue]int[/color][COLOR=black] a=n[i], b=n[i+1];[/color]
                    // a+=b;b=a-b;a-=b;  // this works
                    // a=a^b  // can also use Xor operator
                    // b=b^a  // nice thing about Xor is, unlike minus, it is commutative
                    // a=a^b
                    // a^=(b^=(a^=b));
//                    a^=b;b^=a;a^=b;  // THIS WORKS!!
                //    b^=(a^=b);  // THESE WORK
                //    a^=b;       // THESE WORK
//                    a=(b^=(a^=b))^a;  // this works, but for some reason this a^=(b^=(a^=b)); does not (actually, I understand now why)
                    //a=(b^=a^=b)^a;  // THIS WORKS!!!
                    //a=a^(b^=a^=b);  // how is it possible that this does not work, but the above does?? (I understand now)
                 //   a^=b^=a^=b;  // THE HOLY GRAIL!!! BUT FOR SOME REASON THE *&^%$#@! JAVA VIRTUAL MACHINE FAILS TO EXECUTE IT CORRECTLY!!
                                   // Later: SORRY, I APOLOGIZE for thinking it wasn't working!
                    [COLOR=black]a^=b^(b^=a^=b);[/color]  // This works, but doesn't look as svelte as above, sigh.
                                     // Guess I'll have to go back to a=(b^=a^=b)^a; as the best I can come up with.
                    [COLOR=black]a=(b^=a^=b)^a;[/color]   // It has a nice symetry with a b a b a, but wish I could have eliminated the parens...
//                  b^=a^=b;a^=b;  // but this has the smallest number of characters, and no parens

                    [COLOR=blue]int[/color] [COLOR=black]s=n[i], w=n[i+1], p=w;[/color]  // experimental version
                    [COLOR=black]s=(w^=a^=p)^a;[/color]  // this actually works! if only Java allowed references to array elements
                    [COLOR=black]n[i]=s; n[i+1]=w;[/color]  // how could any programmer NOT know what the above line was doing! :)

                //    n[i]=(n[i+1]^=n[i]^=n[i+1])^n[i];
                    //a^=(b^=(a^=b));
//                    n[i]=a; n[i+1]=b;
            //showNumberArray("List during=", number);
//                    n[i] = n[i+1] + (n[i+1]=n[i])*0;
                    // tmp = number[i];  // bleagh!!
                    // number[i] = number[i+1];  // and bleagh!!
                    // number[i+1] = tmp;  // bleagh again!!
[/color][/small]

So which would you rather see in your code, this:
tmp = a;
a = b;
b = tmp;
or this:
a=(b^=a^=b)^a;

Now, as far as your comment

But why you'd bother to do this in a high level language is beyond me. Do it with a temporary variable, and run it through a profiler. If you've actually got a problem, fix it. But as stefanwagner says, if you are using a bubble sort, you have a performance problem already. There are other much better algorithms (like quicksort) you could use before worrying about the overhead of a temporary variable...

This kind of remark I just don't get! ITS FOR LOUSY CLASS, FOR GOD'S SAKE! THE ASSIGNMENT WAS TO USE A BUBBLE SORT!! OK?? It doesn't matter one twit if I do it or not, or how I do it (and its too late now, I already had to submit my assignment). Why can't I have some fun in what I do? You must be a really dull person or something. Don't you and the rest of the responders here know what programming is all about? Its about wasting your time! All programming is a way to waste your time. I want you to write on the blackboard 100 times, "Doing programming is a complete waste of time!!!" (or you can use a for loop if its too much trouble). Every programmer should have put on their tombstone when they die "I was a programmer and my life was a complete waste of time" (on mine I'll add ", but I managed to have some fun with it, despite all the what's-his-nameses"). Ok, just so we got that all straightened out.

Now, as for snitin78's comment. Yes, at one point I was thinking, maybe there is some swap() function provided by the extensive Java class library they supply, and I actually searched for one. And I now see, thanks to you, that there is indeed one. But I just can't see creating an instance of one of these high-level class objects an ArrayList, putting my 2 variables that need to be swapped into this little 2 element ArrayList so I can call an ArrayList method swap(), and then extracting them from the ArrayList. Although your probably gonna say, no, you want to initially set up the ArrayList as the thing you are gonna sort. Well, yea, I could do that, but, but, this programming assignment is for sorting a regular array, not an ArrayList, which has a sort function all programmed into it already, which if used would obviate the need to use a swap anyway. What's the fun of programming and coming up with new ways to program, if everything is already done for you, like it seems Java is trying to do (and all the other programming languages are too, I think).

Now, there is just one other thing I wanted to say. Even though I came close to discovering the Holy Grail of swapping 2 variables, I still think it is really not that good. I think Java should really come up with a BRAND NEW OPERATOR just for swapping 2 variables. Just think, if it did that, it would blow away all other computer programming languages! Just think, how many other programming languages have a swap operator. Doesn't the Sun corporation and Java enthusiasts everywhere want to sell Java to as many people as possible? Well, here's your sales pitch: "HAS ITS OWN VARIABLE-SWAPPING OPERATOR!!" I even came up with a symbol I think they should use for this operator: §
So to do the swap I want to do, we have:
a § b; // TADA!!
or
n § n[i+1];
This would be one of the first operators that needs an l-value on both the left-hand side and the right-hand side.
Now you might think, oh come on, that's ridiculous. Make a special operator for something like that, which is needed so rarely. Why make a whole special operator for that? To that my response is, I bet it might be used more than this operator:

a >>>= b;

HAHAHA!!!

 

[Diancecht]

Nice disertation.

But that was an assignment, and this is supposed to be a forum for IT professionals. When you become one, you will realize that you have the requirement of doing something the best possible way, and there's no room for "you have to use arrays" or "you can't use static methods"

So the answers you got were professional answers that would make your program more efficient.

Furthermore, you will learn that readibility and mantainability of code is usually more important that useless and still-to-prove performance improvements

Good luck

Cheers,
Dian

 

[stefanwagner]

A swapoperator schould look more swappingly, like a <-> b, or a <~> b

don't visit my homepage:

http://home.arcor.de/hirnstrom/minis/index.html

 

[stevexff]

Doing programming is a complete waste of time!!

Possibly, but it pays the bills. However, the next time you use your mobile, iPod, satnav, credit card, xBox, PC... (cont. p94) think how much time you'd be wasting if you didn't have them...

Steve

[small]"Every program can be reduced by one instruction, and every program has at least one bug. Therefore, any program can be reduced to one instruction which doesn't work." (Object:erlDesignPatterns)[/small]