0

Recently I came across this question write a function to swap two numbers without using extra space? The function can be in two ways:

int swap ( int *a, int* b)
{
    *a = *a+*b;
    *b = *a-*b;
    *a = *a-*b;
}

The other way is XOR operation:

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

Even though both these functions are a good idea, they will not work if both of a and b point to a single memory location? How to tackle this?

Kranthi Kumar
  • 1,184
  • 3
  • 13
  • 26
  • 7
    `if (a != b)`?? – Joseph Mansfield Apr 16 '13 at 09:38
  • 1
    That's a special case and that's normally how people handle it, as a special case. – Joe Apr 16 '13 at 09:38
  • Did you search for an answer first? – Peter Wood Apr 16 '13 at 09:39
  • 3
    Well if both pointers point to the same place, there's nothing to swap is there? A simple check should be enough for that. – Some programmer dude Apr 16 '13 at 09:39
  • This was asked a million times. – Lightness Races in Orbit Apr 16 '13 at 09:41
  • 3
    -1 for "Even though both these functions are a good idea". They are both terrible ideas. This is a perfect example of premature optimization. Use a temp variable, it will most likely be more efficient. And it doesn't make any sense to return a value. – Lundin Apr 16 '13 at 09:44
  • @Lundin Can you explain more about premature optimization – Kranthi Kumar Apr 16 '13 at 09:46
  • @Lundin Except he is not optimizing anything in there. I'd say your down vote is a greater example of anything that is premature. – luk32 Apr 16 '13 at 09:47
  • @luk32 "without using extra space" is an optimization. – Lundin Apr 16 '13 at 09:48
  • 1
    @Ludin What?! It looks like a constraint to me. What does it optimize? You are jumping to conclusions. Maybe it is an academical task. Maybe a real task. Why would you downvote question for any of such reasons. And I have heard about at least one example when such optimization did work good. – luk32 Apr 16 '13 at 09:50
  • @Kranthi Kumar Basically it means: the programmer thinks they are smarter than the compiler at optimizing code, while in reality they are not. So the programmer produces unreadable code, that isn't faster, but perhaps slower, than what the compiler would have done. To optimize code you need a lot of in-depth knowledge about the specific CPU, its instruction set, instruction pipes/cache etc etc. – Lundin Apr 16 '13 at 09:50
  • @Ludin I never said that it is a great idea of optimization. I just said it is a good idea for solving the problem basing on the constraints. – Kranthi Kumar Apr 16 '13 at 09:53
  • 5
    @luk32 There is no situation in the real world where it makes sense to use XOR swaps. If you can't store one int in memory for a plain swap function, then you should inline the function to begin with. The historical reasons for XOR swaps is that on systems with extremely small RAM, you'd use a register instead. But such optimizations does not even make sense on any of the most low-end 8-bitters today. It's an obsolete algorithm. – Lundin Apr 16 '13 at 09:53
  • 2
    @Ludin OP never said he uses it as an actual optimization in a production code. Of course it is not meant for a memory optimization. Maybe it is for better asm, or squeeze more instructions per cycle. Also would you down-vote all theoretical questions 'cause they are non-real world ? Actually nvm. It's relevant to question. I think you should differentiate between constraints and optimizations, though. – luk32 Apr 16 '13 at 10:04
  • 1
    @luk32 - The problem (in addition to being a duplicate) is that this code is just *never* useful. It doesn't produce smaller code, or faster. Using xor or add actually introduces *more* dependencies and makes the code run slower, if anything. And has the aliasing problem the OP asks about. Using `std::swap` in C++ solves all of that (and that function uses an extra variable *as an optimization*). – Bo Persson Apr 16 '13 at 12:24

4 Answers4

5

The problem is obvious in math.

int swap ( int *a, int* b)
{
    *a = *a+*b;
    *b = *a-*b;
    *a = *a-*b;
}

when a and b point to same place then, above code turns into

*a = *a + *a; // *a = 2 x (*a)
*b = *a - *a; // = 0
*a = *a - *a; // = 0

So, Both *a and *b are zero. Therefor you should handle it with an if:

int swap ( int *a, int* b)
{
    if (a!=b)
    {
      *a = *a+*b;
      *b = *a-*b;
      *a = *a-*b;
    }
}

And same for xor version.

masoud
  • 55,379
  • 16
  • 141
  • 208
2
#define SWAP(a, b) (((a) == (b)) || (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b))))
Joe
  • 7,378
  • 4
  • 37
  • 54
1

Why would anyone swap two numbers without using extra space?

What sadist would give you enough space for two but not three?

Why do you call it 'space' anyway? It's just a third number, there's no need to allude to a vast, vacuum-filled place.

The algorithm using a temporary uses O(1) space in the number of swap operations. It's O(n) in the numbers' length, but quite possibly so are the bit-twiddling and arithmetic ones given a processor-unfriendly n.

If you don't have enough space for a simple number, you've simply run out of space. I can't see where you can go from a swap in that case.

Why not store the two numbers in their proper places in the first place?

aib
  • 45,516
  • 10
  • 73
  • 79
-1

You can try this, a=a+b; b=a-b; a=a-b;

Subhajit
  • 320
  • 1
  • 6