RE: swapping two numbers
"Larry Rosler" <[email protected]> Sun, 25 Jun 2006 00:31:19 -0700
| Newsgroups | gmane.comp.lang.perl.fun |
|---|---|
| Message-ID | <[email protected]> |
> From: Philippe "BooK" Bruhat [mailto:[email protected]] > Sent: Saturday, June 24, 2006 04:10 > To: [email protected] > Subject: Re: swapping two numbers > > > Le vendredi 23 juin 2006 à 17:40, Samy Kamkar écrivait: > > Although x could overflow in this case, where it wouldn't with an xor, > > right? > > I've quickly tried to overflow it, but I didn't manage to break it. > It looks like even if you overflow x with the first addition, you > cross the border in the other direction when doing the substraction. > > -- > Philippe "BooK" Bruhat The issue has nothing to do with overflow; everything to do with loss of precision. Subtraction of two nearly equal numbers, or addition of two numbers of opposite sign and nearly equal magnitude) followed by a second similar computation can produce results with few or no significant bits. The only correct way to perform these in-place swap operations is to treat the operands as bit patterns and use the xor operation. -- Larry Rosler mailto:[email protected] http://pobox.com/~Larry.Rosler