SPUG: swapping two numbers

DeRykus, Charles E charles.e.derykus at boeing.com
Fri Jun 23 15:25:08 PDT 2006

M> I was digging through some old code and came across a proof that I
had done 
M> that you can swap two numbers in place (i.e. without using an
M> temporary value).

M> Of course, in Perl, we can just do this:
M>  ($x, $y) = ($y, $x)

M> But I was challenged (at a GSLUG meeting) to do it in a
language-independent way.  
M> Since the guy mentioned he had known the solution for 20+ years, I
descended into 
M> bit-flipping land and came up with a solution.

M> (BTW:  I'm not sure why my first gut reaction was right.  I guess
I've been in the 
M> business long enough.  There's no way my conscious mind came up with
this solution!!!  
M> Nevertheless, my subconscious came up with this solution within about
3 seconds.  
M> Brains are amazing!!!)

M> I present it here as an interesting piece of code:

M> #! /usr/bin/perl -w

M> use warnings;
M> use strict;

M> my $iterations = shift @ARGV || 10;

M> for (my $i = 0; $i < $iterations; $i++) {
M>   my ($orig_a, $a) = (int(rand 1000)) x 2;
M>   my ($orig_b, $b) = (int(rand 1000)) x 2;

M>   # Original solution:
M>   #    $a = $a ^ $b;
M>   #    $b = $b ^ $a;
M>   #    $a = $a ^ $b;
M>   # Refined to use op=
M>   #    $a ^= $b;
M>   #    $b ^= $a;
M>   #    $a ^= $b;

M>   # Utilizing op= value, factored onto one line
M>   #    $a ^= ($b ^= ($a ^= $b));
M>   # Refined to remove unnecessary parens
M>    $a ^= $b ^= $a ^= $b;

'Algorithms with Perl' has your original, refined solution in the
Crytography chapter (pg. 539 'Swapping values with XOR') but not
the nice, de-cluttering refinement.

Charles DeRykus 

More information about the spug-list mailing list