XOR swap algorithm
Did you know that you can swap the value of 2 variables without an auxiliary one? The most commonly used way is as follows:
But you actually don't need that aux variable:
This method is known as the XOR swap algorithm.
public static void main(String[] args) { int x = 1; int y = 2; System.out.println("Before swap: X = " + x + ", Y = " + y); int aux = x; x = y; y = aux; System.out.println("After swap: X = " + x + ", Y = " + y); }
But you actually don't need that aux variable:
public static void main(String[] args) { int x = 1; int y = 2; System.out.println("Before swap: X = " + x + ", Y = " + y); x = x ^ y; y = x ^ y; x = x ^ y; System.out.println("After swap: X = " + x + ", Y = " + y); }
This method is known as the XOR swap algorithm.
Why not use the following notation? It's more concise.
ReplyDeletex ^= y;
y ^= x;
x ^= y;
Yes, you're right, it's more concise but IMHO slightly less readable :)
ReplyDeleteAnother method I found out, perhaps you could compare both approaches?
ReplyDeletea += b;
b = a - b;
a += -b;
Also, the xor swap fails when x equals y, whilst this approach doesn't. That's one clear advantage.
However, I don't know how they compare in speed and on a low level; I guess it'd be an interesting extension to your article.
The XOR swap algorithm works fine when x = y, you might have tested wrong.
ReplyDeleteAbout your algorithm, yes, it works, but it is most likely to be slower than XOR algorithm. Logical operations are ALU's fastest, and XOR is one of them. Also in your algorithm you're doing more operations, even if you write them in one line: a += -b (here you got one unary operator then a binary one).
From wikipedia: "[...]if the addresses are equal, the algorithm will fold to a triple *x ^= *x resulting in zero."
ReplyDeleteVery interesting to know about ALU, though. I'm reading more on it right now.
You can try yourself and see that's it's working even if x = y, for example:
ReplyDeletex = 1
y = 1
x = x ^ y (x = 0; y = 1)
y = x ^ y (x = 0; y = 1)
x = x ^ y (x = 1; y = 1)
You are actually correct, I should have tested it.
ReplyDeleteI believe you will find this interesting: https://rbt.asia/g/thread/32344720
I find it fascinating how using bitwise operations can simplify variable swapping.
ReplyDelete