Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Swapping two Numbers without Temporary Variables

garrit.xyz

Post reply on HN
Print view View original

41–50 of 93 posts

Re: Swapping two Numbers without Temporary Variables

#41

Post by kevin_thibedeau »

xxs wrote: post #27
StillBored wrote: post #20

I think the more accepted way for a long time has been to use xor. https://en.wikipedia.org/wiki/XOR_swap_algorithm Its better in a number of ways, and since each bit is independent, it could actually be faster on really low end/old processors. Although these days just about any modern OoO processor will just detect swaps (even if there isn't an actual instruction) and the renamer makes it zero cost.

The only weird thing is that the article has managed to reach the front page. I was under the impression all number (and pointer) swap methods are very well known - with xor being the most applicable. Edit: I am hard pressed to think of an Assembly that doesn't have exchange (swap) between registers - e.g. 6502, but has a xor instead.

I had it as an interview question a few years ago. I explained it before the whiteboard was complete but many people aren't necessarily familiar with such things.

Re: Swapping two Numbers without Temporary Variables

#43

Post by layer8 »

a_e_k wrote: post #38

Behold!, as it all becomes the same thing in C++ with optimizations on: https://godbolt.org/z/joh1jhdhq Good production compilers recognize all these swap idioms and will compile them down (i.e., canonicalize them) to the same thing. In the case of things like swapping by adding and xoring, they'll often undo the cleverness and just use temporary registers anyway. These are the kinds of micro-optimizations that compi…

I don’t think the compilers recognize the specific idiom here, but instead (what you also say) perform normalizations (e.g. into static single assignment form), expression analysis and elimination, yielding the same result. For the present case, I’d imagine a sequence of transformations like this:

Convert into SSA:

    c = a + b;
    d = c - b;
    e = c - d;
    b’ = d;
    a’ = e;
Eliminate c:

    d = a + b - b;
    e = a + b - d;
    b’ = d;
    a’ = e;
Simplify d:

    d = a;
    e = a + b - d;
    b’ = d;
    a’ = e;
Eliminate dependency of e on d:

    d = a;
    e = a + b - a;
    b’ = d;
    a’ = e;
Simplify e:

    d = a;
    e = b;
    b’ = d;
    a’ = e;
Eliminate d:

    e = b;
    b’ = a;
    a’ = e;
…resulting in the normal swap.

Re: Swapping two Numbers without Temporary Variables

#45

Post by makeset »

StillBored wrote: post #20

I think the more accepted way for a long time has been to use xor. https://en.wikipedia.org/wiki/XOR_swap_algorithm Its better in a number of ways, and since each bit is independent, it could actually be faster on really low end/old processors. Although these days just about any modern OoO processor will just detect swaps (even if there isn't an actual instruction) and the renamer makes it zero cost.

XNOR is the (only) other binary operator that also works.

Re: Swapping two Numbers without Temporary Variables

#47

Post by sgeisenh »

a_e_k wrote: post #38

Behold!, as it all becomes the same thing in C++ with optimizations on: https://godbolt.org/z/joh1jhdhq Good production compilers recognize all these swap idioms and will compile them down (i.e., canonicalize them) to the same thing. In the case of things like swapping by adding and xoring, they'll often undo the cleverness and just use temporary registers anyway. These are the kinds of micro-optimizations that compi…

This example is kind of funny in a compiled language because a lot of modern compilers use a static single assignment (SSA) form as an intermediate representation. SSA effectively creates temporaries for each subsequent assignment operation. This helps with data-flow analysis but also makes it so that code like in the post can actually be less space efficient without optimizations in compiled languages.

Re: Swapping two Numbers without Temporary Variables

#49

Post by Thiez »

jslaby wrote: post #7
milliams wrote: post #5

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

or with a static variable

Congratulations, your program is now thread-unsafe because you thought using a temporary variable is expensive :-p using mutable static variables is a terrible idea in most situations.

Re: Swapping two Numbers without Temporary Variables

#50

Post by Thiez »

abainbridge wrote: post #35
baseballdork wrote: post #22

Earlier quoted context omitted.

Indeed, both the algorithm in the article, the rust suggestion, and even the naive solution compile to the same instructions[1]. [1] - https://godbolt.org/z/1P98ss37P

That uses 4 registers and a stack!

You can't do better with a non-inlined function.
Post reply on HN