How can you swap two variables without using a third?

Moore's law is just an observation and not a real law like the Law of Gravity.

Over the years, developers have taken the increasing CPU speeds and Memory sizes for granted. Here's a warm-up interview question that I ask every candidate.

Let's assume the working memory for your function is 8-Bytes. You are given two 32-Bit Integers and you need to swap them. In other words, how can you swap two variables without using a third?

Please take your time to solve this and refrain from looking up solutions online or for answers below. This is your first step in becoming a Computer Scientist!

---

If you accepted this challenge, ❤️ it and [follow me on Twitter](https://twitter.com/intent/follow?screen_name=theoutlander).

How to Improve Your Debugging Skills

Nick Karnik ・ Oct 1 '18

#beginners #computerscience #programming #debugging

Comments

[Dustin King]

x, y = y, x #

[Dustin King]

To be a little bit sneaky, use part of the function itself as swap space. This would only work if that space could be after the return instruction.

In pseudo-C:

#define NOP {32 bits of assembly NOP instructions};

void swap(int* a, int* b){

    *&yep = *a;
    *a = *b;
    *b = *&yep;

    return;

    yep:
    NOP;
}

This isn't thread-safe though, and a decent operating system might throw exceptions if you try to have executable code modify itself.

[Nick Karnik]

It creates more memory though.

[Zuodian Hu]

The NOPs don't actually give you any memory. Those NOPs are wherever the executable image was loaded in memory, and the variable yep is on the stack. Assuming your standard C memory model.

[Nick Karnik]

I misread the post on the phone, but I see what the code is doing. Although, I'm not sure what assigning to NOP does?

[Dustin King]

C memory layout:

(source)

The function code itself is in the text segment. The variables for a particular invocation of the function are on the stack. Padding out the function with NOP creates space within the function, which I'm using as a variable. Basically I'm interpreting the "working memory" part of the post to mean "variables allocated on the stack". Now that I think of it, what I'm doing is basically a static variable, which (according to the link) C puts in the initialized data segment if you do it the right way, but then it would legitimately be a variable so I'd lose.

It's probably not a legit way to do things (and might be impossible if the text segment is read-only as the link says it might be), but people had already posted the legit ways.

[Nick Karnik]

Thanks for that explanation. It's been a while since I've written C/C++, but this approach makes sense. I love the thought process of cleverly using that available memory, even if it doesn't work out. 👏👏👏

[Zuodian Hu]

The variable yep is declared within a function body without a static qualifier, which means it's what the C standard calls an automatic storage duration variable. This means its duration is between the curly braces, and most compilers will use a register or put it on the stack.

Being completely nitpicky here, but the variable yep is declared after its use and also without a type. I'm sure modern compilers wouldn't even let you do that.

Modern operating systems load the text segment into a virtual memory page marked as read-only. So yes, even if this compiles, it will generate a segfault on modern operating systems.

[Dustin King]

yep isn't a variable, though, it's a label, representing an offset from the start of the function.

I agree compilers and OS's will tend to prevent this. I said as much before, and trying to create a proof of concept in assembly has born that out.

It wasn't a completely fruitless exercise though, as it was a chance to learn some assembly, which provided some insights about the challenge that I might make a post about. Basically, swapping using math might not actually be more memory-efficient (however you define that, and without the kind of cheating I've been talking about) than swapping using "a variable".

[Leonardo Teteo]

This was my solution as well. I honestly never thought about this problem seriously and went for a third variable every time. I'm taking capacity for granted. I learned my lesson. u.u

[Sathwik Matsa]

Wait.. readability of your code is also important!

[Nick Karnik]

Sure, it is. That's when you modularize your code and make an inline method or macro out of this.

[simonhaisz]

Good thing the question was specific to integers. With floating point arithmetic this wouldn't be guaranteed to work in all cases. Especially in Java 😭

This is probably the simplest case that shows the space vs time choice for optimisation. Here you are saving memory but have more operations. 3 arithmetic and 3 assignments. If you used an extra variable you still have 3 assignments but lose the 3 arithmetic but also have to add/remove the variable to from the stack.

[P. Todd Decker]

JavaScript, by nature, stores all numbers as double-precision IEEE 754 floating point numbers. The 52 bits of the fractional portion is used to store integers. This results in 'maximum safe integer' of 2⁵³ - 1. Further complicating things is that JavaScript's bitwise operators only deal with the lowest 32 bits of JavaScript's 54-bit integers. So the bitwise approach will not work on big integers in JavaScript.

[Nick Karnik]

Can you please elaborate on that?

[Chinmay Joshi]

If that's the case, then why swap at all?

[dean]

Sorting functions. So you can write something simple like

// at this point in the sort, we know we must
// swap x with some other value
if a[x] < a[y] {
     swap(&a[x], &a[y])
} else {
     swap(&a[x], &a[z]) // a[x] and a[z] may be the same value
}

[Adarsh]

if (x == y) return;
x = x ^ y
y = x ^ y
x = x ^ y

Bitwise operators for the win.

[Nick Karnik]

The swap with bitwise operators will be the fastest at the hardware level. :)

[Adarsh]

Yes. Whenever you can achieve something using bitwise operations I always prefer that.

[Jason C. McDonald]

When I started going through the comments, I was actually thinking "what about bitwise xor?" And sure enough, here it is. ^,^

[Peter Ellis]

Rather disappointingly, in most modern hardware it's the one with the temp variable that is fastest.

[Nick Karnik]

Depending on the architecture and compiler, they end up using three registers to do a swap under the hood I think.

[Peter Ellis]

Yes, but the idea is that you do this in assembly. It was a common trick because it saved a register and (at worst) it ran in the same number of cycles.

[Nested Software]

This is a rather beautiful "bit" of problem solving :)

It will work for both integers and floating points, positive and negative, and there is no issue with overflow. If someone can figure this out on their own, I think that's quite impressive. Most of us just know it from having seen it before though.

[Nick Karnik]

That's true. My initial solution to it was using addition/subtraction and once I got the concept of diffs, I was able to deduce a solution using bit manipulation.

[P. Todd Decker]

JavaScript, by nature, stores all numbers as double-precision IEEE 754 floating point numbers. The 52 bits of the fractional portion is used to store integers. This results in 'maximum safe integer' of 2^53 - 1. Further complicating things is that JavaScript's bitwise operators only deal with the lowest 32 bits of JavaScript's 54-bit integers. So the bitwise approach will not work on big integers in JavaScript.

[Dave Carter™]

I guess BigInt new primitive proposal will do the trick :)

[ｅｎｄａｎ]

$a = 7;
$b = 9;

list($b, $a) = [$a, $b];

echo "a is " . $a; # 9
echo "b is " . $b; # 7

/* scratches head */

[Sergiu Mureşan]

I like defining one of these macros when swapping variables in C:

#define SWAP(A, B) A ^= B ^= A ^= B
#define SWAP(A, B) A = A - (B = (A = A + B) - B)

The second one works on floating point numbers too.

[Nick Karnik]

That's a good one. Although it won't work in Javascript I think.

x=10;y=5;console.log(x,y);(x=(x-(y = (x=x+y)-y)));console.log(x,y)

[Sergiu Mureşan]

I think it doesn't like the double assignment on same expression. In JS you can do:

[a, b] = [b, a];

or

b = [a, a = b][0];

although less readable.

[Nick Karnik]

[] allocates new space I think so this solution won't be in constant space.

[ｅｎｄａｎ]

function swap (&$a, $b, $A) {
    $a = $b;
    return $A;

} 

$a = 7;
$b = 9;

$b = swap($a, $b, $a);

echo "a is " . $a; # 9
echo "b is " . $b; # 7

/* scratches head again */

[Guillaume Martigny]

As funny as it is, you declare a new pointer to the swap function allocating new memory.

[Sven Luijten]

// Since PHP 7.1:
[$b, $a] = [$a, $b];

// Or before 7.1:
list($b, $a) = [$a, $b];

[Nick Karnik]

Do you know how this is implemented internally?

[Nick Karnik]

That's awesome. I did not know about it. I wonder if it swaps values instead of pointters.

Found this on SO @ stackoverflow.com/questions/445179....

[Peter Ellis]

So now we've reduced the problem to "How do you swap the two topmost stack items?" :)