[HN Gopher] Swapping two Numbers without Temporary Variables
___________________________________________________________________
Swapping two Numbers without Temporary Variables
Author : davesailer
Score : 40 points
Date : 2022-03-24 18:00 UTC (5 hours ago)
(HTM) web link (garrit.xyz)
(TXT) w3m dump (garrit.xyz)
| MrZongle2 wrote:
| 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!"_
| dimsumbytes wrote:
| 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
| milliams wrote:
| Or, in Python a, b = b, a
|
| Or Rust: (a, b) = (b, a);
| w3news wrote:
| JS: [b,a] = [a,b];
| paxys wrote:
| These aren't algorithms. The language is still doing something
| under the hood to do the swap.
| lanna wrote:
| Some people seem to forget that in high-level programming
| languages, lines of code seldom map 1-to-1 to processor
| instructions.
| baseballdork wrote:
| 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
| abainbridge wrote:
| That uses 4 registers and a stack!
| Thiez wrote:
| You can't do better with a non-inlined function.
| happytoexplain wrote:
| The downvotes on the OP comment and the negativity in the
| replies is totally baffling to me. The OP's post was
| interesting and relevant, despite being non-algorithmic
| examples. Non-algorithmic examples are not required by the
| title of the article, and are only _implicitly_ the topic
| of the article 's body, and even if it were explicit, that
| _still_ wouldn 't render the OP comment unrelated. It would
| have been enough to simply talk about the difference
| between an algorithmic and language-feature solution
| without implying something is wrong with even posting the
| latter.
| kzrdude wrote:
| And then the compiled code is doing something under the hood
| to do whatever the language thought it said.
|
| And then the cpu is doing something under the hood to do
| whatever the assembly code thought it said.
| manojlds wrote:
| Was that the problem statement? Come up with an algorithm to
| swap two numbers?
| jslaby wrote:
| or with a static variable
| Thiez wrote:
| 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.
| Adverblessly wrote:
| Even in C++ std::tie(a, b) = std::tuple(b, a);
| kmill wrote:
| For what it's worth, the Python example isn't too relevant
| since it's hiding a number of intermediate variables (that
| said, swapping without intermediate variables tends to be more
| of a curiosity anyway -- and a motivated person can "well
| actually" the whole concept into oblivion). What it does is
| push a and b onto the interpreter stack, then (in the version
| of Python 3 I'm running, though the more recent one should be
| similar) it pops those into two local C variables and pushes
| them in a different order, then it pops them and stores them
| into local python variables. import dis
| def swap(a, b): a, b = b, a return a
| dis.dis(swap)
|
| Output: 4 0 LOAD_FAST
| 1 (b) 2 LOAD_FAST 0 (a)
| 4 ROT_TWO 6 STORE_FAST 0 (a)
| 8 STORE_FAST 1 (b) 5 10
| LOAD_FAST 0 (a) 12 RETURN_VALUE
|
| Implementation of ROT_TWO
| https://github.com/python/cpython/blob/bc85eb7a4f16e9e2b6fb7...
| StillBored wrote:
| 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.
| [deleted]
| xxs wrote:
| 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.
| deanCommie wrote:
| https://xkcd.com/1053/
| vincent-manis wrote:
| 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.
| kevin_thibedeau wrote:
| 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.
| makeset wrote:
| XNOR is the (only) other binary operator that also works.
| karmasimida wrote:
| Overflow?
| johnea wrote:
| XOR A,B; XOR B,A; XOR A,B; credit to Andy Warren
| wolpoli wrote:
| 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 wrote:
| 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 wrote:
| 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.
| sam_goody wrote:
| 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...
| throw_away wrote:
| This is a variation on xor-swap, but one that suffers from
| over(/under)flow
|
| https://en.wikipedia.org/wiki/XOR_swap_algorithm#Variations
| Animats wrote:
| 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 wrote:
| can you explain this please (your comments are lovely btw)
| KMag wrote:
| 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.
| throwaway81523 wrote:
| 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 wrote:
| 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.
| LambdaTrain wrote:
| 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 wrote:
| the second half my comment is wrong. As someone comment points
| out there is xor swap
| nayuki wrote:
| No - to deal with overflow, the variables need to be widened by
| 1 bit.
| prophesi wrote:
| Not sure if this is what the OP meant, but adding a bit is
| effectively doubling the size. 16 bits = 65535. 17 = 131071.
| joe_the_user wrote:
| You could use unsigned ints, whose arithmetic wraps, to deal
| with the overflow.
|
| I'd still be curious about any theories of storage.
| charcircuit wrote:
| Javacript doesn't have an unsigned int datatype. The numbers
| in the article were doubles.
| xxs wrote:
| 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 wrote:
| It also breaks due to rounding even if you don't have NaN
| or Inf.
| sys_64738 wrote:
| The XOR trick does the same.
| everyone wrote:
| 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 wrote:
| 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.
| a_e_k wrote:
| 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
| 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 wrote:
| 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.
| sgeisenh wrote:
| This example is kind of funny in a compiled language because a
| lot of modern compilers use a static single assignment (SSA)
| form as an intermediate representation. SSA effectively creates
| temporaries for each subsequent assignment operation. This
| helps with data-flow analysis but also makes it so that code
| like in the post can actually be _less_ space efficient without
| optimizations in compiled languages.
___________________________________________________________________
(page generated 2022-03-24 23:02 UTC)