3

Assume you have two variables a and b, and you need to swap them, and for whatever reason, making a temporary variable for storage is not an option. This is the algorithm in pseudocode

a ← a XOR b
b ← a XOR b
a ← a XOR b

Based on examples I can see that this does work.

But, why does it work?

More specifically, how was this derived? Was it a mere coincidence that XOR such and such values does this? This question applies to all bitwise operators.

I understand perfectly what they do, and how they work, and various algorithms that take advantage of them. But, are there mathematical properties of these bitwise operators that these algorithms are derived from? What are those mathematical properties? And which of them apply to the specific example of an XOR swap?

  • 3
    "Are there mathematical properties of these bitwise operators that these algorithms are derived from?" Yes. "What are those mathematical properties?" that's too broad for here. See Knuth volume 4A for a start if you have a mathematical mind. – AProgrammer Jan 29 '14 at 8:53
  • I have a copy of the full set, I'm assuming it's the K&R kind of book where it's perfectly fair to jump around, and isn't meant to be read linearly? – David Jan 29 '14 at 14:55
  • yes. (Note that the volume 4A is far more recent than the others and that it may be absent of your full set depending on when you bought it, I know it was published after I bought mine). – AProgrammer Jan 29 '14 at 15:21
10

This can be done with any invertable binary operation like XOR or addition. So you could just as well write:

 a ← a + b
 b ← a - b
 a ← a - b

Or more generally, suppose that for some binary (associative, commutative) operator # there is an identity i such that

x # i = i # x = x

and that for every value x there is a value x' such that

x # x' = i

Then you can swap two values using that operator:

a ← a # b
b ← a # b'
a ← a # b'

For addition, x' = -x, but for XOR we have x XOR x = 0 so that x' = x, so that:

a ← a XOR b
b ← a XOR b'
a ← a XOR b'

reduces to

a ← a XOR b
b ← a XOR b
a ← a XOR b
| improve this answer | |
  • Thanks for the edit. I'm not sure the operator has to be commutative. – kevin cline Jan 29 '14 at 18:55
  • Great point. The only reason we need to use XOR for this "trick" rather than addition and subtraction is that it cannot overflow, where +/- can, with fixed-size integers. – Carson63000 Jan 30 '14 at 0:41
  • 1
    @Carson63000: It doesn't matter if there is overflow, as long as a + b - b is always equal to a. – kevin cline Jan 30 '14 at 6:37
  • 1
    @kevincline It has not to be commutative and it does not need to have a left inverse or even a left unit. :-) But computationally, this algorithm is probably only relevant for machine words as a and b and using XOR as #. – user40989 Jan 30 '14 at 8:44
  • If this works with any commutative operator, then why do we use XOR instead of addition? Is it because it takes less CPU operations? – David Mar 2 '14 at 1:05
5

More specifically, how was this derived? Was it a mere coincidence that XOR such and such values does this? This question applies to all bitwise operators.

These bitwise operations correspond to well-known elementary operations from higher-algebra that I will briefly describe.

Modular arithmetic

The first important item is modular arithmetic—which is a special kind of computations a quotient ring. Even if you do not suspect it you are already familiar with special cases of modular arithmetic.

If we choose a positive integer N that we call the modulo we can compute on residues modulo N which is just like computing with normal numbers and pretending than N = 0. All the usual computation rules on integers still hold, with two provisions:

  • For residues a = b modulo N means that the integers a and b differ by a multiple of N.

  • For residues modulo N the relation m × a = m × b does not imply that a = b even if m is non-zero modulo N. [RSA]

But the remaining usual relations still hold. Let us review a few examples.

  • If January the 2nd is a Thursday, then February the 2nd is a Sunday because we identify days with residues modulo 7 and, January having 31 days, we write

    2 + 31 = 2 + 4 × 7 + 3 = 2 + 3 = 5

    so that February the 2nd is the same day of the week as January the 5th, a Sunday.

  • At school we learn to sum up the digits of numbers to check if we performed well a multiplication. We are actually computing on residues modulo 9, so that 10 = 1, and verify that our multiplication is correct modulo 9. (Of course, this is not foolproof, e.g. we would not see if we were off by 9.)

  • When computing on bits, we compute on residues modulo 2 and the addition is XOR, the multiplication is AND. So

    a XOR b = a + b

    a AND b = a × b

    NOT a = 1 XOR a = 1 + a = 1 - a (which is the “good”definition of NOT)

    a OR B = a + b + a × b

As an exercise, you can check that a OR b is NOT(NOT a AND NOT b) by expanding the corresponding algebraic expression. It is also interesting to note that “the easy operation” is XOR and not OR.

[RSA]: As a side note, the RSA system is based on the nultiplicative theory of residues modulo N where N is the product of two prime numbers.

Linear algebra

Linear algebra systematises computations on coordinates. At an elementary level, it is taught with coordinates in the ring R of real numbers and applied to geometry and mechanics. Ring is the mathematical term for a set of coefficients, on which we can compute just like on integers. So, yes, sets of residues modulo a given N are also rings, and can also be as coefficients to do linear algebra.

Now let B be the ring of residues modulo 2, that is 0, 1 endowed with addition and multiplication as above. A machine register, say in a 8 bits machine, but 8 could be any other number, can be seen as a 8-dimensional vector with entries in B, so that a XOR b = a + b, where the addition considered is the addition of vectors with entries in B. (If you consider a and b as 2-complement's representation of some integers, a XOR bhas nothing to do with the sum of these integers.)

XOR-Swap

Now let's take an overpedantic look at the XOR-Swap algorithm. We start with a and b and I write a[k] and b[k] the values of a and b at the various steps of the algorithms.

a[1] ← a[0] + b[0]

b[1] ← a[1] + b[0]

a[2] ← b[1] + a[1]

Note that for these vectors with entries in B we have,

b[1] = a[0] + 2× b[0] = a[0]

a[2] = b[1] + a[1] = 2 × a[0] + b[0] = b[0]

So, by the end of our computation, b holds the initial value of a and a holds the initial value of b.

| improve this answer | |
2

"Why does the algorithm work?" is a subjective concept and primarily opinion-based, so don't feel bad if this question is put on hold. But the closely related "How does it work?" can be answered, so I'll have a go.

First of all, XOR is special in that it preserves all information that you put into it: it maps 1 to 0 and 0 to 1 (when applied to 1) and 0 to 0 and 1 to 1 (when applied to 0). This is important, because without that property the trick couldn't work. For instance, logical AND is not information-preserving: if you AND 0 to a value, you'll always get 0 no matter what the left hand side was, so you cannot reconstruct the input from the output.

Also, it's cyclical: if you XOR the same value to one number twice, you get the original number back. This isn't hard to see, because every 0 in the number turns into a 1 and then back again to 0, and vice versa. This is also critical for the trick to work.

After the first step, a has been overwritten with a different value, but the information about that value is still present. The original value is the one that you would get if you applied XOR b to it again, and that's what happens in the second step. The third step repeats this trick for b, but because b has already been changed in the second step, the final a = a XOR b effectively executes two XOR operations, ending up with exactly the original value of b.

That is as close as I can come to explaining why I think the method works, but note that to acquire an intuitive understanding of such tricks, nothing beats actually performing the computation yourself. Pick a couple of two-digit binary numbers, get a piece of paper, and get busy assigning. Better yet, get all 16 combinations of two-digit binary numbers and compute all those 48 steps on paper. It's almost impossible not to understand the XOR information flow after that.

| improve this answer | |
0

why bitwise algorithms work? because someone found it and proved they worked for all values.

if you remember that a^b = b^a and a^a=0 and a^0=a then you can expand the algorithm as:

a'=a^b;
b'=a'^b;
a''=a'^b';

or

b'=(a^b)^b=a^(b^b)=a;
a''=((a^b)^b)^(a^b)=a^b^b^a^b=a^a^b=b;

that said I believe that this is useless in modern languages because the optimizer will recognize the "temp var swap" (tmp=a;a=b;b=tmp;) and optimize as needed.

Plus on RISC architectures you need to load the variables into a register before you can xor them and if you have them both in registers you can just write them out in opposite places. This means that is is only useful if there is a direct xor on the locations and there isn't an extra location to store the temporary.

| improve this answer | |
0

But, why does it work?

Since XOR works bitwise, it is enough to assume that a and b are just one bit long. In this case, XOR is just the same thing as the addition modulo 2. Now if a[0] and b[0] denote the value of a and b before the calculation and a[1] and b[1] their value after, we have (modulo 2):

 a[1] = b[0] + 2*a[0] = b[0]
 b[1] = a[0] + 2*b[0] = a[0]

If you are in a pedantic mood, you can pack all this in a little sentence: we are computing in a vector space of characteristic two and XOR is just the addition of vectors.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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