Talk:XOR swap algorithm

From Wikipedia, the free encyclopedia

You have new messages (last change).

Contents

[edit] Code snippets, algorithm vs. pattern philosophy

Do we really need separate articles for code in each language? It's pretty obvious, once you've read a couple, to see how to do it in another. Otherwise we'll end up with articles on XOR swap in { Forth, LISP, MIXAL, SNOBOL, C#, Eiffel, Smalltalk ... }

Just a suggestion - if one wishes to keep the code snippets, maybe they should be merged into this single article?
This is an encyclopedia, it is meant to provide information, many of the algorithm articles have long listings of code in different languages, people who read this article will want to come and instantly find the code in their own prefered language. I beleive that for the users every language possible should be included, after all, an encyclopedia is about teaching people and providing information. Tell me what you think, and please, someone add the GML version back. I beleive that it is quite usefull and that this algorithm should be posted in many languages.

71.28.13.158 22:33, 27 November 2006 (UTC)

the whole 'Effiency' discussion is plain wrong, x86 optimisation is too complex for these statements, sometimes using a temp is more efficient, the xchg instruction is not very efficient on pentium and so forth (making reg dep and so), also I don't see the relevance of putting various impl and discussions here about how it would be in x86, C , pascal and who know what.

... another point: 'Basically, this trick should never be used in real code' is 'baised', who's to say what's to use in 'real' code, or what is 'real' code? personally i've used it in comertial (real?) production code, more than once, and I know of several other cases, this code is still used AFAIK in some commrtial products used by 'serious' companies, it is not obfuscated, and I'll be suprised if IOCCC judges would be impressed. I know of no xor-swapping compiler, and i think the last paragraph should be removed or altered.

I agree, it's POV. Also, code is not obscure unless it is not commented - this section can simply have the preceding comment /* swap X and Y */ and it becomes clear - what's the problem? GRAHAMUK 01:20, 21 Oct 2003 (UTC)

Shoudn't XOR swapping be regarded more a pattern than algorithm? About production code, and use, it's really a very straight forward use of plain parity nature of XOR, as used also in RAID for example, or any parity checking. For some math or hardware oriented people this doesn't seem at all obfuscated or hard to analyse.

An algorithm is a finite sequence of steps that performs some task. The XOR swap is a finite sequence of steps that swaps two variables. It's an algorithm. Dysprosia 09:44, 24 Oct 2003 (UTC)
But what about it's pattern'ish use, as in xor-blitting a sprite on a computer screen for example (as patented by IBM), the pattern of symmetric diff is used here quite trivially. Proboably my usage of 'pattern' term is skewed here, what I mean is that it's useful in the middle of other algorithms. I can give you some code examples, from production code, of computer games, using xor-swapping embedded in a velocity calculations, or for example in specific optimised mul routines on Z80. It is an 'algorithm' in the same manner that adding together 2 numbers is.

,

So is adding two numbers a pattern? :) Define pattern, in any case - I still think algorithm is the best way to describe this. We still also use algorithms in the middle of other algorithms however; and I don't think "pattern" to describe a section of code is a widely used term - we may end up confusing people... Dysprosia 08:19, 28 Oct 2003 (UTC)
I will try to avoid a semantic disccussion about patterns, however adding two numbers is certainly frequent enough, even to be embedded in silicon. The term pattern is confusing for it, so I would describe them now, more as 'idioms' than algorithms or patterns. Anyway, let's please avoid this discoussion.

Btw: I still find the code snipplets just heavy on the eye, and irrelevant to the page. For anyone familiar with a lang's syntax writing xor swap should be trivial, and I see no reason turning lots of pages into '100 bottles of beer in 99999 diffrent langs'

I agree a little with you, but the issue should be discussed here before it is removed. Dysprosia 09:18, 28 Oct 2003 (UTC)
so that's what we're doing aren't we? aren't there some more global discussions about that? programming-pages wikipedia guidelines?

Of course addition is an algorithm. e.g

add a 0 = a
add a b = add (pred a) (succ a)

We just often forget this, since it is not usually necessary to remind ourselves how a particular addition is done (the one here only works for natural numbers...). There are several different algorithms for addition, and many for multiplication. These are not all trivial.

Re the example here, XOR is not the only way to swap two numbers, but it is just quite an easy one to understand since it only uses one operation. If the numbers to be swapped are in registers A,B and have initial values a,b the following also works:

A <- A - B (A contains a-b)
B <- B + A (B contains a)
A <- B - A (A contains (a - (a-b) = b)

The reason the XOR method would be preferred is that it applies to the whole length of the numbers being swapped. The algorithm given here might not work if there are problems with the carry bit/overflow situations, whereas the XOR algorithm should always work. David Martland 09:36, 28 Oct 2003 (UTC)

I have found that it is easier to see what is going on by using this addition reasoning, since XOR is the same as bitwise addition modulo 2. (While I'm here, I'd like to suggest emphasising the special case bug a bit more, and mentioning it in the introductory material.) PML.
Addition is not one algorithm, there's plenty of ways to do that, same way GCD isn't an algorithm, but euclid's algorithm is a gcd algorithm.
So, the other addition algorithms are still algorithms, it doesn't make them invalid in any way. The actual number that is the gcd of two numbers isn't an algorithm, but the method you use to calculate the gcd is. Dysprosia 10:44, 28 Oct 2003 (UTC)

I'm sorry, I'm abit off topic, but why do so many programming related pages in wikipedia look like a cross between a programming guide and a flame war? I couldn't find any general guidelines specific to programming or sciene in the FAQs. Shouldn't pages like this and others talk more about the history or sociology or wide-speadity of entries, instade of recommending wherther or not to do them, or wherther or not their are efficient? how should 'code' examples look in wikipedia? too many prg pages start with demostrating how good or bad a certain technic or prg lang is or is not...

Yes, you are a bit off topic :) Only messing. Anyway. I don't see how this article looks like a flame-war, the discussion down the bottom is a discussion, and can't really be a flame war because it's supposed to be NPOV.
What is wrong discussing the efficiency of an algorithm? Many studies are done into the efficiency and practicability of algorithms. Dysprosia 10:34, 5 Nov 2003 (UTC)
For what it is worth, I did a test of the XOR swapping method versus using a temporary variable when swapping 32-bit integers on a P4. Using a temp var was nearly four times as fast. Bubba73 18:56, July 14, 2005 (UTC)

[edit] Machine instructions

First:

However, all x86 microprocessors have an XCHG instruction which does the same work on its operands more efficiently than the above sequence of XORs.

Then:

In actual code, the need to exchange the contents of two variables occurs frequently. At least one machine, the Datacraft (later Harris) 6024 series did provide such a capability (...)

So x86 processors support this operation but later they might not? Are there others? I'm not an expert on what instructions CPU:s support, so I won't edit.Fredrik 01:45, 5 Mar 2004 (UTC)

Ignorance (of the X86), stupidity, and carelessness (failure to read the preceding article) on my part, I'm afraid. Dpbsmith 01:58, 5 Mar 2004 (UTC)
So, we are left with the puzzle that we have a commonly needed operation, that is efficiently implemented in the most popular machine architecture available, but has no compact way to express it in a high-level language. Do X86 environments typically provide macros or library calls or any other way to tell the compiler that you're trying to swap two variables and the XCHG instruction should be used?
The x86 XCHG afaik can only swap integers. Swapping in higher level languages takes a bit more effort. Dysprosia 10:32, 5 Mar 2004 (UTC)
How the heck is an integer different from any other kind of data (with the same number of bits?) Dpbsmith 11:00, 5 Mar 2004 (UTC)
I apologize - what I mean is, for example, if you have, say, a C structure or union, XCHG on its own isn't going to work - you either have to copy the memory block the struct/union occupies, or, copy each component of the struct one by one, making sure you're not violating/changing any extra alignment padding. Dysprosia 11:24, 5 Mar 2004 (UTC)
There's no need for special macros. Most modern C compilers are good at optimization - they can be expected to use XCHG if it's useful to do so. (But it's not useful as frequently as you might think. The exchange of two ints can often be avoided completely by being careful about which registers are used to store intermediate results, and compilers such as GCC are clever enough to do this.) --Zundark 13:39, 5 Mar 2004 (UTC)
There's no need for a ++ operator either; the good old ALGOL a := a + 1 expresses the intention well enough and most compiler optimizers can handle it. That doesn't mean ++ wasn't a good idea.
More to the point... I added the section on machines with hardware swap capability, but I'm now unsure whether or not it belongs. I still think it does have some relevance, but it's a bit marginal, and if someone wants to delete it, I'm not going to try to restore it. Dpbsmith 13:47, 5 Mar 2004 (UTC)
I've been told that ++ exists in C because it maps nicely to a PDP-11 opcode for increment. Dysprosia 13:54, 5 Mar 2004 (UTC)

[edit] Parallelisation

One paragraph in the article states that modern computer can do parallel computation and hence other swap algorithm may be faster than the XOR swap. Can someone explain how other swapping technique achieve parallel processing?

Take the vanilla approach for example.

var tmp1 <- var A
var A <- var B
var B <- var tmp1

regardless how you slice and dice the steps and memory access to the registers. You still have to wait till the data transfer is complete before you can do the next step, even if you parallellize everything, these operation needs to be synchronized. How would parallellism benefit? Am I missing something?

Here's a parallel version:
tmp1 <- A  ||  tmp2 <- B
B <- tmp1  ||  A <- tmp2
-- Smjg 16:52, 12 Apr 2005 (UTC)

The XOR algorithm was commonly known to assembly language programmers many years ago. It gets the best benefit at register level when memory access is eliminated and the use of an intermediate register is eliminated. I don't see why someone what to do this trick in high level languages because this kind of optimization can be automated by a good code generator of a compiler.

Modern PC processors use register renaming. Therefore one register in your machine code may map to different physical registeres on the CPU. What matters is the dependency chain, that is what instructions depend on what other instructions not really what registers the programmer decided to call the result. Plugwash 10:29, 22 March 2006 (UTC)

[edit] Generalisation

Has anyone tried generalising the xor swap algorithm to cyclic permutations of three or more values?

It is possible to write the 3-cycle as five ^= statements

x ^= y;
y ^= x;
z ^= x;
x ^= z;
z ^= x ^ y;

but that's still six XOR operations, the same as swapping y<->z and then x<->y.

The interesting question is: Is it possible, for any n, to cycle n variables in place using fewer than 3n operations?

You need a temporary register for storing the result of x ^ y. That means no register space is saved with this algorithm. --Graue 16:59, 18 September 2005 (UTC)

[edit] Caveat is wrong

The caveat section says:

One would assume that "swapping a variable with itself" effectively does nothing. The standard, intuitive algorithm that uses a temporary variable indeed comes out that way, but the XOR algorithm will xor the variable with itself, thus setting it to zero instead.

But this is wrong. Why don't we let A = B = 5, and see what happens:

  1. A := A xor B
    A = 5 xor 5 = 0
  2. B := A xor B
    B = 0 xor 5 = 5
  3. A := A xor B
    A = 0 xor 5 = 5

Sure, there's a zero involved, but then the other property of XOR kicks in: a number XORed with 0 is the number you started with. I'm going to remove this section. MShonle 19:20, 14 August 2005 (UTC)

Ah, looking at this a little further the case where this does break is when X and Y are aliased to the same memory location. A brief sentence could mention this, it doesn't need to be a section. MShonle 21:49, 14 August 2005 (UTC)
Same variable means same memory location. Variable != value. Fredrik Johansson - talk - contribs 21:05, 17 January 2006 (UTC)
If we're going to have a whole article about that trick, and are going to get into the details of how it works, a section could easily be dedicated to pointing out this flaw and working it out. Aliasing can occur in many situations, starting with random shuffles or sorting algorithms that use a sentinel. If your basic swap operation breaks in such cases, you're in for a world of hurt. This deserves more than just a passing mention. 199.111.193.97 04:48, 22 March 2006 (UTC)

[edit] application?

When would you wish to swap values (say on an abacus)? Why can one not simply use B instead of A when needed? Even when doing something like sorting, say: a. check if A>B b. if (a) then swap A,B

would need some register to store the result of A-B etc.

[edit] Too much strength given to the xor swap.

I'm going to edit this page shortly, but I thought I'd ask for some comments first.

Firstly, "Another advantage is that this algorithm is actually easier to remember and write without mistakes than the standard temporary variable swap algorithm.."

Surely that is not true? You have to remember to write first to the variable you copied into the temp. That is all you have to remember. Surely that's easier than what is written down.

Also, one very important thing I think is missing from this article is that when using an optimising compiler for a language like C, C++, java, then a temporary is almost always better.

This is because any optimising compiler will turn:

int temp = a;
a = b;
temp = a;

into:

Load a into register 1
Load b into register 2
Put register 1 into memory location b
Put register 2 into memory location a

and if a and b are already in register, the "temporary variable swap" will turn into no code at all, and the compiler will just note that the locations of the variables have swapped around.

If it is ever better to swap the variables using the xor trick, then your compiler will know about it :) —The preceding unsigned comment was added by Mrjeff (talk • contribs).

Yep. This is mentioned in the article, but I agree that it needs work. People keep adding little snippets of (mis?)information about assembly programming on various platforms, the history of C, and whatnot, which really ought to be consolidated into coherent sections of the article. For example, there could be one section on the abstract algorithm, one section on actual (documented) uses, and one section on reasons it should never be used. :) However, it needs to be worked out so that people don't keep reading the first paragraph, discovering that it doesn't mention how many CPU cycles XOR swap takes on a PDP-42, and adding that in. There needs to be a clearly demarcated section for random machine-language exhumations. --Quuxplusone 05:52, 16 April 2006 (UTC)

[edit] Proposed merge of XOR and ADD/SUB article pairs

I propose to briefly summarize Swap by addition and subtraction as a section of the XOR swap algorithm article, and change the former into a redirect. The two methods share everything in common except for the particular arithmetic operator they choose to use.

At the same time, I propose to briefly summarize Subtraction edge as a section of the XOR linked list article, and change the former into a redirect. The two methods, blah, blah, blah.

Discuss here; I'll perform the merges in a few days if I hear no strong objections. --Quuxplusone 03:39, 28 November 2006 (UTC)

Sure. Ideally this would involve renaming the articles to something more inclusive, but I can't think of anything. Deco 05:54, 28 November 2006 (UTC)
I don't think they should be merged as they are different methods after all. Also, in practive, swap by addition and subtraction is not done.... However, it would be good to have them links under the see also section. --Cyktsui 23:33, 6 December 2006 (UTC)
Retrieved from "http://en.wikipedia.org../../../x/o/r/Talk%7EXOR_swap_algorithm_3a54.html"