Swap two (string) variables without using a third
A beginner's challenge
A common, classic learning puzzle for new programmers to get them thinking about the building blocks of algorithms is this:
If you have two (integer) variables, how can you swap their values without using any third variable?
<?php
$a = 4;
$b = 7;
function swapValues(&$a, &$b)
{
// The puzzle is to figure out what goes in here, such that in the example inputs
// above, $a = 7 and $b = 4, without using any additional variables.
}
swapValues($a, $b);
echo $a, ' ', $b;
Now this puzzle, once you figure it out, is very easy to understand. It's just maths; we can do it with simple arithmetic.
<?php
$a = 4;
$b = 7;
function swapValues(&$a, &$b)
{
$a = $a + $b;
$b = $a - $b;
$a = $a - $b;
}
swapValues($a, $b);
echo $a, ' ', $b;
A tougher version
Let's add a fun twist to this challenge! What if the variables are strings?
$a = 'hello';
$b = 'world';
function swapValues(&$a, &$b)
{
// Can you swap these values without using a third variable,
// or any PHP library functions?
}
It may surprise you to learn this is also entirely possible, provided the strings are the same length.
Before we get to the solution, we need to understand a little more about binary. A string in PHP is just a sequence of bytes and a byte is 8 bits. The first letter of "hello", for example, "h" is stored as the number 104, represented in binary as (8 + 32 + 64), or 01101000.
The entire string "hello" can be represented in binary as 01101000 01100101 01101100 01101100 01101111.
The string "world" can be represented as 01110111 01101111 01110010 01101100 01100100.
Now we understand how the letters of these strings are stored as numbers, we can think about how we might swap them.
Bitwise operators
PHP, like most programming languages, supports performing operations on the individual bits of a number through its bitwise operators.
One operator in particular, XOR (aka "exclusive or") works like this: given two bits, if one of the bits is a 1 and the other is 0, the result is 1, otherwise the result is 0.
So 0 xor 1 = 1, 1 xor 0 = 1, 1 xor 1 = 0 and 0 xor 0 = 0.
An interesting mathematical consequence follows from this rule; if a xor b = c
, then b xor c = a
.
Try it:
1 xor 0 = 1
0 xor 1 = 1
0 xor 1 = 1
1 xor 1 = 0
Now look at what happens if we XOR each pair of bits in our binary representations of the first letters from "hello" and "world":
$a = 'h';
$b = 'w';
$c = $a ^ $b; // The ^ symbol is PHP's XOR operator
01101000 // $a
01110111 // $b
00011111 // $c = h XOR w
Remember that if $a ^ $b = $c
, then $b ^ $c = $a
. Which means using the bitmask we've created, we can derive either $a
or $b
from the bitmask $c
and the other value:
$mask = bindec('00011111'); // $mask = 31
$letter = 'w'; // $w = 01110111 = 119
$letter = $letter ^ $mask;
00011111
01110111
01101000 // XOR result, $letter is now 01101000 = 104 = 'h'
Solving our puzzle
Because we can use XOR to create a bitmask for each letter in "hello" and "world" which will allow us to transform one letter to the other, all that's left to solve our puzzle is to do this without using a third variable $c
to hold the bitmask.
$a = 'h'; // Remember, this is just the number 104
$b = 'w'; // And this is 119
$a = $a ^ $b; // $a is now 00011111 = 31
$b = $b ^ $a; // $b is now 01101000 = 104 = 'h'
$a = $b ^ $a; // $a is now 01110111 = 119 = 'w'
Because "hello" and "world" are both five bytes (or 40 bits), we can just go ahead and XOR the entire strings together like this:
$a = 'hello';
$b = 'world';
function swapValues(&$a, &$b)
{
$a = $a ^ $b;
$b = $b ^ $a;
$a = $b ^ $a;
}
swapValues($a, $b);
echo $a, ' ', $b;
// Outputs "world hello"
And thus we can swap two strings without using any third variable!
In conclusion
Bit of a random, geeky post I know, and not particularly useful in the real world - but understanding binary and bitwise operators certainly is.
Comments
All comments are pre-moderated and will not be published until approval.
Moderation policy: no abuse, no spam, no problem.
Recent posts
The difference between failure and success isn't whether you make mistakes, it's whether you learn from them.
musings coding
Recalling the time I turned down a job offer because the company's interview technique sucked.
musings
Buy this advertising space. Your product, your logo, your promotional text, your call to action, visible on every page. Space available for 3, 6 or 12 months.
Recalling the time I was rejected on the basis of a tech test...for the strangest reason!
musings
Why type hinting an array as a parameter or return type is an anti-pattern and should be avoided.
php
Leveraging the power of JSON and RDBMS for a combined SQL/NoSQL approach.
php
Really cool methods, but what about:
Easy, simple and works also for strings :-)
Editor's reply: I would argue for the specific purposes of the challenge, the array
[$a,$b]
is a third variable, it's just not a named variable.