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

51–60 of 93 posts

Re: Swapping two Numbers without Temporary Variables

#51

Post by a_e_k »

layer8 wrote: post #43
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’…

True; I probably overstated it in terms of idiom recognition (compiler enthusiast, but by no means expert). I suspect that a similar SSA or data flow analysis combined with some judicious rewrite rules like (X ^ Y) ^ Y -> X [0] are enough for the xor swap trick as well.

[0] https://github.com/gcc-mirror/gcc/blob/9fdac7e16c940fb6264e6...

Re: Swapping two Numbers without Temporary Variables

#53

Post by bastawhiz »

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.

Where do you think the intermediate results of doing math on the two variables are kept?

Re: Swapping two Numbers without Temporary Variables

#54

Post by groby_b »

makeset wrote: post #45
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.

That'd be because they are the only bitwise operations under which integers form an Abelian group.

Specifically, AND and OR lack an inverse operation.

Re: Swapping two Numbers without Temporary Variables

#55

Post by rcfox »

dimsumbytes wrote: post #42

Sorry to be that guy, but this doesn't work in languages that use floats: let a = 9007199254740992; let b = 1; a = a + b b = a - b a = a - b a // 1 b // 9007199254740991

By the same logic, you could argue that `x++` doesn't work work for floats. As long as your intermediate values stay between `Number.MAX_SAFE_INTEGER` and `Number.MIN_SAFE_INTEGER`, you'll be fine.

Re: Swapping two Numbers without Temporary Variables

#56

Post by setuids »

wolpoli wrote: post #15

The person that developed this trick is obviously familiar with the Mathematical properties of numbers. But this is the wrong approach from many prospective, including the impact to performance, the potential of under/overflow, and the lack of readability.

> under/overflow Assuming the 2 variables are treated as unsigned ints, even with under/overflows the algorithm works, since if a=a+b overflows, then b=a-b is guaranteed to underflow, thus returning the original a. The overflowed bit is irrelevant here

Re: Swapping two Numbers without Temporary Variables

#57

Post by anyfoo »

prophesi wrote: post #39
nayuki wrote: post #36

Earlier quoted context omitted.

No - to deal with overflow, the variables need to be widened by 1 bit.

Not sure if this is what the OP meant, but adding a bit is effectively doubling the size. 16 bits = 65535. 17 = 131071.

I'm reasonably certain you'd more commonly say that the range is doubled. When we say "size", we usually mean the "width" of the variable, as e.g. demonstrated by the "sizeof()" operator in C, which gives the size/width in bytes[1].

[1] Actually multiple of sizeof(char), where sizeof(char) is defined as 1. And that's technically not 1 byte everywhere, but most of the time nowadays it is.

Re: Swapping two Numbers without Temporary Variables

#58

Post by mkdirp »

sam_goody wrote: post #46

This is JS, so you should use de-structuring to swap in one easy-to-follow step [1]: let a = 5; let b = 10; [a,b] = [b,a]; console.log(a,b) // 10, 5 [1]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

Doesn't this create a new (temporary) array of value `[b,a]`?

Re: Swapping two Numbers without Temporary Variables

#59

Post by ncmncm »

StillBored wrote: post #32
Animats wrote: post #4

Earlier quoted context omitted.

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.

Yah, or just store both the forward and backwards links in a single variable by xoring the forward and backward links together and storing it. Then the list traversal direction is picked by selecting either the head or tail and starting the operation. Halves the cost of a doubly linked list, while allowing the same function to be used for forward and backwards traversal.

Halves the cost provided that touching that many cache lines is free. Even after you rewrite them back to how they were, the cache doesn't know, so has to write back every line.

If it's a balanced tree, you need only log(n) stack entries you can statically provision, and then other threads can traverse the tree at the same time.

Most of the traditional optimizations turned into pessimizations decades back. That has been a good thing.

Re: Swapping two Numbers without Temporary Variables

#60

Post by ncmncm »

mkdirp wrote: post #58
sam_goody wrote: post #46

This is JS, so you should use de-structuring to swap in one easy-to-follow step [1]: let a = 5; let b = 10; [a,b] = [b,a]; console.log(a,b) // 10, 5 [1]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

Doesn't this create a new (temporary) array of value `[b,a]`?

If it does, that was optimal. If it doesn't, that was optimal.

Outsmarting your optimizer is harder than that nowadays.

Post reply on HN