Hacker News Reader

Comment by StillBored | Hacker News Reader

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.

View on HN

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.

https://xkcd.com/1053/

Indeed, I first learned about xor-swap from an example in the IBM System/360 Principles of Operations manual, circa 1968. (For some funky reason I don't understand, the Programming Examples section vanished from later editions of PrincOps.) I can't see any reason for wanting to use arithmetic 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.

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 suspect it might be useful on ArmV1 because xor can operate between registers and it doesn't (IIRC) have an xchng. Although Arm wasn't nearly register starved enough, nor does it have special register uses (index vs accumulator, etc) for a trick like this to be really useful.

PS: The fastest way to swap a register pair on 6502 is probably storing the first register into the instruction stream for an immediate load, then a register, register transfer, followed by the immediate load. Bonus if the code is running in the zero page, saving a cycle on the store. (3+2+2=7 cycles).

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.

> The only weird thing is that the article has managed to reach the front page.

This is the kind of detail not surfaced in a Boot Camp.

This isn’t to harsh on BCs. They have a specific goal and a short fuse, and the kind of things they cover use languages that are so high level you tend to have no visibility into the actual machine.

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.

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.

By the way, while one indeed needs the ability to "cancel out"/invert, we can derive similar swaps in weaker algebraic structures (and don't need full Abelian groups). For example, non-zero rationals can be divide-swapped: a = a / b; b = a / (1 / b); a = b / a; or similar for subtraction-swap. In general, a quasigroup seems to suffice: a = a * b; b = a / b; a = b \ a (where * is the group operation and / and \ are the right and left divisions, respectively).

Reply on news.ycombinator.com