StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Most people would swap two variables x and y using a temporary variable, like this:</p> <pre><code>tmp = x x = y y = tmp </code></pre> <p>Here’s a neat programming trick to swap two values without needing a temp:</p> <pre><code>x = x xor y y = x xor y x = x xor y </code></pre> <p>More details in <a href="http://betterexplained.com/articles/swap-two-variables-using-xor/" rel="noreferrer">Swap two variables using XOR</a></p> <blockquote> <p>On line 1 we combine x and y (using XOR) to get this “hybrid” and we store it back in x. XOR is a great way to save information, because you can remove it by doing an XOR again.</p> <p>On line 2. We XOR the hybrid with y, which cancels out all the y information, leaving us only with x. We save this result back into y, so now they have swapped.</p> <p>On the last line, x still has the hybrid value. We XOR it yet again with y (now with x’s original value) to remove all traces of x out of the hybrid. This leaves us with y, and the swap is complete!</p> </blockquote> <hr> <blockquote> <p>The computer actually has an implicit “temp” variable that stores intermediate results before writing them back to a register. For example, if you add 3 to a register (in machine-language pseudocode):</p> </blockquote> <pre><code>ADD 3 A // add 3 to register A </code></pre> <blockquote> <p>The ALU (Arithmetic Logic Unit) is actually what executes the instruction 3+A. It takes the inputs (3,A) and creates a result (3 + A), which the CPU then stores back into A’s original register. So, we used the ALU as temporary scratch space before we had the final answer.</p> <p>We take the ALU’s implicit temporary data for granted, but it’s always there. In a similar way, the ALU can return the intermediate result of the XOR in the case of x = x xor y, at which point the CPU stores it into x’s original register.</p> <p>Because we aren’t used to thinking about the poor, neglected ALU, the XOR swap seems magical because it doesn’t have an explicit temporary variable. Some machines have a 1-step exchange XCHG instruction to swap two registers.</p> </blockquote>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload