4 ms·

I think the more accepted way for a long time has been to use xor. https://en.wikipedia.org/wiki/XOR_swap_algorithm https://en.wikipedia.org/wiki/XOR_swap_algo

I think the more accepted way for a long time has been to use xor. https://en.wikipedia.org/wiki/XOR_swap_algorithm 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.

wolpoli 5y ago
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?
- aix1 5y ago
  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.
deleted 5y ago
[deleted]
xxs 5y ago
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.
- vincent-manis 5y ago
  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.
- deanCommie 5y ago
  https://xkcd.com/1053/ https://xkcd.com/1053/
- kevin_thibedeau 5y ago
  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.
- StillBored 5y ago
  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).
  - xxs 5y ago
    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.
- gumby 5y ago
  > 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.
makeset 5y ago
XNOR is the (only) other binary operator that also works.
- groby_b 5y ago
  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.
  - madars 5y ago
    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).

wolpoli 5y ago

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?

aix1 5y ago
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.

deleted 5y ago

[deleted]

xxs 5y ago

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.

vincent-manis 5y ago
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.
deanCommie 5y ago
https://xkcd.com/1053/ https://xkcd.com/1053/
kevin_thibedeau 5y ago
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.
StillBored 5y ago
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).
- xxs 5y ago
  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.
gumby 5y ago
> 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.

makeset 5y ago

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

groby_b 5y ago
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.
- madars 5y ago
  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).