Fun With Exclusive Or

Exclusive OR is fun. I used it in a very old assembler project (don't ask when :-). The code in question was essentially a case statement. The code loaded the value to be tested in an accumulator, and XOR'ed it with each of the values to be tested against. If the result was zero, a branch on zero instruction invoked the corresponding code. Otherwise, the code would XOR the target value with the accumulator a 2nd time, restoring its original value, before going on to the next test. Fun, but don't try this at home.

If it really did that, the programmer wasn't having enough fun. You don't need to do the restoring-XOR between tests; instead, XOR with value1, then with value1^value2, then with value1^value2^value3, and so on.

Also from an old assembler program: using the identity

 x ^ (2**n - 1) == 2**n - x 

saved a whole (8 bit) instruction. I was converting from the UK BBC Computer (screen height 256 pixels) to the US model (screen height 200) and this was my first 6502 program, and it took me quite a while to work out what the XOR was doing...

That isn't an identity. (You can tell that instantly: look at the parity.) If you have 2**n-1 on both sides, though, you get an identity. Is that what you meant?

---

Don't forget the classic XOR hack for swapping ints without using a temp:

 int a = 3; // 0011
 int b = 4; // 0100
 a ^= b;// a == 0111, b == 0100
 b ^= a;// a == 0111, b == 0011
 a ^= b;// a == 0100, b == 0011

Don't try this at home, kids!

I actually had to use that one once in microcoding a program board which had no capability for swapping two registers. So I used three cycles as you describe and XOR'd them thrice to effect the swap. Doubted I'd ever use it, doubt I'll ever use it again :) -- AlistairCockburn

What about this?

  a ^= b ^= a ^= b;

Modifies a twice between sequence points => undefined behavior.

More generally, one can rotate an array of n values in 3(n-1) XOR operations, without using a temp.

  for (i = 0; i < n-1; i++)
array[i+1] ^= array[i];
  for (i = 0; i < n-1; i++)
array[i] ^= array[i+1];
  for (i = 0; i < n-1; i++)
array[n-1] ^= array[i];

Probably only worth the trouble for n=2, though. More formally inclined people may note that any group operation ^ with the property that for all x, x^x=identity, will work. [Such a group must be commutative.]

Finally, observe that since any permutation can be decomposed into a set of independent cycles, it is now obvious that any permutation of n integers can be done in-place with at most (worst case) 3(n-1) XORs. The best case is of course 0, for the identity permutation.

Well, that is enough rigour to promote the XOR trick from a hack to an official Technique (TM), methinks ;-)

It should be noted that it might backfire on modern architectures. For instance, gcc on intel x86 will generate faster code if you just use a temporary (only slightly faster with optimizations; 1 xchg @ 3 cycles vs. 3 mov @ 1 cycle each). Same goes for using substraction in a similar way, gcc will detect it and generate xchg instructions which don't seem to save anything.

---

Then, there's always the memory-clearing mechanism:

 n ^= n;

When would you do this instead of just assigning zero?

- Some early machines lacked immediate load operators, and their programmers would resort to odd tricks like SUB A,A to get a zero.

- On a Z80, xor a is one byte; ld a,#0 is two.

- On an x86, xor ebx, ebx is idiomatic to clear ebx. It is much shorter than the perhaps more logical:

mov ebx, 0

The latter has to encode a 32-bit integer value in the instruction. The 'xor ebx, ebx' instruction is generated by all compilers I am aware of. It is also the instruction Intel recommends to clear a register. Intel processors after the original Pentium special-case this instruction to make it extra efficient.

-- StephanHouben plus anonymous contributors

Certainly in the old days (I haven't coded in assembler for years), arithmetic operations affected the condition codes differently from assignment operations, leading to differences in subsequent branching behavior. I always assumed (without any particular evidence) that this was the motivation for the Intel recommendations. Further, in microcoded machines (such as the PERQ), arithmetic operations were a more direct route to microcode magic (such as using one routine to reliably clear LHS's of varying width).

Certainly: xor eax, eax changes various flags. If you need to preserve the flags, mov eax, 0 may be your only option.

---

There's another'un on: TwoPointersInOneWord. And yet another in ThreePointersInOneWordAndOneBit.

---

Another interesting application : http://www.mactech.com/articles/mactech/Vol.01/01.12/PICTRotation/.

---

Here's how to add two numbers without using addition or subtraction:

 unsigned int Add(unsigned int n1, unsigned int n2)
 {
while (n2 != 0)
{
unsigned int sum = n1 ^ n2;
n2 = (n1 & n2) << 1;
n1 = sum;
}
return n1;
 }

If you're programming in INTERCAL that may be useful, but otherwise use + to take advantage of carry-prediction.