Swap Numbers

Standard

 

Write a function that takes two numbers and returns the numbers in the swapped order without using temporary memory?

The catch here is we are not allowed to use a temporary memory. So the following solution is not acceptable:

# NOT OKAY
def swapper(a, b)
    t = a
    a = b
    b = a
    [a, b]
end

# btw, it is cheating to just return [b, a].

So how to we store information about two numbers in one ‘buffer’? Bit manipulation is the answer.

The thing you need to remember is the XOR operator. We note that if we XOR a number with itself, we get 0. Let us use this to our benefit. We can swap the two numbers if we can rewrite this equation and somehow not lose any information

# a is the first number, b is the second number
a = a^b^a
b = b^a^b

Note that in the first case we XOR ‘a’ twice to get rid if it. So essentially, we are saying a = b. But this will screw up our second equation as it will become

b = b^(b)^b

And that is just equal to b = b. But, if we have an intermediate step, we can rewrite our function

def swapper(a, b)
  a = a^b
  b = b^a # which is b^(a^b) = a
  a = a^b # which is (a^b)^a = b
  [a, b]
end

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s