Swapping two Numbers without Temporary Variables

#1

Post by davesailer » Thu, Mar 24, 2022, 6:00 PM UTC

Swapping two Numbers without Temporary Variables
garrit.xyz

Re: Swapping two Numbers without Temporary Variables

#2

Post by throw_away » Thu, Mar 24, 2022, 6:50 PM UTC

This is a variation on xor-swap, but one that suffers from over(/under)flow

https://en.wikipedia.org/wiki/XOR_swap_algorithm#Variations

Re: Swapping two Numbers without Temporary Variables

#3

Post by everyone » Thu, Mar 24, 2022, 6:55 PM UTC

I remember just after college I applied for a .net job, when I came in for the interview they gave me a paper exam with a bunch of questions on how to do silly little tricks including that one specifically. I didn't take that job.

Re: Swapping two Numbers without Temporary Variables

#4

Post by Animats » Thu, Mar 24, 2022, 6:57 PM UTC

throw_away wrote: post #2

This is a variation on xor-swap, but one that suffers from over(/under)flow https://en.wikipedia.org/wiki/XOR_swap_algorithm#Variations

The classic use of XOR-swap was to traverse a tree without needing a stack. As you traverse the tree, the forward links are swapped with backward links, so you can find your way back. Used in the mark phase of some early garbage collectors.

Re: Swapping two Numbers without Temporary Variables

#5

Post by milliams » Thu, Mar 24, 2022, 7:01 PM UTC

Or, in Python

    a, b = b, a

Or Rust:

    (a, b) = (b, a);

Re: Swapping two Numbers without Temporary Variables

#6

Post by paxys » Thu, Mar 24, 2022, 7:04 PM UTC

milliams wrote: post #5

Or, in Python a, b = b, a Or Rust: (a, b) = (b, a);

These aren't algorithms. The language is still doing something under the hood to do the swap.

Re: Swapping two Numbers without Temporary Variables

#7

Post by jslaby » Thu, Mar 24, 2022, 7:05 PM UTC

milliams wrote: post #5

Or, in Python a, b = b, a Or Rust: (a, b) = (b, a);

or with a static variable

Re: Swapping two Numbers without Temporary Variables

#8

Post by manojlds » Thu, Mar 24, 2022, 7:16 PM UTC

paxys wrote: post #6

milliams wrote: post #5

Or, in Python a, b = b, a Or Rust: (a, b) = (b, a);

These aren't algorithms. The language is still doing something under the hood to do the swap.

Was that the problem statement? Come up with an algorithm to swap two numbers?

Re: Swapping two Numbers without Temporary Variables

#9

Post by Jerrrry » Thu, Mar 24, 2022, 7:23 PM UTC

Animats wrote: post #4

throw_away wrote: post #2

This is a variation on xor-swap, but one that suffers from over(/under)flow https://en.wikipedia.org/wiki/XOR_swap_algorithm#Variations

The classic use of XOR-swap was to traverse a tree without needing a stack. As you traverse the tree, the forward links are swapped with backward links, so you can find your way back. Used in the mark phase of some early garbage collectors.

can you explain this please (your comments are lovely btw)

Re: Swapping two Numbers without Temporary Variables

#10

Post by throwaway81523 » Thu, Mar 24, 2022, 7:23 PM UTC

Animats wrote: post #4

throw_away wrote: post #2

This is a variation on xor-swap, but one that suffers from over(/under)flow https://en.wikipedia.org/wiki/XOR_swap_algorithm#Variations

The classic use of XOR-swap was to traverse a tree without needing a stack. As you traverse the tree, the forward links are swapped with backward links, so you can find your way back. Used in the mark phase of some early garbage collectors.

That's pointer reversing but as I've seen it, it usually doesn't involve xor swap. It is still used in some gc's.