Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

The XOR swap is a well-known in-place algorithm to swap two values, by XOR:ing them bitwise. It goes as follows:

a = a ^ b
b = a ^ b
a = a ^ b

Now, I was thinking to myself if I can find a way to help with my intuition regarding this algorithm. And here's what I thought of:

Bitwise XOR is the same as bitwise addition (1 + 1 = 0, as the carry is lost). Hence, if we write down the operations as addition, we get:

a = a + b
b = a + b + b
a = a + b + a + b + b

I then cancel any matching pair, i.e. b simply becomes a and a becomes b + b + b, which becomes b.

This is all very simple, so does it hold up to scrutiny?

share|improve this question
    
To begin with, you should use proper notation. Exclusive or is not addition. So use the operator "^" if that is the notation of your instructor, rather than +. Addition is irrelevant, work with the algebraic properties of exclusive or. Then your second series of assigment is not understandable, as it writes like the first, but should be read differently. It should use the original values of variable, and be written $a=a_0+b_0$, $b=a_0+b_0+b_0$ ..., or rather $a=a_0\hat{}b_0$, $b=a_0\hat{}b_0\hat{}b_0$, ... Then simplify with algebraic properties of XOR (such as cancelling pairs) –  babou Jul 30 at 14:39
2  
@babou um, in boolean algebra, XOR is addition modulo 2. –  Christofer Olsson Jul 30 at 14:41
1  
This is the explanation, though it could be further simplified by replacing the second line with $b=a+b+b=a$ and then the third line becomes $a=a+b+a=b$. And of course babou is right that the left-hand $a,b$ are not the same as the right-hand $a,b$, which is rather confusing. –  Yuval Filmus Jul 30 at 17:46
1  
@babou Arguably, if translating xor into addition in $\mathbb{Z}/2$ helps with understanding something (about xor), it's worth doing (here). –  Raphael Jul 30 at 21:39
1  
@Raphael I am not saying that relation with $\mathbb{Z}/2$ is uninteresting, only that it is not needed in the proof ... unless one takes Yuval Filmus' aproach, which does not make it necessarily easier for some readers. I would rather be minimalist. But as I already said, I was sure I should have bought a lightning rod before starting this. I do hope the OP enjoys the discussion. –  babou Jul 30 at 22:19

2 Answers 2

Let me mention a generalization of this algorithm, which works in any Abelian group: $$ \begin{align*} x_\text{temp} &= x_\text{in} + y_\text{in} \\ y_\text{out} &= x_\text{temp} - y_\text{in} \\ x_\text{out} &= x_\text{temp} - y_\text{out} \end{align*} $$ The proof is left to the reader. Your case corresponds to the group $\mathbb{Z}_2^n$, in which both operations $+$ and $-$ correspond to XOR.

share|improve this answer
    
Of course, and that means we could theoretically use it for integers. Except for the fact that we might overflow word size while doing it. It is rather cute that binary encoding sort of lends its own ability to all other types of data. (I am afraid we are getting a bit off topic). –  babou Jul 30 at 21:52
    
We can use it for integers. Integer arithmetic is really modulo $2^N$, where $N$ is the word size. In C, you could use x += y; y = x-y; x -= y. –  Yuval Filmus Jul 30 at 21:56
    
You mean nothing catches word overflow after adding? I have not played such games for a very long time. –  babou Jul 30 at 22:01
    
That's right. In x86 CPUs a flag would be raised (silently), but that's it. It is all on purpose, since sometimes you want to do arithmetic modulo $2^{32}$ (say). When multiplying or dividing it makes a difference whether you interpret numbers as signed or unsigned, but addition and subtraction are exactly the same in both cases. –  Yuval Filmus Jul 30 at 22:04
    
Your extension assumes that computing the inverse of an element is simple, mot requiring extra memory, which is not necessarily the case. Then assuming it can be done, the "in-place exchange" property does not even require the group to be abelian. You only have to change the order of operands in the third assignment: a=a+b; b=a+(-b); a=(-a)+b. This requires three extra assignment for inversion, compared to the XOR case, unless left and right substraction are each a single operation (the same one in the abelian case) –  babou Jul 31 at 16:26

Your proof is correct in intention, but the style is not adequate.

Of course, there is no perfect style, and most of us could improve their style, myself included.

Still, hoping readers will not be too harsh, here is an attempt at writing it, as an example, following your own proof. It may be too verbose, one of my own failings. (it is also a bit intentional here)

Actually the style usually depends also on the audience you are addressing. If the intended audience is very competent in the field, you can skip a lot of details. Nevertheless, careful notation always helps (like the indexing $a_0$ below).


The XOR swap is a well-known in-place algorithm to swap two values, by XOR:ing them bitwise. It goes as follows for two variables a and b, using the notation of the C programming language:

a = a^b

b = a^b

a = a^b

Correctness proof

We note the XOR operation $\oplus$ as is common in mathematical uses. This notation is justified by the isomorphism between XOR on the booleans and the addition in $\mathbb{Z}/2$.

The algebraic properties of XOR extend to bitwise operations on bit vectors (i.e., sequences of bits) of equal sizes. In particular it remains associative and commutative, and we have for any sequence $x$ of bits: $x\oplus x=\vec{0}$ where $\vec{0}$ is a bit vector of $0$´s of the same length, and $x\oplus\vec{0}=x$.

Assume the initial values of a and b are respectively $a_0$ and $b_0$.

The 3 assigments above are then equivalent to:

a =$a_0\oplus b_0$

b =$(a_0\oplus b_0)\oplus b_0$ which simplifies algebraically to $a_0$ as indicated above

a =$(a_0\oplus b_0)\oplus a_0$ which simplifies to $b_0$

The initials values of a and b have been swapped bitwise. $\;\Box$


Though I may be in some disagreement over this with other users, I do not see the usefulness for this proof of insisting on the relation between XOR and addition (other than for justifying the notation). Of course, the generalized view of Yuval Filmus]1 brings wider understanding, but the point for me is to have a simple proof, not to write a treatise.

Note that I have been using distinct notation for syntax (taken fron C) and for the semantics of these operations. This justifies having two notations for the XOR operator, and gives a cleaner presentation of the proof, which may sometimes be important.

Of course, one is not always that careful, but it is better to have these principles in mind, without overdoing it, depending on the purpose and audience of what is being written. I think the most important here was to distinguish a and $a_0$.

Hoping this version will satisfy most readers. Further comments welcome.

With my thanks to all for all the very useful comments. Perfection is not of this world.

share|improve this answer
    
The XOR operation (which is addition in the group $\mathbb{Z}_2^n$) is usually denoted by $\oplus$. –  Yuval Filmus Jul 30 at 21:24
    
@YuvalFilmus I agree, and thought of switching to the notation you suggest. But I chose to respect the notation of the OP, which might have been chosen for some unstated reason. Another reason is that the choice of a proper operation symbol is not quite on the same level as my other comments, thought important too. Teaching style is not obvious. Just trying. –  babou Jul 30 at 21:30
1  
The notation ^ comes, as your are well aware, from C. –  Yuval Filmus Jul 30 at 21:31
    
@YuvalFilmus Actually, I have no memory, even though I occasionally program in C. I just look for what I need :-) But I thought it was something of the kind, and C is a good candidate for bitwise operations. –  babou Jul 30 at 21:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.