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.

How to Improve Your Debugging Skills

Nick Karnik ・ Oct 1 '18 ・ 4 min read

#beginners #computerscience #programming #debugging

Comments

[tux0r]

x = x + y
y = x - y
x = x - y

[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
}

[tux0r]

Which would be inefficient, thus not recommended.

[dean]

The function usually gets inlined anyway (depending on your compiler) and if it starts with if x == y { return } then it just compiles to if x != y { /* swap x and y */ }

In fact, might as well use a temporary variable at that point if you're expecting for compiler optimizations :shrug:. At that point they'd just become temporary registers and wouldn't have anything in memory, and a single xchg call

[tux0r]

You could just write the registers yourself then...

[tux0r]

x = 1 + 1
y = 2 - 1
x = 2 - 1

Nope, still true.

[Adarsh]

Sorry perceived wrongly my mistake. Deleted the previous comment. But the possibility of overflow is still there in this method.

[Theofanis Despoudis]

Tricky bit: It can cause integer overflow if x + y > int.MAX

[tux0r]

Validity checks were not a part of the question. But yes, you are right.

[Theofanis Despoudis]

That's the second step in becoming a computer scientist.

[Lewis Cowles]

limit x and y to 16 bit or store 32-bit numbers in 64-bit. max int for 64-bit signed or unsigned is twice that of it's 32-bit counterpart.

You cannot overcome size problem if it's expressed in bits. Only higher-order structures like arrays would enable that and then you are absolutely storing more than two variables (possibly more than one per entry if it's a pointer).

[Theofanis Despoudis]

That defeats the purpose of doing that plus you are making a difficult work of complicating things. I suspect is better if you use a temp variable after all!

[Lewis Cowles]

I suspect it's better if you don't try to copy with only two memory areas, but if you're going to worry about overflowing, then doubling storage size is the least complex thing you could do, and compatible with various CPU operating modes.

[DrBearhands]

assuming cyclic overflows, i.e. INTMAX + 1 = INTMIN:
if INTMAX - y < x (equivalent to x + y > INTMAX without cycles)
then x + y = INTMIN + y - (INTMAX - x - 1)
ergo, rewriting the equations as
x' = x + y
y' = x' - y
x'' = x' - y'
we get:
x' = INTMIN + y - (INTMAX - x - 1)
y' = x' - y
y' = INTMIN - (INTMAX - x - 1)
y' = INTMIN + 1 - INTMAX + x
y' = x
x'' = INTMIN + y - (INTMAX - x - 1) - y'
x'' = INTMIN + y - (INTMAX - x - 1) - x
x'' = INTMIN + y - INTMAX + x + 1 - x
x'' = INTMIN + 1 + y - INTMAX
x'' = y

Overflows schmoverflows.

EDIT: Might be worth noting that this approach and the bitwise operator are essentially the same thing. Combine two things in a way that is reversible if you have either of the two originals.

[Theofanis Despoudis]

Unfortunately that works in theory but in practice and most compilers do not guarantee that behavior. For example:

Java: Will back cycle to -2147483648
Javascript: will eventually print infinity if the value is too high
Go: Will not compile

[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".

[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?" :)

[Zuodian Hu]

Very contrived, only works on ARM, not even acceptable by all C compilers, but you never constrained the problem that way!

void swap(int* a, int* b) {
    __asm volatile (
        "MOV R2, R1 \n"
        "MOV R1, R0 \n"
        "MOV R0, R2 \n"
    );
}

[Zuodian Hu]

Oh and as prplz mentioned, any self-respecting compiler nowadays will use only registers any way you decide to implement this little stub of a function. Yes yes, the question is very contrived too, but hey.

[Nick Karnik]

Aren't you using a third register though?

Are you're thinking that you can do that because it's not in RAM?

[Zuodian Hu]

The way the question is formulated, you're limited by having a certain amount of memory. Any register use doesn't count against that at all.

[Zuodian Hu]

I went to bed, and realized that my answer is wrong. Exchanging the values in register is completely invisible to the function caller. Here's the correct answer.

void swap(int* a, int* b) {
    __asm volatile {
        "LDR R2, [R0] \n"
        "LDR R3, [R1] \n"
        "STR R2, [R1] \n"
        "STR R3, [R0] \n"
    }
}

Further, as R0-R3 are all caller-save registers in the ARM ABI, the function body, excluding the function entry stack shenanigans, uses zero memory.

[Phuc Duong]

Can I use pointers?

x:=1
y:=2
*(&x) = y
*(&y) = x

[Nick Karnik]

You can do anything as long as you swap the values and don't create more memory.

In your solution, x is overwritten by y so it isn't swapping both the values.

[Phuc Duong]

Ah, I thought it wouldn't work but at midnight computer tells you lies :).

The multiple assignment in Go ( assuming C/C++ are the same mechanism, and i see Python below) works though.

x, y = y,x

[Jason Steinhauser]

Someone has already posted my XOR solution 😄 this is one we occasionally ask in interviews, and it's one of my favorite abstract problems

[Nick Karnik]

Wouldn't that have upstream effects on the program?

[tux0r]

Not after you have replaced y in the second step.

[Robin Kretzschmar]

Thanks for this post, I also take the modern "common" hardware for too granted.
Good reminder :)

[yev]

x ^= y;
y ^= x;
x ^= y;

[dean]

x := 5
y := 5
swap(&x, &y)
fmt.Println(x, y) // uh oh, they are both zero!

[yev]

I've written my answer with C in mind, and it does explain how it works if you try the calculation by hand: onlinegdb.com/B1IY6hFK7

#include <stdio.h>

int main()
{
    int a = 77;
    int b = 42;
    printf("a: %d, b: %d \n", a, b);

    swap(&a, &b);
    printf("after swap \n");
    printf("a: %d, b: %d", a, b);

    return 0;
}

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

When both a and b has the same value: onlinegdb.com/r1WeypFF7

Result may vary depending on the language compiler, you might have to adjust the snippet according to your language's nuances.