Swap Integers

I have to write a function that will swap the value of two integers around. The definition for the function is swapInts(int *firstInt, int *secondInt);

As it's address' that's being passed in I thought the following would do it:

Code:

---

void swapInts(int *firstInt, int *secondInt)
{
        int *tempInt = firstInt;
        firstInt = secondInt;
        secondInt = tempInt;
}

---

In fact, I still think that the above should work but I can't figure out why it doesn't. The lines that are calling the above look like this:

Code:

---

int firstInt = 1;
int secondInt = 2;

swapInts(firstInt, secondInt);

std::cout << "firstInt: " << firstInt << " secondInt: " << secondInt << "\n";

---

If I test the value of firstInt and secondInt at the end of the swapInts function they are swapped but when they're output back in the main program they aren't anymore. Why is this?

The only way I could get it to work is to use the actual values of the ints like this:

Code:

---

void swapInts(int *firstInt, int *secondInt)
{
        int tempInt = *firstInt;
        *firstInt = *secondInt;
        *secondInt = tempInt;
}

---

But this seems a bit silly. Surely I could just change the address' that the variables are pointing to?

> swapInts(firstInt, secondInt);
This shouldn't even compile, given your function definition.

> Surely I could just change the address' that the variables are pointing to?
You can't change where a variable exists.

You pass a pointer to the two ints, then swap the data by dereferencing those pointers.

Quote:

---

Originally Posted by Salem

> swapInts(firstInt, secondInt);
This shouldn't even compile, given your function definition.

---

You're right. It was swapInts(&firstInt, &secondInt);

Quote:

---

Originally Posted by Salem

> Surely I could just change the address' that the variables are pointing to?
You can't change where a variable exists.

You pass a pointer to the two ints, then swap the data by dereferencing those pointers.

---

If that's the case then why does it work in the function? If I do...

int firstInt = 1;
int secondInt = 2;

...and say the address' for these variables are (for argument's sake) 0x22CCE4 and 0x22CCE0 respectively then when I set the address of secondInt to 0x22CCE4 it's value will be 1. By the same token, if I set the address of firstInt to 0X22CCE0 it's value should be 2. That's the because the values stored at those address' are 1 and 2 respectively, right?

Or am I missing something completely? :)

The more C++ way in this situation is to use references.

Code:

---

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

int main()
{
    int first = 1, second = 2;
    swap(first, second);
}

---

A reference (declared with the & symbol) means that the variable is not a copy of the value passed as an argument, but an alias or another name for the original variable in the calling code.

As for your question, you can't change the address of a variable. You can change where a pointer is pointing to but in this case you are not swapping pointers but the contents of what the two pointers are pointing to. (In main you don't declare pointers but ints and try to change their content.)

Quote:

---

Originally Posted by anon

The more C++ way in this situation is to use references.

---

I think that's a little subjective. Even so, I AM using references. See: swapInts(&firstInt, &secondInt);

Quote:

---

Originally Posted by anon

A reference (declared with the & symbol) means that the variable is not a copy of the value passed as an argument, but an alias or another name for the original variable in the calling code.

---

A thought a reference was literally the address of the variable? So it essentially gets you a pointer to the address that the value is stored in.

Quote:

---

Originally Posted by anon

As for your question, you can't change the address of a variable.

---

Again, if I can't then why does it work in the function.

Quote:

---

Originally Posted by anon

You can change where a pointer is pointing to but in this case you are not swapping pointers but the contents of what the two pointers are pointing to. (In main you don't declare pointers but ints and try to change their content.)

---

Well, if I use pointers I still get the same result. I changed int firstInt = 10 to int *firstInt = new int(10) and int secondInt = 20 to int *secondInt = new int(20) and again, they were swapped in the function but when I output their values they aren't.

Quote:

---

I think that's a little subjective.

---

A little subjective, yes, but mostly objective since that is the way the standard library does it.

Quote:

---

Even so, I AM using references. See: swapInts(&firstInt, &secondInt);

---

No, that is more like using pointers and addresses than references.

Quote:

---

A thought a reference was literally the address of the variable? So it essentially gets you a pointer to the address that the value is stored in.

---

In C++, a reference is an alias, a pointer is a variable that holds an address.

Quote:

---

Surely I could just change the address' that the variables are pointing to?

---

The pointer arguments in your swap function are local variables.

Quote:

---

Originally Posted by redneon

I think that's a little subjective. Even so, I AM using references. See: swapInts(&firstInt, &secondInt);

---

It's more like intersubjective :) (Its easier to make mistakes with pointers...)
And you are not using references, but the address-of operator. (Yes in C++ many operators have different meanings in different contexts.)

Quote:

---

A thought a reference was literally the address of the variable? So it essentially gets you a pointer to the address that the value is stored in.

---

Not quite. The syntax how you use a reference is identical to how you use a variable (not a pointer). You can't have a NULL-reference and you can't change what a reference is referencing (make int& c first a reference of int a and then change it into a reference of int b).

Quote:

---

Again, if I can't then why does it work in the function.

---

You have to make yourself clear whats the difference between a pointer and what it points to. The function works because you pass it the addresses of two int variables (which become local copies of the pointers you pass) and you swap what resides at these addresses.
The pointers themselves, however, are local to the function and therefore have no effect to the calling code.

Code:

---

swap(int* a, int* b) //a and b are local to the function
{
    int* temp = a;
    a = b;
    b = temp;
    //no effect because a and b go out of scope here
}

---

Hence, if you want to swap whole arrays (pointers), you'll need to take it one step further and pass a pointer to the pointer that points to the array (or a reference of the pointer to the array).

Ok. I'm a little confused about pointers then. I understand references now but take the following code:

Code:

---

void inc(int *val)
{
    *val++;
}

int main()
{
    int a = 10;
    inc(&a);

    std::cout << "a: " << a;
}

---

The function inc takes a pointer to an address as an argument, right? So when I pass it the address of the variable a val should equal the address of a. So, when I do *val++ I am then incrementing the value stored in the address of a, correct? If this is the case, any other pointers that point to that address should then contain the new value, surely?

So in the above, int a = 10. Then it's address is passed into the function inc. The value that's stored at that address is then incremented by 1. So back in main, the value of a should now be 11, but it isn't.

I'm obviously not understanding something about pointers. I understand that if I used a reference the variable a would get incremented because effectively the reference IS the variable a. It's just the pointers that's blowing my mind =o)

Quote:

---

Originally Posted by redneon

The function int takes a pointer to an address as an argument, right? So when I pass it the address of the variable a val should equal the address of a.

---

No and no. The function takes a pointer to an int, which is an address. And in the function you are incrementing the pointer, not what it points to.

This was recently discussed in another thread. The function is equivalent to:

Code:

---

void inc(int *val)
{
    //*val++; // ==> *(val++);
    *val; //has no effect
    val++;  //possibly undefined result? For sure undefined to dereference now.
}

int main()
{
    int a = 10;
    inc(&a);

    std::cout << "a: " << a;
}

---

Because of precedence of operators, it should look like this:

Code:

---

void inc(int *val)
{
    (*val)++;
}

---

Or again, you might see how using a reference leaves less room for mistakes and misunderstanding:

Code:

---

void inc(int& val)
{
    val++;
}

---

Or

Code:

---

void inc(int *val)
{
    ++*val;
}

---

Quote:

---

Originally Posted by Dave_Sinkula

No and no. The function takes a pointer to an int, which is an address. And in the function you are incrementing the pointer, not what it points to.

---

Ah, I think I understand but I just want someone to confirm it.

If in my main function I do this:

Code:

---

    int a = 100;
    int *b = &a;

    *b += 50;

---

Then both a and b's values will be 150 because they both point to the same address, correct?

Now, if I did this:

Code:

---

void inc(int *val)
{
    *val += 50;
}

int main()
{
    int a = 100;
}

---

The argument int *val in the function inc() is a pointer to a new int with a different address. So, although I'm passing a pointer to an int as an argument the pointer for both wont point to the same address, right?

Quote:

---

Ah, I think I understand but I just want someone to confirm it.

If in my main function I do this:

Code:

int a = 100;
int *b = &a;

*b += 50;

Then both a and b's values will be 150 because they both point to the same address, correct?

---

"a" is a variable that initially has the value of 100.
"b" is a pointer to "a" (b's value is some memory address, and the value at that memory address is that of "a": 100).
After the increment, where you dereference "b", i.e use it to "go" to the memory location which has 100, the memory (variable "a") that "b" points to will have the value 150.
Now "*b == 150" and "*b == a" but "b == &a" - b itself will still have the same value as before: the address of a that didn't change.

Quote:

---

The argument int *val in the function inc() is a pointer to a new int with a different address.

---

It is a pointer to the int variable whose address was passed to it. You are not actually using inc() in your second code example. If you call inc(&a), then val in inc() does point to a, for the duration of that function call.

Quote:

---

Originally Posted by anon

"a" is a variable that initially has the value of 100.
"b" is a pointer to "a" (b's value is some memory address, and the value at that memory address is that of "a": 100).
After the increment, where you dereference "b", i.e use it to "go" to the memory location which has 100, the memory (variable "a") that "b" points to will have the value 150.
Now "*b == 150" and "*b == a" but "b == &a" - b itself will still have the same value as before: the address of a that didn't change.

---

Yeah, I get that. b doesn't actually contain a value. It contains the address of a. So when I increment the value stored in the memory address that b point to I am incrementing the value of a by proxy.

That's why I'm confused about the function. If it works in main then I would have thought that doing...

Code:

---

void inc(int *b)
{
    *b += 50;
}

int main()
{
    int a = 100;

    inc(&a);

    return 0;
}

---

...would work.

EDIT: Fixed stupid mistakes. Evidently it does work =o)

Now, a is local to the main function. You are trying to access it as a global variable in inc(). Try this instead:

Code:

---

#include <iostream>

void inc(int* b)
{
    *b += 50;
}

int main()
{
    int a = 100;
    std::cout << "a = " << a << std::endl;
    inc(&a);
    std::cout << "a = " << a << std::endl;
}

---

You guys are so funny...

Code:

---

template <typename T>
void swap(T &a, T &b)
{
    T tmp;
    tmp = a;
    a = b;
    b = tmp;
}

---

Or for ints only:

Code:

---

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

---

Quote:

---

You guys are so funny...

---

That's rather funny too, writing a function template already present in the standard library, and doing it rather inefficiently by not using the copy constructor ;)

Quote:

---

Originally Posted by laserlight

That's rather funny too, writing a function template already present in the standard library, and doing it rather inefficiently by not using the copy constructor ;)

---

I did that on purpose, since initializing tmp with the copy constructor, then doing the assignments via operator=, seemed asymmetrical to me.

Quote:

---

I did that on purpose, since initializing tmp with the copy constructor, then doing the assignments via operator=, seemed asymmetrical to me.

---

Interesting way of viewing it. Going off topic here, but I suppose redneon's query on pointers has been answered: what do you mean by "asymmetrical"?

Quote:

---

Originally Posted by laserlight

Interesting way of viewing it. Going off topic here, but I suppose redneon's query on pointers has been answered: what do you mean by "asymmetrical"?

---

Well, what if operator= and the copy constructor do slightly different things?

Quote:

---

Well, what if operator= and the copy constructor do slightly different things?

---

What if operator= does not actually assign? The way I see it, one has to assume certain preconditions are met before the swap works, and having the copy constructor and copy assignment operator do the same thing is one such condition.

EDIT:
Or perhaps, what if there is no default constructor? swap() is required to work on types that are copy constructible and assignable, with no requirement on being default constructible.

Quote:

---

Originally Posted by laserlight

What if operator= does not actually assign? The way I see it, one has to assume certain preconditions are met before the swap works, and having the copy constructor and copy assignment operator do the same thing is one such condition.

---

Valid argument.

Quote:

---

Originally Posted by brewbuck

Or for ints only:

Code:

---

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

---

---

That one's so icky it's just not worth mention.

Quote:

---

Originally Posted by Dave_Sinkula

That one's so icky it's just not worth mention.

---

Funny thing though, gcc on Intel actually optimizes that into a xchg instruction, at least if the variables are held in registers at that point. I don't dare to even consider what sort of machinery inside gcc is able to figure that out!

Even at that it still has a bug in it.

Quote:

---

Originally Posted by Dave_Sinkula

Even at that it still has a bug in it.

---

I'm stumped.

The swap with self thingy.

Quote:

---

Originally Posted by Dave_Sinkula

The swap with self thingy.

---

Of course.

Quote:

---

Originally Posted by brewbuck

Funny thing though, gcc on Intel actually optimizes that into a xchg instruction, at least if the variables are held in registers at that point. I don't dare to even consider what sort of machinery inside gcc is able to figure that out!

---

I suppose they decided to fix the mistake "clever" programmers are making by using this. As for the machinery, it's nothing that isn't there to recognize far more complex patterns, such as loops that can/should be unrolled.

Quote:

---

Originally Posted by CornedBee

I suppose they decided to fix the mistake "clever" programmers are making by using this. As for the machinery, it's nothing that isn't there to recognize far more complex patterns, such as loops that can/should be unrolled.

---

It's not really a mistake if you know that the swapped objects are not the same. In a swap function, that is obviously an inappropriate assumption, but it isn't always.

I wasn't really being serious, though.

It's still a mistake, because there is not advantage to the method.

Quote:

---

Originally Posted by CornedBee

It's still a mistake, because there is not advantage to the method.

---

It requires no temporary variable.

> It requires no temporary variable.
Your point being?

Code:

---

void foo ( int a, int b ) {
    a ^= b;
    b ^= a;
    a ^= b;
    printf( "%d %d\n", a, b );
}

void bar ( int a, int b ) {
    int temp = a;
    a = b;
    b = temp;
    printf( "%d %d\n", a, b );
}

---

By the time the optimiser (gcc) has finished with the second one, it has managed to simplify the code into printf("%d %d\n", b, a );
The temp and the swap are GONE.
Not so with the attempt to obfuscate the heck out of things in the mistaken belief that using a variable is the end of the world. As well as confusing the average reader, you also managed to hide the true intent of the code from the compiler as well.

Clear simple code wins every time. If you insist on treating C like some high level assembler, then expect to get the code you write.

I think this reasoning is not quite right. That's not what you need swapping for, where you really need values relocated.

However, wouldn't xor be something more complicated as simple assignment? A quick test showed that using a temp is a bit faster.

Quote:

---

Originally Posted by Salem

The temp and the swap are GONE.

---

If you have an optimizer...

Quote:

---

Not so with the attempt to obfuscate the heck out of things in the mistaken belief that using a variable is the end of the world.

---

I certainly don't believe that. And anybody who claims to know CS should know this property. I never said it should be used in real code.

Quote:

---

Clear simple code wins every time. If you insist on treating C like some high level assembler, then expect to get the code you write.

---

You're preaching to a choir... Why did I post it in the first place? I dunno, I was bored. Had I known you would jump all over me I wouldn't have bothered.

I'd never heard of this algorithm. The following talks about its efficiency vs. using a temporary.

http://en.wikipedia.org/wiki/XOR_swap_algorithm

Quote:

---

Originally Posted by robatino

I'd never heard of this algorithm.

---

Count yourself lucky.

Quote:

---

Originally Posted by robatino

I'd never heard of this algorithm. The following talks about its efficiency vs. using a temporary.

http://en.wikipedia.org/wiki/XOR_swap_algorithm

---

I would just like to point out at this time, that any method which has it's own GOSH DANG WIKI PAGE cannot possibly be "obscure." This is something a CS person should know. I didn't say "use," I said "know."

EDIT: Why should you know it? For one thing, it might be on your final in boolean algebra.

Quote:

---

Originally Posted by Dave_Sinkula

Count yourself lucky.

---

Honestly... It's only obscure if you don't know it. How is this any different than shifting right by one in order to divide an integer by 2? I think it's something a person should be aware of, not necessarily that they should put it into practice in new code.

If you understand it, then you can "fix" it when you see it in older code. Isn't that a good enough reason to be aware of it?

brewbuck: Your points are well understood by many of us here. We tend to be harsh on things that generally persuade young'uns to do the Wrong Thing, regardless of the intentions, merely -- hopefully -- to produce better programmers. There is no malice.

There are a number of things that are easily beaten up merely by presentation:

• void main()
• fflush(stdin)
• gets(string)
• Etc.

The XOR swap thing merely happens to be among them, but not (yet) in the FAQ.

I don't know, I guess that it's just a 25-year-old solution to a 30-year-old problem that some compilers may possibly now fix up bad programming idioms that may be common.

Quote:

---

Originally Posted by brewbuck

How is this any different than shifting right by one in order to divide an integer by 2?

---

Doesn't this have issues depending on the implementation?

(Seriously, it's been a long day and I'm forgetful.)

[edit]And frankly, fixing a problem that does not exist is in itself a problem.

> This is something a CS person should know.
I'm a mathematician. I don't have a formal CS background.

Quote:

---

Originally Posted by robatino

> This is something a CS person should know.
I'm a mathematician. I don't have a formal CS background.

---

I didn't mean you, personally. Sorry.

Quote:

---

Doesn't this have issues depending on the implementation?

---

Yes, since the C++ Standard leaves the exact result of a right shift as implementation defined for negative integers. For non-negative integers it is quite clear that a division by the nth power of two will be performed. So, (1 >> 1) == 0, but (-1 >> 1) == 0 or (-1 >> 1) == -1 are both possible, as are other interpretations of what happens on a right shift (e.g., largest possible positive integer value).

Quote:

---

Originally Posted by Dave_Sinkula

[edit]And frankly, fixing a problem that does not exist is in itself a problem.

---

Wait. So we're saying that the XOR trick is a problem, or not a problem? I'm confused.

Quote:

---

Originally Posted by laserlight

Yes, since the C++ Standard leaves the exact result of a right shift as implementation defined for negative integers. For non-negative integers it is quite clear that a division by the nth power of two will be performed. So, (1 >> 1) == 0, but (-1 >> 1) == 0 or (-1 >> 1) == -1 are both possible, as are other interpretations of what happens on a right shift (e.g., largest possible positive integer value).

---

Out of instinct, I would never shift right to divide when I knew that the value might be negative. It's sometimes hard for me to gauge what should be "obvious." Again, I mentioned it simply for the sake of mentioning it.

My impression is that it was an '70's problem with the price of memory affecting hardware manufacturer's choices: namely, have less memory. So due to the lack of available registers in hardware, the XOR swap was developed by clever programmers. As soon as the unavailability of hardware registers disappeared, so did the problem that this addressed. So computer hardware developed since at least the early '80's already solves the problem this solution seeks to solve. Thus making it a non-issue.

Unless programmers are still taught that we live in the 1970's. Then this can screw up some compilers that were raised to understand that the programmers writing the code already knew that.

So apparently now compilers are supposed to solve problems that programmers are putting in practice that solve problems that have already been solved elsewise, but the programmer has yet to understand this.

Why shouldn't programming be a little simpler?

Okay okay, I give up... In the future, I'll keep stuff like this a secret. When newbie folks see it in code they'll just be stuck wondering "What the hell is THAT?"

EDIT: Also, if I really used this stuff in my own code, don't you think I would have known about the swap-with-self problem off the top of my head? So obviously I don't do this.

Again, you seem to misunderstand the thwarting I've undergone.

Sure it helps to know things about the underlying implementation, but that is not completely or entirely relevant.

Times change.

Just as sure as I can say, "Integer math is faster than floating point math," such things are subject to the times. Surely someone will discover this thread in a decade and try to ask me what I was smoking.

[My answer: a legal tobacco cigarette in the United States in my own garage. This itself may have changed in a decade.]

Quote:

---

Originally Posted by Dave_Sinkula

Just as sure as I can say, "Integer math is faster than floating point math," such things are subject to the times. Surely someone will discover this thread in a decade and try to ask me what I was smoking.

---

Funny you choose that example. I think that ceased to be true a few years ago, at least on the systems I was testing on. It seems like casting between the two is the source of slowness these days. Get your data into doubles and keep it there! :)

I make assumptions based on obsolete experience, too. I try to challenge my own assumptions as often as possible, but sometimes there just aren't enough useful hours in the day...

> The XOR swap thing merely happens to be among them, but not (yet) in the FAQ.
Are we inany hurry at all to change this? Just curious.

for simple stuff, try to use refs more, they provide cleaner syntax than pointers

>The XOR swap thing merely happens to be among them, but not (yet) in the FAQ.
I believe it's in the C faq.

But I agree with brewbuck, it's a good trick to know, the reason being some expert will come along and ridicule you for not knowing it. Just like if you don't know a certain acronym, you will get the same reaction.

Ridicule the "expert" in return for holding on to archaic, useless trivia. :)

Quote:

---

Originally Posted by CornedBee

Ridicule the "expert" in return for holding on to archaic, useless trivia. :)

---

Some of us can't help but hold on to pretty much everything interesting we ever saw. At times this is a real curse, because it makes me look like a loser who wasted his time memorizing useless facts. Hey, they just go in there and stay there, there's nothing conscious about it :)

Oh, I know that. It's very much imprinted in my brain, too. But I try to avoid spreading the knowledge about these things.

Quote:

---

Originally Posted by CornedBee

Oh, I know that. It's very much imprinted in my brain, too. But I try to avoid spreading the knowledge about these things.

---

I shall endeavor to be more esoteric.

I suppose the ratio of useful / useless knowledge I have is 0 - at least in integer math. :)

I expect if you saw some old game code, you'd see all kinds of tidbits like this. In fact it wouldn't surprise me to see them in new game code. The code may not run on every processor, but it's blazing fast.

You'd be surprised. Reusability is the keyword in game development nowadays.