swapping two variables without using a temp var

Fdbdc4176840d77fe6a8deca457595ab
0
dk 158 Jul 31, 2003 at 15:59
void swap(int &x, int &y)
{
    x -= y;
    y += x;         // y gets the original value of x
    x = (y - x);    // x gets the original value of y
}

Enjoy testing it out!

33 Replies

Please log in or register to post a reply.

4851117d61425bafb6c034e0f595d517
0
DrunkenCoder 101 Aug 01, 2003 at 06:22

and don’t try swapping a variable with itself…

the code below, have the exact same behaviour.

void swap2(int &x, int &y)
{
    x ^= y ^= x ^= y;
}
6ad5f8c742f1e8ec61000e2b0900fc76
0
davepermen 101 Aug 03, 2003 at 20:13

hehe, the much beloved xor..

haven’t seen the +- above yet..

but fastest is still with a temp variable.. register actually..

__asm {
mov eax,a
mov ebx,b
mov b,eax
mov a,ebx
}

or possibly there is even some way with mmx? :D

similar there is something for the fu**ing fpu..

but its always fun to swap “mathematically”.. without tempvar..

with that idea, people where able to define the radix sort, the only sort faster than the minimum O(n*lg2(n)).. hehe:D

4851117d61425bafb6c034e0f595d517
0
DrunkenCoder 101 Aug 04, 2003 at 06:14

smaller (but definatly not faster)

_asm
{
 xchg [a], eax
 xchg [b], eax
 xchg [a], eax
}

but if you’re resorting to assembly swaping of variables you’re probably
already writing the loop in assembly and trying to hold everything in
registers.

6ad5f8c742f1e8ec61000e2b0900fc76
0
davepermen 101 Aug 04, 2003 at 06:17

i never got how xchg really works, but it looks similar to the xor-snippet above :D

any other swap-codes?

4851117d61425bafb6c034e0f595d517
0
DrunkenCoder 101 Aug 04, 2003 at 08:22

well, the ones I can think of right now are

push    [a]
push    [b]
pop [a]
pop [b]

not very effective and even worse for register only swaps where xchg should
be used, but it’s diffrent…

for floats you could use:

fldp [a]
fldp [b]
fxch
fstp [a] 
fstp [b]

using mmx you could use the pshufw instruction family.

22b3033832c5c699c856814b0cf80cb1
0
bladder 101 Sep 22, 2003 at 08:58

@davepermen

any other swap-codes?

void swap(int& a, int&b )
{
  int c = a;
  a = b;
  b = c;
}

sorry. couldnt resist.

2b97deded6213469bcd87b65cce5d014
0
Mihail121 102 Oct 20, 2003 at 09:31

Here is a swap performed without a second variable. My creation so hands off!!!!

void swap(int *x,int *y)
{
   int second_varible;
   int third_variable;

   // See?! I'm not using the second!!!

  third_variable = *y;
  *y = *x;
  *x = third_variable;
}
F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Oct 20, 2003 at 11:13

:lol: :lol: :lol:

no wait you are serious about your post ?

6ad5f8c742f1e8ec61000e2b0900fc76
0
davepermen 101 Oct 20, 2003 at 13:42

hehe

Fe2c292911f2fadfba66571370810280
0
Smokey97 101 Oct 21, 2003 at 01:22

lol, i saw this post a few mins after he posted it… and i thought it must have been a joke, so i didnt say anything… but i guess ti isint a joke. :lol: :lol: :lol: :lol:

2b97deded6213469bcd87b65cce5d014
0
Mihail121 102 Oct 21, 2003 at 09:24

What’s wrong with you people? Why do u laugh? Of course i’m serious. Don’t u see it works perfecly fine?! I use this one a lot in my projects. Stable and fast and everything. Yep it’s cool :D

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Oct 21, 2003 at 11:11

hospital or police ???

280b3ca57720c1b1ad08dbc458325952
0
FarooqMela 101 Oct 13, 2004 at 21:09

I had something similar sitting around in a header file…
Mine is one line of code though ;-)

inline void
UselessSwap(int& a, int &b)
{
  a -= b += a -= b = -b;
}
Aed0ca439c3e81c59c4317f7b5cc5835
0
momotaro 101 Oct 10, 2006 at 23:29

where the hell did u find this one! it is pretty cool!

B91eae75cd6245bd8074bd0c3f1cc495
0
Nils_Pipenbrinck 101 Oct 11, 2006 at 01:19

Haha..

What a great thread.. I like the last one.. Never thought about this solution (did anyone tried if it really works?). I also like the function name as it really sais what it’s all about.

These “optimizations” are nowadays slower than a temporary variable. But they re cool nevertheless.

I like bit-tricks like these alot.

6aa952514ff4e5439df1e9e6d337b864
0
roel 101 Oct 11, 2006 at 09:26

Funny thread indeed, resurrecting old threads isn’t always that bad :)

22b3033832c5c699c856814b0cf80cb1
0
bladder 101 Oct 11, 2006 at 23:20

@FarooqMela

I had something similar sitting around in a header file…
Mine is one line of code though ;-)

inline void
UselessSwap(int& a, int &;)
{
  a -= b += a -= b = -b;
}

Not that I’m whining or anything, but if my understanding is correct about certain aspects of c++, the above code is going straight for the realm of “undefined behavior” in c++.

Someone correct me if I’m wrong.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Oct 11, 2006 at 23:26

You’re wrong ;)

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Oct 11, 2006 at 23:39

Sorry, I was being a bitch :happy:
The reason you’re wrong is because the associativity of these expressions is well defined. Just as a + b + c + d is parsed as ((a + ;) + c) + d and std::cout << “hello” << 34 << std::endl is equivalent to ((std::cout << “hello”) << 34) << std::endl, this expression becomes a -= (b += (a -= (b = -B)))

Each = operator returns a reference to *this and is used in the outer expression. The thing that isn’t defined is the order of evaluation (which is different from associativity) in the function argument list. ++a = a++ is undefined because that translates to operator=(++a, a++) and the outcome depends on which is evaluated first: ++a or a++.

22b3033832c5c699c856814b0cf80cb1
0
bladder 101 Oct 12, 2006 at 00:50

:wallbash: argh…

Ok ok, hold on, so the above would translate to:

op-=( a, op+=( b, op-=( a, op=( b, op-( b ) ) ) ) )

mhmm… i see i see…

Man they keep on saying that it’s easy to get caught if you don’t read the standard specs. But I gotta say, the more I’m reading the specs the more I’m getting confused. All that monkey business about sequence points -> ;)

the following quote+reply is a preemptive strike in-case davperman reads this:
@davperman

… some stuff… use c# …more stuff…

ok.

22b3033832c5c699c856814b0cf80cb1
0
bladder 101 Oct 21, 2006 at 01:57

Yo! .oisyn!!! You have some explaining to do:

I went back to all this stuff and searched some on undefined behavior and found some… “stuff”. Now a statement such as:

i = i++;

is undefined right? because the standard claims that you cannot modify the same value between sequence points. Associativity doesnt come into play in the above.

So looking at that += stuff in the same light as i = i++ we have:

i = i += whatever;

The exact words of the standard are:

“Except where noted, the order of evaluation of operands of individual operators and subexpressions of individual expressions, and the order in which side effects take place, is unspecified. Between the previous and next sequence point a scalar object shall have its stored value modified at most once by the evaluation of an expression.” [from 5.0.4]

but in the above expression, it’s being modified twice, so it should be undefined. So while it is defined by associativity, the actual evaluation of the internal representation on i is undefined, so the value of i is undefined after the expression (a direct effect of undefined order of evaluation)

if you we’re going by associativity, the i = i++ should also be defined that way:

op=(i, op++(i))

or for a = a+= b;

op=(a, op+=(a, :huh:)

[edit]
Another way of putting it, the expr “a -= b += a -= b = -b;” does the following:

A: assign negative b to b
B: subtract b from a
C: add a to b
D: subtract b from a

The sequence points statement says that the order of eval is undefined so it could be ABCD or ACDB or BCDA, etc… I’m not saying the above won’t work, but it’s still undefined according to the standard (sigh… again if i’m understanding all this correctly)
[/edit]

6ad5f8c742f1e8ec61000e2b0900fc76
0
davepermen 101 Oct 21, 2006 at 16:50

@bladder

the following quote+reply is a preemptive strike in-case davperman reads this:

more important: learn my name

22b3033832c5c699c856814b0cf80cb1
0
bladder 101 Oct 21, 2006 at 17:32

apologies davepermen - believe it or not, i was expecting such a reply from you :huh:. I was unsure when typing the spelling and i recalled you would always grab anyone who didn’t spell your name correctly. But I just didn’t have the time to search for the correct spelling.

8fd4a055522ce713cde7dd1cb4083cb2
0
martinsm 101 Oct 21, 2006 at 18:21

C++:

std::swap(x, y);

Python:

x, y = y, x
340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Oct 21, 2006 at 21:10

bladder: You’re actually on to something there, I didn’t think of that. But I’m not so sure if you’re actually right in the way that the swap expression is undefined. The standard clearly says that such an expression can be undefined, but that is more in the general sense. The real question we need answered here is: is a compiler really allowed *in this particular case* to use old values of a and/or b high in the expression tree.

Surely, this is not undefined, at least not according to that paragraph:

a += b += 3;

both b and a are changed only once in the expression. Yet, how is that different when changing a to b. so it reads b += b += 3? If the compiler can choose the old value of b on the right side of the first +=, the first example would be undefined as well, which isn’t the case.

But, when rambling about this, something came up. It may very well have to do with the actual storage of the result in the variables. So suppose we have this code

int b = 1;
b += b += 2;

Of course, you’d expect b to be increased to 3, and then add the result (3) to the new value of b (3), which results in 6.
Now let’s assume some intermediate code the compiler produces with this expression

int b = 1;
register reg_b = b + 2;
b = reg_b; // #1
register reg_b2 = reg_b + reg_b;
b = reg_b2; // #2

Now, almost every compiler would ignore #1 here, but the standard doesn’t say that it has to, nor does it say that it should come before #2. Clearly, when #1 is generated after #2, b would finally yield 3 instead of the 6 you suspect. I think this is where the ‘undefinedness’ (is that a word? it is now) comes from.

So yeah, that swap expression is probably undefined. Not in the way that it calculates the wrong value, but in the way that the actual calculated value is not returned to the variables correctly :)

I was wrong, every point their finger at me :huh:
COMMENCE FINGER-POINTING

2b86346862e39fd5476b34bb3f7314ca
0
Kieran_Hewitson 101 Feb 26, 2010 at 11:20

sorry for the necro… but this post is quite high on google when searching swap variables…
@FarooqMela

I had something similar sitting around in a header file…
Mine is one line of code though ;-)

inline void
UselessSwap(int& a, int &B)
{
  a -= b += a -= b = -b;
}

for me, that didn’t work… but this did :)

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

I’m using C# not C++ so that might make a difference, i don’t know.

There’s actually 3 more ways of doing this as far as i know:

a ^= b;
b ^= a;
a ^= b;

the use of a 3rd variable also, and the obvious one:

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

hopefully those will help someone, if not then just kick me up the backside! :)

edit:
also, you can do this if you really want…

string aa = a.ToString();
string bb = b.ToString();
bb += aa;
aa = bb.Substring(0, bb.LastIndexOf(aa));
bb = bb.Replace(aa, "");
a = int.Parse(aa);
b = int.Parse(bb);

this will work for strings too, or pretty much anything provided it’s got a way to convert to it’s original format (maybe even your own custom class?)

but that’s just me trying to be clever, if you had 2 classes that needed switching, it’s best to use the a \^= b etc.

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 104 Feb 26, 2010 at 14:00

you sort three variables using 3 swaps

if(a<b) swap(a,b);
if(b<c) swap(b,c);
if(a<b) swap(a,b);

thats what i use swapping lots for, and i also swap to get bounding
rects.

“It is important to swap.”

But until I read this, i didnt know there were even fancier ways to do it. :)

A638aa42130293f319eda7fa4ba121f4
0
fireside 141 Feb 26, 2010 at 16:35

Interesting read, but I won’t remember any of them when I need to do it, so it’s still old temp for me.

2b86346862e39fd5476b34bb3f7314ca
0
Kieran_Hewitson 101 Mar 02, 2010 at 11:07

@rouncer

if(a<B) swap(a,B);
if(b<c) swap(b,c);
if(a<B) swap(a,B);

aye but the way you sort is assuming you only have 3 numbers to sort :).

I would use something more like this:

//Create List where you want, don't declare it publically though ;)
List<int> numbers = new List<int>{/*put your integers here in form 1,2,3*/};
numbers = Sort(numbers);

private List<int> Sort(List<int> numbers)
{
    //Declare new list to put the new sorted list into
    List<int> sortedNumbers = new List<int>();
    int i = 0;
    int imax = numbers.Count;
    for(i=0; i<imax;i++)
    {//Just a for, being done the amount of times as the amount of numbers in list
        int highest = Highest(numbers);
        sortedNumbers.Add(highest);
        numbers.Remove(highest);
    }

    return sortedNumbers;
}

private int Highest(List<int> numbers)
{//retrieves highest number to be removed from numbers and to be added to sortedList
    int highest = int.MinValue;
    foreach (var i in numbers)
    {
        if (i > highest)
            highest = i;
    }
    return highest;
}

This method doesn’t call the sort more than needed… yours is what would be called the bubble sorting method, which would only work if you know exactly how many ints you are sorting and then you would need to change your code to look a mess. Using this method has compatibility for any size of list :).

Is that ‘swap’ function built into a different code than c# or is it a function you made?

9c876748cc763a2120b1c230a1de0ea5
0
Hickeroar 101 Apr 28, 2010 at 16:28

thought of this in PHP this morning:

function swapVars (&$a, &$B) {
    list($b, $a) = array($a, $B);
}
A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Apr 28, 2010 at 16:31

Actually, that uses temporaries internally, since you’re constructing the array object and storing the values in it.

The Python “a,b = b,a” is the same way.

9c876748cc763a2120b1c230a1de0ea5
0
Hickeroar 101 Apr 28, 2010 at 16:42

@Reedbeta

Actually, that uses temporaries internally, since you’re constructing the array object and storing the values in it. The Python “a,b = b,a” is the same way.

Yeah, it’s definitely not a pure/academic answer. It’s also probably not nearly as fast as the simple arithmetic solution.

The python method is what made me think of the “php alternative.”

However, it’s important to note that the python and php solutions would swap any variable type, whereas the arithmetic solutions only work on numbers.

Does anyone have any “true” solutions to this problem if you were operating on any given object, or string?

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Apr 28, 2010 at 18:00

You could apply one of the integer swap methods to every byte or word in an arbitrarily large chunk of data. B) (It would have to be a method that wasn’t sensitive to overflow issues, e.g. the XOR one someone posted - I’m not sure if the add/subtract ones would work.) That should get you a bit-for-bit swap of the objects’ memory images.

Of course, that’s not always what you want when relocating objects…for instance if either object contains a pointer into itself, or a pointer to the other object, those would be wrong following the swap. (The same issues exist when swapping by means of a temporary copy, of course.)