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

71–80 of 93 posts

Re: Swapping two Numbers without Temporary Variables

#71

Post by xxs »

StillBored wrote: post #65
xxs wrote: post #27

Earlier quoted context omitted.

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.

6502's xor is not efficient (IIRC) for swapping because the result is always stored in A, and the second operation is either immediate or memory. AKA it is to much an accumulator machine, similarly for 6800 even though the xor can target multiple registers the source still has to be memory, so while its possible to create an xor swap, the alternatives are going to be more efficient. Z80+/8080/etc have an exchange.. I…

About 6502 - that was my point, I can't think of a such processor. 6502 uses the accumulator for everything, except inc/dec on x and y.

Hmm, Arm v1 - that's something I don't know. The earliest Assembly I know is the v6.

Re: Swapping two Numbers without Temporary Variables

#72

Post by wolpoli »

setuids wrote: post #56
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

I never considered that this algorithm would work so well with unsigned int. Looks like I learn something new today.

Re: Swapping two Numbers without Temporary Variables

#73

Post by wolpoli »

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.

I am not a Javascript expert: Would the XOR version work in Javascript where numbers are Doubles? Perhaps that's the reason the article used addition/subtraction instead?

Re: Swapping two Numbers without Temporary Variables

#74

Post by aix1 »

wolpoli wrote: post #73
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.

I am not a Javascript expert: Would the XOR version work in Javascript where numbers are Doubles? Perhaps that's the reason the article used addition/subtraction instead?

You really wouldn't want to use any of these algorithms on doubles (certainly not in the general case).

Think of NaNs, infinities, operands that are vastly different in magnitude (e.g. try calculating (1e10 + 1e-10 - 1e10)) and so on.

Re: Swapping two Numbers without Temporary Variables

#75

Post by prophesi »

anyfoo wrote: post #57
prophesi wrote: post #39

Earlier quoted context omitted.

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.

For future reference, don't assume everyone on HN writes C/C++. I know what those terms mean but I was trying to point out that OP probably meant the exact same thing.

Telling someone who doesn't know what widening a variable means that they meant widening a variable without explaining what widening a variable means helps no one.

(Plus adding 1 bit to the "bit size" of a variable _does_ double the base 10 size of the variable if you want to be really pedantic)

Re: Swapping two Numbers without Temporary Variables

#76

Post by anyfoo »

prophesi wrote: post #75
anyfoo wrote: post #57

Earlier quoted context omitted.

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.

For future reference, don't assume everyone on HN writes C/C++. I know what those terms mean but I was trying to point out that OP probably meant the exact same thing. Telling someone who doesn't know what widening a variable means that they meant widening a variable without explaining what widening a variable means helps no one. (Plus adding 1 bit to the "bit size" of a variable _does_ double the base 10 size of the…

I think it's pretty intuitive that the size of a variable is the amount of memory it takes, while the range of a variable describes the bounds of the values it can represent.

This is consistent with other uses: The size of an array, the size of a data structure in general, the size of a file... In all of those you are concerned about how much memory or disk space is taken.

So I think calling the range "size" is counterintuitive and gives the wrong idea, and I do not agree that the "base 10 size" of a variable is equivalent to its range. (What does "base 10" have to do with it anyway? The range is doubled no matter what base we're operating in.)

Re: Swapping two Numbers without Temporary Variables

#78

Post by [deleted] »

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]`?

[deleted]

Re: Swapping two Numbers without Temporary Variables

#80

Post by jayceedenton »

dimsumbytes wrote: post #64
rcfox wrote: post #55

Earlier quoted context omitted.

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.

Again, not trying to be that guy, but technically it still breaks: a = -0.0 b = 0.0

I think you might be that guy :)
Post reply on HN