10 ms·

Swapping two Numbers without Temporary Variables

71 points by davesailer 5y ago

throw_away 5y ago
This is a variation on xor-swap, but one that suffers from over(/under)flow https://en.wikipedia.org/wiki/XOR_swap_algorithm#Variations https://en.wikipedia.org/wiki/XOR_swap_algorithm#Variations
- Animats 5y ago
  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.
  - Jerrrry 5y ago
    can you explain this please (your comments are lovely btw)
    - KMag 5y ago
      If you're interested in this sort of thing "The Art of Garbage Collection" is the standard go-to text these days. It's been a little while, but as I remember, the main reason for pointer reversing is to be able to not use any extra space to keep track of the list of grey (currently being processed) objects in a standard three-color collector. As you'll recall, a basic tracing collector marks each object as one of 3 colors: black, white, and grey. It must maintain the invariant that black objects never have pointers to white objects. A (full) GC cycle begins with all objects marked white, then the GC roots are marked grey. Then the collector repeatedly removes an object from the grey set, marks all of the white objects it points to as grey, and then marks the just removed grey object black. The GC cycle ends when there are no more grey objects, at which point all white objects are garbage and can be reclaimed. This is often implemented by using a single bit in the object header to keep track of white/black, and a stack to keep track of the set of grey objects. In this setup, a white object is marked grey by setting the color bit in the object header to whichever color indicates black, and putting it in the grey set. That is, grey objects are really marked black, but in the grey set. In other words, the color bit in the object header is really a "white"/"not white" bit. This is the easiest way to ensure a white object never gets added twice to the grey set without having to explicitly mark the object as grey. (Some systems actually invert the sense of the color bit in the object header between major GC collections. In one major collection 0 means white, and the next major collection 0 means black. This avoids having to scan the heap marking all objects white at the beginning of the GC cycle.) One way to implement the logical stack of grey objects is to use a singly-linked list. If you want to implement a linked list of objects without adding an extra pointer to every object's header, and you don't want to allocate any extra space in the middle of a garbage collection, then you need to figure out some kind of clever hack to re-purpose some existing space. I forget the exact details, but (1) if an object doesn't have any pointers in it, you can immediately mark it black without first adding it to the grey set ... and that's where I lose track of the details about how you keep track of which object pointer you've borrowed to reverse in order to use a linked list to implement your grey object stack. So, I'm missing the key detail that makes the whole trick work, but at a high level, you have extra storage space of one pointer to point at the top of the grey stack. The object at the bottom of the grey stack has its pointer nulled out, and off to the side you keep track of that last final pointer to restore when you empty the grey stack (which ends the GC cycle). When you pop an object off of the grey stack, you point its pointer to the previous object popped off of the grey stack (thus restoring (re-reversing) its reversed pointer). However, I can't for the life of me remember how you keep track of which pointer you've reversed in each object without using any extra space. I don't think you can always just use the first pointer in an object, because that could trap you in a cyclic sub-graph. EDIT: I've found a few different sets of very vague lecture notes online that are super vague... just saying you reverse pointers in order to make a linked list of grey objects. However, if you reverse all of the pointers, you don't get a linked list, but a general graph. You need to have exactly one pointer per object in order to have a singly linked list. If you have some rule of always using the first (or last) non-null pointer in an object, you might still wind up in a situation where you're reversing a cycle of pointers. I found a nice slide deck showing the steps, but the example was acyclic, and there was no explanatory text. I thought maybe there's a trick with using two bits for color in the object header, and using that to mark which pointer has been reversed by also marking the target object, but that breaks if there are multiple pointers to the specially marked object. Maybe the unmentioned trick is to use tagged pointers to keep track of the one pointer in each grey object that has been reversed. I really hope that's not it. That just feels... less brilliant.
      - mangamadaiyan 5y ago
        > The Art of Garbage Collection By any chance, were you referring instead to Richard Jones' "The Garbage Collection Handbook: The Art of Automatic Memory Management"? Garbage Collection interests me greatly, and I was looking forward to exploring a new reference - as it turned out, I couldn't find anything titled "The Art of Garbage Collection", so I thought I'd ask.
        KMag 5y ago
        Oops. You're right. "The Garbage Collection Handbook: The Art of Automatic Memory Management" by Richard Jones, et al., CRC Press, 2012.
      - KMag 5y ago
        Aha... it seems I've been lied to! It seems the proof of correctness is for a binary graph (each node has an out-degree of at most 2, but cycles are allowed in the graph) and needs 2 extra bits of state per node. [0][1] Now, one can represent any higher-degree graph as a binary graph by simply replacing any higher-degree nodes with a binary tree with the required number of out-nodes, but then that increases the number of extra bits required. Gries's 2006 less formal writeup [1] is simple to extend to higher-degree nodes. Instead of his 2-bit counter, one can use a counter that goes from 0 to the number of out-links. My guess is that real implementations use tagged pointers to indicate which pointer has been reversed instead of using a counter in Gries's write-up. I feel so lied to! No wonder I couldn't figure out how to do it without tagged pointers! Though, please correct me if you find a pointer reversal algorithm that doesn't use tagged pointers and is guaranteed to terminate in the case of arbitrary graph cycles. [0] https://xlinux.nist.gov/dads//HTML/SchorrWaiteGraphMarking.html https://xlinux.nist.gov/dads//HTML/SchorrWaiteGraphMarking.h... [1] https://www.cs.cornell.edu/courses/cs312/2007fa/lectures/lec21-schorr-waite.pdf https://www.cs.cornell.edu/courses/cs312/2007fa/lectures/lec...
        rurban 5y ago
        yes, you keep the 3 colors in each object. conveniently 2 bits of a pointer.
  - throwaway81523 5y ago
    That's pointer reversing but as I've seen it, it usually doesn't involve xor swap. It is still used in some gc's.
  - StillBored 5y ago
    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.
    - ncmncm 5y ago
      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.
      - jhgb 5y ago
        > Even after you rewrite them back to how they were Why would you do that? I was under the impression that the trick with the "XOR-ly linked list" is to keep these in RAM strictly in the XOR'd form. What exactly did you mean by "has to write back every line"?
        ncmncm 5y ago
        I misremembered the trick. Yes, it does save on storage without appreciable overhead.
everyone 5y ago
I remember just after college I applied for a .net job, when I came in for the interview they gave me a paper exam with a bunch of questions on how to do silly little tricks including that one specifically. I didn't take that job.
- code_runner 5y ago
  I tried to explain to a previous employer how much their little "brainteaser" test was turn off to legitimately talented engineers. I explained that everybody in town knows about the test and basically refuses to even entertain the company because of it. Bear in mind this is a place building relatively simple web apps... standard line of business stuff. The test was questions like "how many words can you unscramble from these letters" etc. A majority of the engineers felt the test meant you "knew you were working with smart people". A majority of the code was unmaintainable sludge. (though a few people were extremely talented) I no longer work there.
- hansvm 5y ago
  I can't comment on the rest of the interview, but this question in particular wouldn't necessarily be bad for some positions if so many people hadn't memorized a few solutions. A large part of some jobs is applying first-principles reasoning to a set of arbitrary requirements, and predicated on the assumption that a reasonable interviewer thought this was a good question or that they explicitly asked you to do your best to reason through the problem you'd be pretty safe starting with what you know and seeing how far that got you. A sample chain of reasoning might go as follows: - We have to take some first step transforming (X,Y) into (f(X,Y),Y) or (X,f(X,Y)). If one has a solution the other must as well, so assume (X,f(X,Y)). - The function f can't destroy any information since swapping two variables twice ends up where we started. - That immediately requires that f(X,Y) must properly depend on Y or else some information would be destroyed. Moreover, it has to properly depend on X if we're to ever make forward progress in swapping the information content of the two variables. - The problem doesn't specify how big the numbers are, so as a first pass at the problem there should probably exist a solution that works with 1-bit numbers. - There are only 16 two-input functions on bits. Only 2 of them (XOR and XNOR) properly depend on both variables and don't destroy information. - Applying XOR or XNOR a few times you'll easily find a small number of operations that swap two variables. For an alternative formulation you might not bother with or notice the 1-bit simplification. You'll go on to the second operation yielding (g(X,f(X,Y)), f(X,Y)). Again looking for something that makes your life easier you assume g is some kind of partial inverse of f so that you've actually almost completed the swap (i.e., that your partial solution at this point is (Y, f(X,Y))). That suggests some kind of a group-structure and lends itself to the XOR/XNOR we previously discovered, the ADD/SUB people commonly attempt as well (and we live in the real-world, say something to the interviewer about wraparound arithmetic or needing an extra bit if you go that route), and all sorts of other methods. And so on. If you have reason to actually try to _solve_ this problem instead of regurgitating answers you'll find a half-dozen easy methods which should still leave plenty of time for the rest of the interview. Side-note: I recall needing silly tricks like that more in .NET than other platforms. They didn't have an optimized popcount even as recently as the beginning of Covid for God's sake.
milliams 5y ago
Or, in Python a, b = b, a Or Rust: (a, b) = (b, a);
- jslaby 5y ago
  or with a static variable
  - Thiez 5y ago
    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.
- paxys 5y ago
  These aren't algorithms. The language is still doing something under the hood to do the swap.
  - manojlds 5y ago
    Was that the problem statement? Come up with an algorithm to swap two numbers?
  - lanna 5y ago
    Some people seem to forget that in high-level programming languages, lines of code seldom map 1-to-1 to processor instructions.
    - baseballdork 5y ago
      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 https://godbolt.org/z/1P98ss37P
      - abainbridge 5y ago
        That uses 4 registers and a stack!
MrZongle2 5y ago
The important takeaway from the article: "Please never use this in any production code. The less we have to think about a piece of code, the better it is. It's a fun thought experiment nevertheless!"
wolpoli 5y ago
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.
- happytoexplain 5y ago
  The author explicitly states that it should never be used due to readability. I'm interested in your point about performance, though - as a layman in this area, I would have thought that the additional operations were cheaper than whatever the overhead of a variable is, even for a primitive value type. Is that definitely not the case?
  - pjscott 5y ago
    In most cases swapping two variables with a temporary variable will be either zero-overhead -- because you've just changed the names you're referring to those variables by, and the compiler knows it -- or very, very low-overhead. You're not actually saving any memory with the fancy tricks.
  - Khoth 5y ago
    A modern CPU makes heavy use of out of order execution to do things quickly. Having the results of one operation depend on another makes it harder for the CPU to do this. If you have this: a = a + b b = a - b a = a - b // use a for something c = a + 7 then the final value of 'a' depends on both 'a' and 'b', so execution of the final line can't happen until the original 'a' and 'b' have both been fetched from memory/calculated/whatever. However, if you have this: temp = b b = a a = temp // use a for something c = a + 7 then the final value of 'a' depends only on 'b', so the final line can be executed even if the original 'a' isn't yet available.
- setuids 5y ago
  > 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
LambdaTrain 5y ago
To deal with overflow the size of variable a needs to be doubled. This trick, if applied correctly, uses the same amounts of memory. Now you may wonder whether we can mathematically prove swapping two variavles requires memory of three variables in digital computer...
- LambdaTrain 5y ago
  the second half my comment is wrong. As someone comment points out there is xor swap
- joe_the_user 5y ago
  You could use unsigned ints, whose arithmetic wraps, to deal with the overflow. I'd still be curious about any theories of storage.
  - charcircuit 5y ago
    Javacript doesn't have an unsigned int datatype. The numbers in the article were doubles.
    - xxs 5y ago
      you cant swap doubles like that though... b/c if any of them is a NaN or an infinity, it breaks down. It works for integers (and pointers)
      - charcircuit 5y ago
        It also breaks due to rounding even if you don't have NaN or Inf.
- nayuki 5y ago
  No - to deal with overflow, the variables need to be widened by 1 bit.
  - 5y ago
StillBored 5y ago
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.
a_e_k 5y ago
Behold!, as it all becomes the same thing in C++ with optimizations on: https://godbolt.org/z/joh1jhdhq 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 compilers excel at, so write the code clearly, leave that job to them, and worry about the high-level stuff that the compiler can't do for you.
- layer8 5y ago
  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.
  - a_e_k 5y ago
    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/9fdac7e16c940fb6264e6ddaf99c761f1a64a054/gcc/match.pd#L1492 https://github.com/gcc-mirror/gcc/blob/9fdac7e16c940fb6264e6...
  - civilized 5y ago
    This is fascinating.
  - tialaramex 5y ago
    Idiom recognition has been a thing in compilers for decades, so certainly don't rule it out.
johnea 5y ago
XOR A,B; XOR B,A; XOR A,B; credit to Andy Warren
dimsumbytes 5y ago
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
- rcfox 5y ago
  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.
  - dimsumbytes 5y ago
    Again, not trying to be that guy, but technically it still breaks: a = -0.0 b = 0.0
    - jayceedenton 5y ago
      I think you might be that guy :)
karmasimida 5y ago
Overflow?
sam_goody 5y ago
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/Reference/Operators/Destructuring_assignment https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
- mkdirp 5y ago
  Doesn't this create a new (temporary) array of value `[b,a]`?
  - ncmncm 5y ago
    If it does, that was optimal. If it doesn't, that was optimal. Outsmarting your optimizer is harder than that nowadays.
    - rurban 5y ago
      if optimizers would be smart. they are not. they do bad things, and occasionally even wrong things. and usually compiler writers blame the user, not themselves then.
  - deleted 5y ago
    [deleted]
sys_64738 5y ago
The XOR trick does the same.
deleted 5y ago
[deleted]
siraben 5y ago
XOR swap, as others have noted, is another very common way of implementing a swap without temporary variables. It's also a good exercise for formal verification, here's a proof in Coq of XOR swap's correctness in C.[0] [0] https://gist.github.com/siraben/d2ad58914166d5f6139b03b1b503ed6c https://gist.github.com/siraben/d2ad58914166d5f6139b03b1b503...
MaxMoney 5y ago
pajko 5y ago
Have done this in Human Resource Machine to shave off a few cycles and instructions in some solutions.
bspammer 5y ago
This was my technical interview question for university. Something like “you have two registers, and only basic mathematical operators. Swap the values contained in the two registers” on a whiteboard.
Alham-Dulillah 5y ago
HLSL can swap the x and y values of a float2 with swizzling: a = a.yx;
IYasha 5y ago
I wonder if there is an efficient hardware implementation for swap... I imagine plainly swapping bits of data[i] with data[n-i] is an intense and cache-unfriendly algorithm.
alex-ant 5y ago
That was an interview question at one of my first jobs, had to take few minutes to figure out.

71 points by davesailer 5y ago

This is a variation on xor-swap, but one that suffers from over(/under)flow https://en.wikipedia.org/wiki/XOR_swap_algorithm#Variations https://en.wikipedia.org/wiki/XOR_swap_algorithm#Variations

Animats 5y ago
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.
- Jerrrry 5y ago
  can you explain this please (your comments are lovely btw)
  - KMag 5y ago
    If you're interested in this sort of thing "The Art of Garbage Collection" is the standard go-to text these days. It's been a little while, but as I remember, the main reason for pointer reversing is to be able to not use any extra space to keep track of the list of grey (currently being processed) objects in a standard three-color collector. As you'll recall, a basic tracing collector marks each object as one of 3 colors: black, white, and grey. It must maintain the invariant that black objects never have pointers to white objects. A (full) GC cycle begins with all objects marked white, then the GC roots are marked grey. Then the collector repeatedly removes an object from the grey set, marks all of the white objects it points to as grey, and then marks the just removed grey object black. The GC cycle ends when there are no more grey objects, at which point all white objects are garbage and can be reclaimed. This is often implemented by using a single bit in the object header to keep track of white/black, and a stack to keep track of the set of grey objects. In this setup, a white object is marked grey by setting the color bit in the object header to whichever color indicates black, and putting it in the grey set. That is, grey objects are really marked black, but in the grey set. In other words, the color bit in the object header is really a "white"/"not white" bit. This is the easiest way to ensure a white object never gets added twice to the grey set without having to explicitly mark the object as grey. (Some systems actually invert the sense of the color bit in the object header between major GC collections. In one major collection 0 means white, and the next major collection 0 means black. This avoids having to scan the heap marking all objects white at the beginning of the GC cycle.) One way to implement the logical stack of grey objects is to use a singly-linked list. If you want to implement a linked list of objects without adding an extra pointer to every object's header, and you don't want to allocate any extra space in the middle of a garbage collection, then you need to figure out some kind of clever hack to re-purpose some existing space. I forget the exact details, but (1) if an object doesn't have any pointers in it, you can immediately mark it black without first adding it to the grey set ... and that's where I lose track of the details about how you keep track of which object pointer you've borrowed to reverse in order to use a linked list to implement your grey object stack. So, I'm missing the key detail that makes the whole trick work, but at a high level, you have extra storage space of one pointer to point at the top of the grey stack. The object at the bottom of the grey stack has its pointer nulled out, and off to the side you keep track of that last final pointer to restore when you empty the grey stack (which ends the GC cycle). When you pop an object off of the grey stack, you point its pointer to the previous object popped off of the grey stack (thus restoring (re-reversing) its reversed pointer). However, I can't for the life of me remember how you keep track of which pointer you've reversed in each object without using any extra space. I don't think you can always just use the first pointer in an object, because that could trap you in a cyclic sub-graph. EDIT: I've found a few different sets of very vague lecture notes online that are super vague... just saying you reverse pointers in order to make a linked list of grey objects. However, if you reverse all of the pointers, you don't get a linked list, but a general graph. You need to have exactly one pointer per object in order to have a singly linked list. If you have some rule of always using the first (or last) non-null pointer in an object, you might still wind up in a situation where you're reversing a cycle of pointers. I found a nice slide deck showing the steps, but the example was acyclic, and there was no explanatory text. I thought maybe there's a trick with using two bits for color in the object header, and using that to mark which pointer has been reversed by also marking the target object, but that breaks if there are multiple pointers to the specially marked object. Maybe the unmentioned trick is to use tagged pointers to keep track of the one pointer in each grey object that has been reversed. I really hope that's not it. That just feels... less brilliant.
    - mangamadaiyan 5y ago
      > The Art of Garbage Collection By any chance, were you referring instead to Richard Jones' "The Garbage Collection Handbook: The Art of Automatic Memory Management"? Garbage Collection interests me greatly, and I was looking forward to exploring a new reference - as it turned out, I couldn't find anything titled "The Art of Garbage Collection", so I thought I'd ask.
      - KMag 5y ago
        Oops. You're right. "The Garbage Collection Handbook: The Art of Automatic Memory Management" by Richard Jones, et al., CRC Press, 2012.
    - KMag 5y ago
      Aha... it seems I've been lied to! It seems the proof of correctness is for a binary graph (each node has an out-degree of at most 2, but cycles are allowed in the graph) and needs 2 extra bits of state per node. [0][1] Now, one can represent any higher-degree graph as a binary graph by simply replacing any higher-degree nodes with a binary tree with the required number of out-nodes, but then that increases the number of extra bits required. Gries's 2006 less formal writeup [1] is simple to extend to higher-degree nodes. Instead of his 2-bit counter, one can use a counter that goes from 0 to the number of out-links. My guess is that real implementations use tagged pointers to indicate which pointer has been reversed instead of using a counter in Gries's write-up. I feel so lied to! No wonder I couldn't figure out how to do it without tagged pointers! Though, please correct me if you find a pointer reversal algorithm that doesn't use tagged pointers and is guaranteed to terminate in the case of arbitrary graph cycles. [0] https://xlinux.nist.gov/dads//HTML/SchorrWaiteGraphMarking.html https://xlinux.nist.gov/dads//HTML/SchorrWaiteGraphMarking.h... [1] https://www.cs.cornell.edu/courses/cs312/2007fa/lectures/lec21-schorr-waite.pdf https://www.cs.cornell.edu/courses/cs312/2007fa/lectures/lec...
      - rurban 5y ago
        yes, you keep the 3 colors in each object. conveniently 2 bits of a pointer.
- throwaway81523 5y ago
  That's pointer reversing but as I've seen it, it usually doesn't involve xor swap. It is still used in some gc's.
- StillBored 5y ago
  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.
  - ncmncm 5y ago
    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.
    - jhgb 5y ago
      > Even after you rewrite them back to how they were Why would you do that? I was under the impression that the trick with the "XOR-ly linked list" is to keep these in RAM strictly in the XOR'd form. What exactly did you mean by "has to write back every line"?
      - ncmncm 5y ago
        I misremembered the trick. Yes, it does save on storage without appreciable overhead.

everyone 5y ago

I remember just after college I applied for a .net job, when I came in for the interview they gave me a paper exam with a bunch of questions on how to do silly little tricks including that one specifically. I didn't take that job.

code_runner 5y ago
I tried to explain to a previous employer how much their little "brainteaser" test was turn off to legitimately talented engineers. I explained that everybody in town knows about the test and basically refuses to even entertain the company because of it. Bear in mind this is a place building relatively simple web apps... standard line of business stuff. The test was questions like "how many words can you unscramble from these letters" etc. A majority of the engineers felt the test meant you "knew you were working with smart people". A majority of the code was unmaintainable sludge. (though a few people were extremely talented) I no longer work there.
hansvm 5y ago
I can't comment on the rest of the interview, but this question in particular wouldn't necessarily be bad for some positions if so many people hadn't memorized a few solutions. A large part of some jobs is applying first-principles reasoning to a set of arbitrary requirements, and predicated on the assumption that a reasonable interviewer thought this was a good question or that they explicitly asked you to do your best to reason through the problem you'd be pretty safe starting with what you know and seeing how far that got you. A sample chain of reasoning might go as follows: - We have to take some first step transforming (X,Y) into (f(X,Y),Y) or (X,f(X,Y)). If one has a solution the other must as well, so assume (X,f(X,Y)). - The function f can't destroy any information since swapping two variables twice ends up where we started. - That immediately requires that f(X,Y) must properly depend on Y or else some information would be destroyed. Moreover, it has to properly depend on X if we're to ever make forward progress in swapping the information content of the two variables. - The problem doesn't specify how big the numbers are, so as a first pass at the problem there should probably exist a solution that works with 1-bit numbers. - There are only 16 two-input functions on bits. Only 2 of them (XOR and XNOR) properly depend on both variables and don't destroy information. - Applying XOR or XNOR a few times you'll easily find a small number of operations that swap two variables. For an alternative formulation you might not bother with or notice the 1-bit simplification. You'll go on to the second operation yielding (g(X,f(X,Y)), f(X,Y)). Again looking for something that makes your life easier you assume g is some kind of partial inverse of f so that you've actually almost completed the swap (i.e., that your partial solution at this point is (Y, f(X,Y))). That suggests some kind of a group-structure and lends itself to the XOR/XNOR we previously discovered, the ADD/SUB people commonly attempt as well (and we live in the real-world, say something to the interviewer about wraparound arithmetic or needing an extra bit if you go that route), and all sorts of other methods. And so on. If you have reason to actually try to _solve_ this problem instead of regurgitating answers you'll find a half-dozen easy methods which should still leave plenty of time for the rest of the interview. Side-note: I recall needing silly tricks like that more in .NET than other platforms. They didn't have an optimized popcount even as recently as the beginning of Covid for God's sake.

milliams 5y ago

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

jslaby 5y ago
or with a static variable
- Thiez 5y ago
  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.
paxys 5y ago
These aren't algorithms. The language is still doing something under the hood to do the swap.
- manojlds 5y ago
  Was that the problem statement? Come up with an algorithm to swap two numbers?
- lanna 5y ago
  Some people seem to forget that in high-level programming languages, lines of code seldom map 1-to-1 to processor instructions.
  - baseballdork 5y ago
    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 https://godbolt.org/z/1P98ss37P
    - abainbridge 5y ago
      That uses 4 registers and a stack!

MrZongle2 5y ago

The important takeaway from the article: "Please never use this in any production code. The less we have to think about a piece of code, the better it is. It's a fun thought experiment nevertheless!"

wolpoli 5y ago

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.

happytoexplain 5y ago
The author explicitly states that it should never be used due to readability. I'm interested in your point about performance, though - as a layman in this area, I would have thought that the additional operations were cheaper than whatever the overhead of a variable is, even for a primitive value type. Is that definitely not the case?
- pjscott 5y ago
  In most cases swapping two variables with a temporary variable will be either zero-overhead -- because you've just changed the names you're referring to those variables by, and the compiler knows it -- or very, very low-overhead. You're not actually saving any memory with the fancy tricks.
- Khoth 5y ago
  A modern CPU makes heavy use of out of order execution to do things quickly. Having the results of one operation depend on another makes it harder for the CPU to do this. If you have this: a = a + b b = a - b a = a - b // use a for something c = a + 7 then the final value of 'a' depends on both 'a' and 'b', so execution of the final line can't happen until the original 'a' and 'b' have both been fetched from memory/calculated/whatever. However, if you have this: temp = b b = a a = temp // use a for something c = a + 7 then the final value of 'a' depends only on 'b', so the final line can be executed even if the original 'a' isn't yet available.
setuids 5y ago
> 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

LambdaTrain 5y ago

To deal with overflow the size of variable a needs to be doubled. This trick, if applied correctly, uses the same amounts of memory. Now you may wonder whether we can mathematically prove swapping two variavles requires memory of three variables in digital computer...

LambdaTrain 5y ago
the second half my comment is wrong. As someone comment points out there is xor swap
joe_the_user 5y ago
You could use unsigned ints, whose arithmetic wraps, to deal with the overflow. I'd still be curious about any theories of storage.
- charcircuit 5y ago
  Javacript doesn't have an unsigned int datatype. The numbers in the article were doubles.
  - xxs 5y ago
    you cant swap doubles like that though... b/c if any of them is a NaN or an infinity, it breaks down. It works for integers (and pointers)
    - charcircuit 5y ago
      It also breaks due to rounding even if you don't have NaN or Inf.
nayuki 5y ago
No - to deal with overflow, the variables need to be widened by 1 bit.
- 5y ago

StillBored 5y ago

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.

a_e_k 5y ago

Behold!, as it all becomes the same thing in C++ with optimizations on: https://godbolt.org/z/joh1jhdhq 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 compilers excel at, so write the code clearly, leave that job to them, and worry about the high-level stuff that the compiler can't do for you.

layer8 5y ago
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.
- a_e_k 5y ago
  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/9fdac7e16c940fb6264e6ddaf99c761f1a64a054/gcc/match.pd#L1492 https://github.com/gcc-mirror/gcc/blob/9fdac7e16c940fb6264e6...
- civilized 5y ago
  This is fascinating.
- tialaramex 5y ago
  Idiom recognition has been a thing in compilers for decades, so certainly don't rule it out.

johnea 5y ago

XOR A,B; XOR B,A; XOR A,B; credit to Andy Warren

dimsumbytes 5y ago

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

rcfox 5y ago
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.
- dimsumbytes 5y ago
  Again, not trying to be that guy, but technically it still breaks: a = -0.0 b = 0.0
  - jayceedenton 5y ago
    I think you might be that guy :)

karmasimida 5y ago

Overflow?

sam_goody 5y ago

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/Reference/Operators/Destructuring_assignment https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

mkdirp 5y ago
Doesn't this create a new (temporary) array of value `[b,a]`?
- ncmncm 5y ago
  If it does, that was optimal. If it doesn't, that was optimal. Outsmarting your optimizer is harder than that nowadays.
  - rurban 5y ago
    if optimizers would be smart. they are not. they do bad things, and occasionally even wrong things. and usually compiler writers blame the user, not themselves then.
- deleted 5y ago
  [deleted]

sys_64738 5y ago

The XOR trick does the same.

deleted 5y ago

[deleted]

siraben 5y ago

XOR swap, as others have noted, is another very common way of implementing a swap without temporary variables. It's also a good exercise for formal verification, here's a proof in Coq of XOR swap's correctness in C.[0] [0] https://gist.github.com/siraben/d2ad58914166d5f6139b03b1b503ed6c https://gist.github.com/siraben/d2ad58914166d5f6139b03b1b503...

MaxMoney 5y ago

pajko 5y ago

Have done this in Human Resource Machine to shave off a few cycles and instructions in some solutions.

bspammer 5y ago

This was my technical interview question for university. Something like “you have two registers, and only basic mathematical operators. Swap the values contained in the two registers” on a whiteboard.

Alham-Dulillah 5y ago

HLSL can swap the x and y values of a float2 with swizzling: a = a.yx;

IYasha 5y ago

I wonder if there is an efficient hardware implementation for swap... I imagine plainly swapping bits of data[i] with data[n-i] is an intense and cache-unfriendly algorithm.

alex-ant 5y ago

That was an interview question at one of my first jobs, had to take few minutes to figure out.