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

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