How to Swap two numbers without temp variable in Java | Hacker News Reader

How to Swap two numbers without temp variable in Java

javarevisited.blogspot.com.br

34 pointsjavinpaul54 comments

There are many ways to swap two variables without using a temp variable, as long as the type of the variables is a mathematical group[0].

If the group operation is denoted <>, with identity e, and the inverse of 'a' is 'inv(a)' then you would do

    a = a0;
    b = b0;            // initial assignment

    a = a <> b;        // a = a0 <> b0 and b = b0.
    b = a <> inv(b);   // a = a0 <> b0 and b = a0 <> b0 <> inv(b0) = a0.
    a = inv(b) <> a;   // a = inv(a0) <> a0 <> b0 = b0 and b = a0.

This works when a and b are ints, which are a group with the operator '+' and identity '0', and inverses inv(n) = -n (see [1])

It works when a and b are nonzero floats, which are a group under multiplication with identity 1.0 and inverses inv(x) = 1/x (but see [2]).

It works when a and b have fixed-length binary representations, because fixed-length binary strings are a group where the operation is xor (or '^') and inv(x) = x.

It works when a and b are matrices of the same dimension, which form a group in two different ways - under matrix addition, where the inverse is elementwise negation, and under matrix multiplication (if a and b are nonsingular) where the inverse is the regular matrix inverse [3].

Note that in my third line, the right-hand side of the assignment is inv(b) <> a, whereas all the examples in the blog post used a <> inv(b). They were implicitly assuming a commutative group (i.e. a <> b == b <> a for all a and b) whereas my procedure works even for non-commutative groups, e.g. matrices under matrix multiplication.

Edit: Obviously, if you actually use this in real code... WAT.

[0] http://en.wikipedia.org/wiki/Group_(mathematics)

[1] this even works if one of the operations causes an integer overflow - the magic of modular arithmetic!

[2] floats don't really form a group, because of non-associativity of floating point multiplication.

[3] http://en.wikipedia.org/wiki/Invertible_matrix

> fixed-length binary strings are a group where the operation is xor (or '^') and inv(x) = x

Most people would call this group (Z/2Z)^n, i.e. n copies of Z/2Z under addition. Similarly, for "matrix addition" you could say Z^(mn) or R^(mn) for matrices with dimension mxn with elements Z or R (or whatever you are filling your matrices with). Your only non-abelian example is matrix multiplication, i.e. GL(n,R), general linear transformations of dimension n over R. It may or may not be interesting that this is mainly focused on abelian groups.

>"Edit: Obviously, if you actually use this in real code... WAT."

For those who haven't seen the video : http://www.youtube.com/watch?v=D0EIZa5e9q4&t=0m40s

Actually, isn't having unique inverses a weaker requirement than being a group? Maybe I am wrong...

There are algebraic objects for which inverses are defined, but which aren't groups: namely groupoids, quasigroups and loops.

In groupoids the binary operation isn't total, i.e. there can be pairs (a,b) for which a <> b is not defined -- so we can't use groupoids.

In quasigroups and loops the binary operation doesn't need to be associative. But we require associativity, so that we can deduce

    (a <> b) <> inv b == a <> (b <> inv b) == a <> e == a

So we do actually need all the properties of a group.

A commenter on Reddit pointed out that quasigroups require both left and right division operators \ and /, and that even though they are not associative, the axioms

    x \ (x * y) = y
    x * (x \ y) = y
    (x * y) / y = x
    (x / y) * y = x

must hold -- so in fact, quasigroups are good enough!

While these are neat for things like a programmer's interview question I would be very careful about actually using these in real code, for two reasons:

1. It obfuscates the code for very little benefit. Readability suffers more than performance gains.

The JVM could employ similar tricks under the covers for performance reasons if it detects that this is on the hot path.

2. The code is sensitive to overflow, sign handling, Not-a-Number, and divide-by-zero.

Both these points should be raised by an experienced programmer.

Actually, it's worse than that.

In both Java and C/C++, doing this kind of thing actually makes code slower. It only makes sense in assembler.

When the compiler can deduce that two variables already in registers have swapped value, it simply relabels the registers, making swap a 0-cost operation. Obviously if are swapping two memory locations, you have to read, but a temporary optimises to:

mem1 -> reg1 mem2 -> reg2 reg1 -> mem2 reg2 -> mem1

While a swap trick, if the compiler can't backward-enginner it out has to add a bit of xoring (or adding).

gcc actually has an optimisation pass with the specific job of trying to take out this trick. Unfortunately, it can't always work because if you try using these tricks on two pointers to the same memory location, you end up zeroing out the value rather than doing nothing (which a proper temporary would).

To add one more evil edge case - if you're using something like libgc in your project and try swapping pointers that way, there's a chance you're going to lose your memory by accident.

> It only makes sense in assembler.

Not even this (well, there obviously are exceptions), given the existence of XCHG, BSWAP and similar instructions.

I would argue that they're harmful even as interview questions. This sort of thing is never a good idea, so why risk giving the other party the impression that maybe it sometimes is?

Perhaps they're useful as interview questions insofar as eliciting whether the applicant understands why it's not a good idea.

One does not understand an opposing view unless one can give a convincing argument for that view, then tear it apart. I usually apply this to politics & philosophy, but it applies to engineering too: X is a clever approach, but subject to limitations Y. In this case, understanding that more information exists somewhere than is obvious shows insight ... and articulating the limitations of that concept demonstrates superior knowledge. It's not about swapping numbers, it's about how much information can be crammed into two variables and their metadata.

That doesn't work in interviews, since the candidate would be very reluctant to question the interviewer's task.

I actually think that even as an interview question the real benefit is in using it as a lead-in to the "do you think this is a good idea?" area of questioning. The xor sequence itself is just another "have you seen this trivia question before?" question, which doesn't really reveal any interesting information. Finding out what the candidate thinks about code readability, whether they know what kind of things a compiler or JVM might do, whether their mental model of assembler-level optimisation is still the "all the world is a Z80 and execution time is proportional to instruction count" flavour or if they are aware of caches, pipelines and so on -- these are all useful. You can also take the "ok, plug in some numbers and show me whether your sequence works" tack to find out whether your candidate can work through doing bitwise logical operations on integers, a sort of bit-flipping variant on fizzbuzz.

But "have you seen this before" is so uninteresting that I always tried to make it clear that I really wasn't interested in whether they knew the trick or not, but more in the ensuing discussion.

I have actually passed an interview where a misuse of the swap trick was part of the "what's wrong with this piece of code" question. Maybe this is similar to "have you seen this trivia question before" but reverted: "can you spot this idiotic trick that causes bugs", which I believe is much more valuable.

It's "cute", I'll give you that. But what possible use could this have? Using a temp variable is MORE likely to be optimized by the compiler[1] and is FAR easier for someone reading the code to understand. Using it in an interview falls into the trap of asking useless and irrelevant questions that weed out perfectly good candidates. All in all, it's a bad idea.

[1] - I don't actually know this... but I suspect that it's true.

Yes, the answer I would like to hear is that in a high level language - if the language itself doesn't support it (e.g. in Ruby you can do 'a, b := b, a' or a parallel computing language) - you don't fight the compiler but use the correct idiom that the compiler can optimize.

You can still say that if you are programming in assembler or java bytecode for optimization reasons you can do any of those stupid programming tricks.

Not to mention this approach has issues with overflow.

The first two methods don't.

ah yep, you are correct.

Deleted comment

> At the hardware level, you can't swap two variables without using a third.

There are situations where that's not true. Consider doing the register allocation for code which does this:

  void foo(int x, int y) {
    for (/* stuff */) {
      // swap x and y on each iteration
      int t = x;
      x = y;
      y = t;
      // do stuff with x and y
    }
  }

This is a situation where the code does a swap, and the register allocator can't optimize it away (without unrolling the loop). But we can use the XOR swap trick to swap x and y in place, without using a third register, which may make another register available which can live across loop iterations.

  x ^= y
  y ^= x
  x ^= y

and we're done. No third register needed.

Of course, this is a really low-level trick useful in certain register allocation algorithms, not something that normal users should write in a high-level language.

> will require the presence of a register into which to place a^b right before writing it back to a. But then you might as well use this register directly for the swap. "Saving" a third variable is in every way a false economy.

I think you will find that you are wrong.

  x86 asm:
  XOR EAX,EBX 
  XOR EBX,EAX
  XOR EAX,EBX

1. I am not saying that this trick is of much use in most cases.

2. But there CPU/MCU's with only registers and no (data) RAM. Also, very early boot on x86 doesn't have RAM initialized.

3. All registers are not equal, some instructions (on x86) default to certain registers, and it might be useful if no free register is available.

4. Again. Doing this without a good reason is stupid.

The argument could be made that this is due to the "high level" nature of x86 assembly :-).

On the actual physical chip such an instruction does involve intermediate register-like storage, and this storage exists by necessity: After all, on the electrical level, the operation is carried out by waiting for the voltage levels on some output "wires" to stabilize while the intermediate network of transistors is presented the input voltages continually. In this case, that would take 1 clock tick - after which the probability that the output pattern represents XOR is almost 1 (there is a neglible chance of failure).

The point is: we cannot predict such circuits precisely enough when the output really is directly connected to the input (that would be a resonating feedback loop, after all - and we only know the input voltage to within some tolerance, not to mention quantummechanical effects), so there's always some gating and that means some intermediate storage. Even when the instruction set hides that from you.

You are correct about that. But that is still not the same as using a third temporary (visible) register for the swap that may, or may not be available.

> But then you might as well use this register directly for the swap. "Saving" a third variable is in every way a false economy.

You mean internally the processor will decode the xor using another register?

Even if that's accurate, it still could be an optimization. You save code space, which might avoid a cache hit. And if the code is targeting some intermediate platform, it might explicitly allocate another local, preventing other optimizations.

actually this is not quite true. most instruction sets don't support a three parameter form a = b xor c, but only the simpler two parameter form a = a xor b.

this is a perfectly valid, and ancient, trick for x86 assembler

If I wanted to find somebody who understood bitwise operations maybe useful.

If I'm looking to find a developer who can write maintainable line of business software, which Java is a common fit for then I'd be aghast if this was proposed as a sensible, maintainable solution.

This trick just reminds me of a long list of things that people ask for at interview, which has no demonstrable link to the job at hand. Why not ask for someone to memorise a complex api? Or understand a workaround for a long standing "won't fix" framework.

Pointless. Useless.

Seeing it since recently more often in Blogs, I see increased readability. After all, you just need to remember 3x XOR (a-b-a).

I find the swap solution w/ temp solution to be more painful for my eyes. It's also 3 lines, but less homogenous.

Cool trick. If I ever see this in your real-world production code, you're fired.

The really nasty edge case is aliasing. Say you're swapping a[i] with a[j]. What happens when i==j? Nope, not what any sane person expects a swap operation to do in this case...

This nasty trick was actually used in one of the Underhanded C Contest entries in 2007.

My solution ended up like this:

a = b + (b = a) - a;

In Java, it seems to work, but in C (gcc 4.6.3) it doesn't. a ends up unchanged, since the first instance of b contains the original value of a when evaluated. Not sure why Java evaluates it the way it does.

That's because java is much stricter about enforcing the order of evaluation in these kinds of aliased statements, whereas in C it's undefined and the compiler just "does something". Of course, you'd have to be a real code-masochist to do this to yourself even in java...

a = b - a + (b = a);

works in C. Trick is operator associativity, with the "-" left of the "+" causing the "b-a" to evaluate (and thus, cheating, causing an anonymous variable/register to store an intermediate value) before evaluating the "+" which invokes assignment of the value of a to b, then undoing the subtraction of a from b.

(Yikes, did I just write that?)

I'm almost sure this is undefined behavior!

It may break on you at unexpected moments (such as when you change optimization options or compilers). I'm certain it was undefined, but perhaps some new standard is stricter (I don't think so, however).

See http://en.wikipedia.org/wiki/Sequence_point

In essence there's no guarantee the read from the first reference to b will occur before the write to the second reference.

Edit: a quick skim of C++11 changes doesn't seem like it includes any changes here, just some rewording and clarification: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n223...

Oh god

Sane programming languages have multiple assignment ie a, b = b, a or some other syntax.

You guys need to read the book "hackers delight" full of really great stuff like this ISBN-13: 978-0-321-84268-8 ISBN-10: 0-321-84268-5

This is a very old trick. According to Knuth, it goes back to at least 1961, where it was found in IBM programming course notes in a more general form that includes a mask:

x ← x ⊕ y, y ← y ⊕ (x & m), x ← x ⊕ y

The mask determines the subset of bits that get swapped.

Funny this should be on the front page the same day that there is stuff about interview "puzzles"

1) This is not really a programming questing. It is a logic or math or algorithm question.

2) Please tell me a real-world programming situation where this would be required.

I guess the third approach breaks if one of the two numbers is 0

Or if an overflow occurs (while methods 1 and 2 work fine even with overflow, in Java at least as overflow semantics are well defined).

two things i'd want to add. firstly the arithmetic with +/- fails when over/underflow occurs. secondly xor works because it is its own inverse. the more generic answer is using any operator that forms a group over the potential values to be swapped... as another comment explains

i remember feeling fantastically clever when i rediscovered this about 15 years ago. it has been of nearly zero value to me since.

+/- doesn't fail in a language where + is addition modulo n.

true, but lots of things work in special cases.

oh... and as alluded to but not explained thorougly 'static single assignment' form completely negates the utility of this hack.

Simple yet difficult to conjure. This is awesome!

What makes it awesome? It seems like a way to take something simple (swapping variables) and write it in a complex way (three operations) so that neither the humans nor the compilers reading it will know what is going on.

Real temporary variables are clearer for both humans and machines.

Read crntaylor's explanation of this via group theory: https://news.ycombinator.com/item?id=5278915

So this is awesome insofar as you find things like group theory awesome (I did). But like he says, if you find this awesome to use in production code, that's a horse of another color.

What's the point of finding the trillionth number in pi? The same is implied here. We do things, just because we can.

This would be a great question for rejecting an otherwise qualified job candidate ...

Yea it's very simple but in an interview environment I probably would have over thought this. (I guess that's the point though)

My initial reaction to the question was simply assign the value of one variable as the name of the other. Does that count?

    a = a0
    a0 = b0 // initial assignments
    a = b0
    a0 = a0 // swapped

Reply on news.ycombinator.com