Swap Using XOR Operations

From Software Engineers Wiki
Jump to: navigation, search

Swap two integer variables without using a temporary variable.

Answer 1: XOR

XOR operation has a special property that, if XOR operation is done twice with same value, the result becomes same as original value. That is,

A XOR B XOR B becomes A regardless of value of B.

Using this property, we can swap two variables without using temporary variable. If there are two variables named a and b.

  • b = a xor b xor b
  • a = a xor b xor a

Following is the code that actually swaps two variable. For your understanding, in the comments, A is original value of a and B is original value of b.

a = a ^ b; /* a = A ^ B, b = B */
b = a ^ b; /* a = A ^ B, b = A ^ B ^ B = A */
a = a ^ b; /* a = A ^ B ^ A = B, b = A */

But this trick has a problem when the two variables are actually same variable.

#define swap_xor(a, b) \
    do { \
        a = a ^ b; \
        b = a ^ b; \
        a = a ^ b; \
    } while (0)

int a = 10;
swap_xor(a, a);

or

void swap_xor(int *a, int *b)
{
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}

int a = 10;
swap_xor(&a, &a);

Answer 2: Arithmetic

Another way is

  • a = difference between a and b : a - b
  • b = b + difference
  • a = b - difference
void swap_arithmetic(int *a, int *b)
{
    *a = *a - *b;
    *b = *a + *b;
    *a = *b - *a;
}

Comparison with temporary variable method

But is this really better than using temporary variable?

void swap_temp(int *a, int *b)
{
    int t;

    t = *a;
    *a = *b;
    *b = t;
}

void swap_xor(int *a, int *b)
{
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}

For 32-bit x86 architecture, gcc compiles above codes as follows with -O2 option.

080483d0 <swap_temp>:
 80483d0:       53                      push   %ebx
 80483d1:       8b 54 24 08             mov    0x8(%esp),%edx ; edx = address of a
 80483d5:       8b 44 24 0c             mov    0xc(%esp),%eax ; eax = address of b
 80483d9:       8b 0a                   mov    (%edx),%ecx ; ecx = (edx) = *a
 80483db:       8b 18                   mov    (%eax),%ebx ; ebx = (eax) = *b
 80483dd:       89 1a                   mov    %ebx,(%edx) ; *a = ebx
 80483df:       89 08                   mov    %ecx,(%eax) ; *b = eax
 80483e1:       5b                      pop    %ebx
 80483e2:       c3                      ret

080483f0 <swap_xor>:
 80483f0:       8b 4c 24 08             mov    0x8(%esp),%ecx ; ecx = address of b
 80483f4:       8b 44 24 04             mov    0x4(%esp),%eax ; eax = address of a
 80483f8:       8b 11                   mov    (%ecx),%edx ; edx = (ecx) = *b
 80483fa:       33 10                   xor    (%eax),%edx ; edx = (eax) ^ edx = *a ^ *b
 80483fc:       89 10                   mov    %edx,(%eax) ; *a = edx = *a ^ *b
 80483fe:       33 11                   xor    (%ecx),%edx ; edx = (ecx) ^ edx = *a ^ *b
 8048400:       89 11                   mov    %edx,(%ecx) ; *b = edx = *a ^ *b
 8048402:       31 10                   xor    %edx,(%eax) ; *a = *a ^ *b
 8048404:       c3                      ret

For swap_temp(), the program anyway needs to load two variables to registers, it doesn't need any other register as a temporary variable. In C code, it appears a temporary variable is needed, but actually this doesn't happen.

However, swap_xor() requires additional memory access and instructions because it performs three extra xor operations.

For ARM architecture, the difference is more obvious.

00000000 <swap_temp>:
   0:   e5903000        ldr     r3, [r0]
   4:   e5912000        ldr     r2, [r1]
   8:   e5802000        str     r2, [r0]
   c:   e5813000        str     r3, [r1]
  10:   e12fff1e        bx      lr

00000014 <swap_xor>:
  14:   e5912000        ldr     r2, [r1]
  18:   e5903000        ldr     r3, [r0]
  1c:   e0223003        eor     r3, r2, r3
  20:   e5803000        str     r3, [r0]
  24:   e5912000        ldr     r2, [r1]
  28:   e0233002        eor     r3, r3, r2
  2c:   e5813000        str     r3, [r1]
  30:   e5902000        ldr     r2, [r0]
  34:   e0223003        eor     r3, r2, r3
  38:   e5803000        str     r3, [r0]
  3c:   e12fff1e        bx      lr

swap_temp() requires 2 loads and 2 stores. However swap_xor() requires 4 loads and 4 stores and 3 exclusive or operations. In summary, swap_xor() is slower than swap_temp() and swap_xor() is not safe from aliasing issue.

Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox