Re: Re: Re: Swapping two values

[sauoq]

In languages like C (and not Perl) where it sometimes makes sense to use this method for swapping values, it will work just fine even if the values are the same. I'm unsure what you mean by "overlap." To see that it will work, try it with all four combinations of 2 bits:

 A | B | A = A^B | B = A^B | A = A^B | A | B 
===|===|=========|=========|=========|===|===
 0 | 0 | 0 = 0^0 | 0 = 0^0 | 0 = 0^0 | 0 | 0
---+---+---------+---------+---------+---+---
 0 | 1 | 1 = 0^1 | 0 = 1^1 | 1 = 1^0 | 1 | 0
---+---+---------+---------+---------+---+---
 1 | 0 | 1 = 1^0 | 1 = 1^0 | 0 = 1^1 | 0 | 1
---+---+---------+---------+---------+---+---
 1 | 1 | 0 = 1^1 | 1 = 0^1 | 1 = 0^1 | 1 | 1

See? It works fine even when the values are equal.

But, don't do it in perl!

-sauoq
"My two cents aren't worth a dime.";

[adrianh]

I think that the point the Anonymous Monk was making that it falls over badly if $a and $b refer to the same sequence of bits in memory. Consider:

# swap ($s, $p1, $p2, $n);
# in $s swap the $n bits at bit $p1 and $p2
sub swap {
    vec($_[0],$_[1],$_[3]) ^= vec($_[0],$_[2],$_[3]);
    vec($_[0],$_[2],$_[3]) = vec($_[0],$_[1],$_[3]) ^ vec($_[0],$_[2],
+$_[3]);
    vec($_[0],$_[1],$_[3]) = vec($_[0],$_[1],$_[3]) ^ vec($_[0],$_[2],
+$_[3]);
};

# swap first two and second two chars
my $string = "ABCD";
print "$string\n";
swap($string, 0,16,16);
print "$string\n";

The problem with code like this is that it falls down badly if the bits sequences being swapped overlap. Consider:

# swap first character with itself
swap($string, 0, 0, 8);

Anything XORed with itself is zero. Oops :-)

[sauoq]

You're probably right. The post makes some sense in that context. It's true, of course, that you can't reliably swap a string's characters in place using the XOR method. You can, however, swap pointers that point into the same string in memory without any problems. In any case, the method does have merit as an optimization in C. But not Perl! :-)

-sauoq
"My two cents aren't worth a dime.";

[Anonymous Monk]

Exactly. The optimization assumes that changing one variable does not change the other and vice versa. When they overlap in memory, this stops being true.