DEV Community

loading...
Cover image for How can you swap two variables without using a third?

How can you swap two variables without using a third?

theoutlander profile image Nick Karnik Updated on ・1 min read

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.

Discussion

pic
Editor guide
Collapse
sadarshannaiynar profile image
Adarsh
if (x == y) return;
x = x ^ y
y = x ^ y
x = x ^ y

Bitwise operators for the win.

Collapse
nestedsoftware profile image
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.

Collapse
theoutlander profile image
Nick Karnik Author

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.

Collapse
ptdecker profile image
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.

Collapse
d4vecarter profile image
Collapse
theoutlander profile image
Nick Karnik Author

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

Collapse
almostconverge profile image
Peter Ellis

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

Thread Thread
theoutlander profile image
Nick Karnik Author

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

Thread Thread
almostconverge profile image
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.

Collapse
codemouse92 profile image
Jason C. McDonald

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

Collapse
sadarshannaiynar profile image
Adarsh

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

Collapse
tux0r profile image
tux0r

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

Collapse
theodesp profile image
Theofanis Despoudis

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

Collapse
drbearhands profile image
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.

Thread Thread
theodesp profile image
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

Collapse
tux0r profile image
tux0r

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

Thread Thread
theodesp profile image
Theofanis Despoudis

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

Thread Thread
lewiscowles1986 profile image
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).

Thread Thread
theodesp profile image
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!

Thread Thread
lewiscowles1986 profile image
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.

Collapse
simonhaisz profile image
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.

Collapse
ptdecker profile image
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 253 - 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.

Collapse
shoupn profile image
Nick Shoup

Algebra for the win.

Collapse
leoat12 profile image
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

Collapse
sathwikmatsa profile image
Sathwik Matsa

Wait.. readability of your code is also important!

Thread Thread
theoutlander profile image
Nick Karnik Author

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

Collapse
Sloan, the sloth mascot
Comment deleted
Collapse
tux0r profile image
tux0r

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

Nope, still true.

Thread Thread
sadarshannaiynar profile image
Adarsh

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

Collapse
theoutlander profile image
Nick Karnik Author

Can you please elaborate on that?

Collapse
joshichinmay profile image
Chinmay Joshi

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

Thread Thread
dean profile image
Dean Bassett

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
}
Thread Thread
tux0r profile image
tux0r

Which would be inefficient, thus not recommended.

Thread Thread
dean profile image
Dean Bassett

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

Thread Thread
tux0r profile image
tux0r

You could just write the registers yourself then...

Collapse
cathodion profile image
Dustin King

x, y = y, x #

Collapse
cathodion profile image
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.

Collapse
zhu48 profile image
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.

Thread Thread
theoutlander profile image
Nick Karnik Author

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?

Thread Thread
cathodion profile image
Dustin King

C memory layout:

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.

Thread Thread
theoutlander profile image
Nick Karnik Author

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. 👏👏👏

Collapse
zhu48 profile image
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.

Thread Thread
cathodion profile image
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".

Collapse
theoutlander profile image
Nick Karnik Author

It creates more memory though.

Collapse
shoupn profile image
Nick Shoup

Not all languages have this type of assignment. But this is probably the simplest.

Collapse
theoutlander profile image
Nick Karnik Author

Do you know how this is implemented internally?

Thread Thread
shoupn profile image
Nick Shoup

Switching reference pointers of memory allocation? Python does this type of variable assignment, and tbh, I don't like to use it.

Thread Thread
theoutlander profile image
Nick Karnik Author

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

StackOverflow Answer

Thread Thread
almostconverge profile image
Peter Ellis

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

Collapse
yaser profile image
Yaser Al-Najjar

Only two options, either using memory or CPU

  1. Memory = third variable
temp = x
x = y
y = temp
  1. CPU = Swap algorithms

like XOR swap (bullet-proof solution)

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

Or addition & subtraction (which is not bullet-proof when dealing with a 32-bit register that would need extra care with overflow)

x += y
y = x - y
x -= y
Collapse
dean profile image
Dean Bassett

XOR swap is NOT bullet proof, you need to check if x == y first. If x == y, then the function sets both values to zero.

Collapse
johnfound profile image
johnfound

No, it will not. Let set x=5, y=5.

x = x xor y = 5 xor 5 = 0
y = y xor x = 5 xor 0 = 5
x = x xor y = 0 xor 5 = 5

It is a nop actually, but still correct.

Collapse
lexlohr profile image
Alex Lohr

Since xor and subtraction were already mentioned, may I chime in with a circular shift over the 64 bit value of the whole function memory?

Collapse
amexboy profile image
Amanuel Nega

This one is different, but how exactly would you implement it in a programming language?

Collapse
lexlohr profile image
Alex Lohr

Basically, it works like this (x64 assembler):

mov rax, [m64]
ror rax, 32
mov [m64], rax

Thread Thread
amexboy profile image
Amanuel Nega

No, I mean on a high level programming language which you have no idea where is stored.

Even for an assembly, the two variables could potentially be stored in two different registers. But we're going to assume not!

Cool idea anyways

Collapse
drbearhands profile image
DrBearhands

I love you

Collapse
zhu48 profile image
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"
    );
}
Collapse
zhu48 profile image
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.

Collapse
zhu48 profile image
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.

Collapse
theoutlander profile image
Nick Karnik Author

Aren't you using a third register though?

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

Thread Thread
zhu48 profile image
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.

Collapse
vycoder profile image
yev
x ^= y;
y ^= x;
x ^= y;
Collapse
dean profile image
Dean Bassett
x := 5
y := 5
swap(&x, &y)
fmt.Println(x, y) // uh oh, they are both zero!
Collapse
vycoder profile image
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.

Collapse
jjjjcccjjf profile image
endan
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 */
Collapse
gmartigny profile image
Guillaume Martigny

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

Collapse
svenluijten profile image
Sven Luijten
// Since PHP 7.1:
[$b, $a] = [$a, $b];

// Or before 7.1:
list($b, $a) = [$a, $b];
Collapse
asciidev profile image
Samuel Raphael
[a, b] = [b, a]
Collapse
robencom profile image
robencom

I wrote the code based on the title only :D, i.e. swapping any 2 variables' values (any type) without using a third one:

Having $x and $y:

$x .= "-" . $y;
$y = explode("-", $x)[0];
$x = explode("-", $x)[1];

Collapse
amexboy profile image
Amanuel Nega

You only have 8 bytes remember?, this string manipulation takes more than that

Collapse
codevault profile image
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.

Collapse
theoutlander profile image
Nick Karnik Author

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)

Collapse
codevault profile image
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.

Thread Thread
theoutlander profile image
Nick Karnik Author

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

Collapse
bgadrian profile image
Adrian B.G.

The math trick works for numbers, but in Go:

a,b = b,a

(I think at the assembly level it uses a 3rd registry, but I'm not sure)

Collapse
updated_tos profile image
Null

Same in Ruby.

Collapse
kritner profile image
Russ Hammett

No idea if this counts

int x = 4242;
int y = 800000;

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

I'm sure this can be improved, but trying to get other stuff done ATM :D

working demo: dotnetfiddle.net/hP6T94

Collapse
theoutlander profile image
Nick Karnik Author

Thanks for the working demo! That is the correct solution. :)

Collapse
justingolden21 profile image
Justin Golden

x,y = y,x;

Syntaxic sugar :)

Collapse
liloow profile image
Tom

No need to go very far... and it will never cause overflow

x.__proto__.y = y
y.__proto__.x = x
x = x.y 
y = y.x
Collapse
jjjjcccjjf profile image
endan

$a = 7;
$b = 9;

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

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

/* scratches head */
Collapse
asparallel profile image
AsParallel

This challenge is to perform the transform reusing only the original pointers. Try again. :)

Collapse
idanarye profile image
Idan Arye
void swap(int* a, int* b) {
    write(open("swapfile", O_WRONLY | O_SYNC), a, sizeof(*a));
    *a = *b;
    read(open("swapfile", O_RDONLY), b, sizeof(*b));
}
Collapse
sriharsha32 profile image
SriHarsha Sreenath

Love your thinking. Nobody ever said you can't write to file and read it back :D

Collapse
almostconverge profile image
Peter Ellis

This is a nice puzzle to work out.

Another interesting(?) lesson is that beyond saving space, once this solution used to really be faster than the "naive method", but on modern CPUs that is no longer the case.

Collapse
josephscade profile image
josephscade

Let's say the two values are in the EAX and EBX registers. Here is the fastest :

push eax
push ebx
pop eax
pop ebx
Collapse
moopet profile image
Ben Sinclair

Here's a warm-up interview question that I ask every candidate.

I've seen this question come up a lot, along with fizzbuzz or "write a sorting function" and I'm not sure it's useful anymore.

It's a purely academic problem that touches on several different concepts, none of which are going to be used by 99% of programmers these days.

Why do you ask this question? What do people's different answers tell you, or are you more looking for how people attempt to solve it (if they've not heard it before) or how quickly they regurgitate a stock solution (if they have?)

If I asked this, and someone answered quickly (they already know why the dead man in the desert is lying next to an unopened pack...) then I'd follow up with something asking when they had ever had to do this in real life, or even if they could come up with three examples of situations where it would be a useful thing to do in real life. If they couldn't, then I don't think I would have learned anything useful about them.

What do you get out of it?

Collapse
theoutlander profile image
Nick Karnik Author

Good question! I used to ask this as a warm-up question back in the days at the beginning of an interview. (However, I've also used it in recent interviews after this post). I've never used this question to influence the outcome of the interview. It's merely conversational and a segue into academics to pique their interest into a deeper technical conversation.

If the candidate has heard the question before, I will follow up with a question around if the solution handles overflow when numbers are large and also dive a bit into perf. We may dive into when and if this solution might be needed for specific use-cases. The reality is that the compiler optimizes the code better when using a temporary variable.

If they haven't heard the question before, it gives me a chance to assess how they work through the problem and helps me find an appropriate role for them if the interview is somewhat generic. If they dislike that problem or find it difficult to solve it, they are most likely not going to enjoy working on hardware/firmware. Most people who solve it really enjoy the problem and in my experience have performed quite well on the job.

Recently, I observed that this question is part of the prep material online and most people have seen it, so there's not much value in asking it. I still do it for fun sometimes.

Anyway, I agree with your comment though.

Collapse
yujiri8 profile image
Ryan Westlund

(Posting before reading the other comments) I came up with two solutions, not sure if there's any reason either would be considered superior:

a = a + b
b = b - a
a = a + b
b = -b
a = a + b
b = b + a
a = b - a
b = b - 2*a
Collapse
leneko profile image
leNEKO

In python

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

am i right ?

Collapse
leneko profile image
leNEKO

oh shorter,

b ^= a
a ^= b
b ^= a
Collapse
leneko profile image
leNEKO

So now, what is the second step ? :)

Collapse
kspeakman profile image
Kasey Speakman

This is your first step in becoming a Computer Scientist!

I think I must have skipped a few steps. The only occasion I've had to use such tricks is when playing Zachtronics games like TIS-100 or Shenzhen IO. I hope you are interviewing for embedded systems programmers. ;-)

Collapse
sivaiah587 profile image
sivaiah587

JAVA

int a=5;
int b=10;
a=a+b;
b=a-b;
a=a-b;
System.out.println(a);//10
System.out.println(b);//5
String s1="java1";
String s2="java2";
s1=s1+s2;
s2=s1.substring(0,(s1.length()-s2.length()));
s1=s1.substring(s2.length());
System.out.println(s1);//java2
System.out.println(s2);//java1

Collapse
isenthil profile image
Senthil Kumar

Here's my code snippet showing how we can swap two numbers without using temporary variable at coderseditor.com/?id=185

using System;

namespace CodeSample
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Swap Number Sample");
int number1, number2;
Console.WriteLine("Enter the First Number : ");
number1 = int.Parse(Console.ReadLine());
Console.WriteLine("Enter the Second Number : ");
number2 = int.Parse(Console.ReadLine());
number1 = number1 - number2;
number2 = number1 + number2;
number1 = number2 - number1;
Console.WriteLine("First Number is " + number1);
Console.WriteLine("Second Number is " + number2);
Console.Read();
}
}
}

Collapse
eerk profile image
eerk

The Law of Gravity is also just an observation :)

Collapse
juanfrank77 profile image
Juan F Gonzalez

By using the ES6 destructuring assignment, that's how I would do it.

Collapse
theoutlander profile image
Nick Karnik Author

Does this solution meet memory constraints?

Collapse
juanfrank77 profile image
Juan F Gonzalez

In general, it does unless you're talking about very large ones.

Collapse
Sloan, the sloth mascot
Comment deleted
Collapse
theoutlander profile image
Nick Karnik Author

The entire swap ends up using three registers I think.

Collapse
darksmile92 profile image
Robin Kretzschmar

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

Collapse
bennypowers profile image
Benny Powers 🇮🇱🇨🇦
let x = 1
let y = 2
[x, y] = [y, x]
x // 2
y // 1