How to swap two variables without using a temporary variable

| 0 Comments | 0 TrackBacks
Swapping two variables in place without using a temporary variable (storage) seems to be a favourite question for some eccentric interviewers. I've been asked it on three separate occasions. The first two times I didn't know the answer and didn't bother looking it up. The third time I realized that perhaps I should figure this out.

The actual answer will be in the context of reversing all the words in a sentence without using a temporary variable. For example, the sentence "last night the DJ saved my life" should be reversed to "life my saved DJ the night last".

The swapping of two variables using no extra storage is done using a technique called the XOR swap algorithm. It is explained by many people over the internet. This is wikipedia's: http://en.wikipedia.org/wiki/XOR_swap_algorithm

so if A=1 0 1 1 0 1 0 0 1 1, and B= 1 1 0 1 1 0 1 0 0 0, then the swap happens in three XOR operations:

A = A ^ B;
B = A ^ B;
A = A ^ B;

The hat sign, ^, is the Perl notation for XOR. Just to show the three XOR operations:

# First step is to XOR the two variables and store the result in A.
A = A ^ B = 1 0 1 1 0 1 0 0 1 1 ^ 1 1 0 1 1 0 1 0 0 0 = 0 1 1 0 1 1 1 0 1 1;

# Now use the new A and XOR it with B, replacing B.
B = A ^ B = 0 1 1 0 1 1 1 0 1 1 ^ 1 1 0 1 1 0 1 0 0 0 = 1 0 1 1 0 1 0 0 1 1;

# Finally, XOR A and B again, storing the result in A.
A = A ^ B = 0 1 1 0 1 1 1 0 1 1 ^ 1 0 1 1 0 1 0 0 1 1 = 1 1 0 1 1 0 1 0 0 0;

Now A and B are swapped. The reversing of the words in a sentence happens in two steps. First reverse all letters within the sentence. Second, reverse all letters within each word. For the above example, the first step produces this string:

e f i l   y m   d e v a s   J D   e h t   t h g i n   t s a l

Reversing each word gives the desired output "life my saved DJ the night last".

I ignore the beginning and ending white spaces and only swap non-white space characters. Then to figure out each word I use a two variables as cursors, i and j. Where the integer i denotes the beginning position for the reversing and j the ending position. So a reverse happens between i and j. And i should never be bigger than j.

#!/usr/bin/perl


use strict;

use warnings;


sub reverse_{

   my $s = shift;

   my $i = shift;

   my $j = shift;


   for( ; $i < $j ; $i++, $j--){ 

       $s->[$i] = $s->[$i] ^ $s->[$j];

       $s->[$j] = $s->[$i] ^ $s->[$j];

       $s->[$i] = $s->[$i] ^ $s->[$j];

    }

}


sub main{

   my $s = $ARGV[0] || 'last night the DJ saved my life';


   my @s = split(//, $s);

   my $ssize = scalar(@s);


   # ignore beginning white spaces

   #

   my $i=0;

   while(1){

      if($i > $#s){ #string is all white spaces

          print "string is empty: '@s'\n"

          exit;

      }elsif($s[$i] =~ /\s/){

           $i++; 

      }else{

           last;

      }

   }


   # ignore trailing white spaces

   #

   my $j = $#s;

   while(1){

      if($s[$j] =~ /\s/){

          $j--;

      }else{

          last;

      }

   }

   # reverse @s until the end

   reverse_(\@s,$i, $j) if($j > $i);

   print "all letters reversed: @s\n";

   

   while($i < scalar(@s)){

        if($s[$i] =~ /\s/){

            $i++;

            next

        }

        if($i == $#s){ last; }

        $j=$i + 1;


        while (1){

             if($j == $#s){

                  last;

             }elsif($s[$j] =~ /\s/){

                  $j--; 

                  last;

             }else{

                  $j++;

             }

        }

        if($s[$j] =~ /\s/){

             print $s[$j];

             $j--;

        }

        reverse_(\@s,$i, $j) if ($j > $i);

        $i = $j + 1;

   }

   foreach my $w (@s){

      print "$w";

   }

   print "\n";

}

main();


farhadsaberi$ ./reverse_words.pl "it's the economy stupid"
all letters reversed: d i p u t s   y m o n o c e   e h t   s ' t i
stupid economy the it's

farhadsaberi$ ./reverse_words.pl "   the yellow     balloon "
all letters reversed:       n o o l l a b           w o l l e y   e h t  
    balloon     yellow the 


The second example shows that the beginning and ending white spaces as well white spaces between words are preserved.

No TrackBacks

TrackBack URL: http://www.farhadsaberi.com/cgi-bin/mt/mt-tb.cgi/25

Leave a comment

About this Entry

This page contains a single entry by Farhad Saberi published on October 2, 2013 2:52 PM.

Perl detach process daemon was the previous entry in this blog.

Find recent content on the main index or look in the archives to find all content.