1

Simply, 

X = Integer
Y = Another Integer

Z ( If used ,Integer Temp )

What's the most efficient method ?

Method I :

Z = X
X = Y
Y = Z

Method II :

X ^= Y
Y ^= X
X ^= Y

Edit I [ Assembly View ]

Method I : 

MOV  
MOV  
MOV

Method II : 

TEST ( AND )  
JZ  
XOR  
XOR  
XOR

Notes :

  • MOV is slower then XOR
  • TEST , JZ is used for XOR Equality Safe
  • `Method I uses extra register
Ahmed Ghoneim
  • 6,834
  • 9
  • 49
  • 79
  • 5
    Method 1. Trust your compiler; don't try to fool it. It'll do good things for you. – Michael Petrotta Jun 05 '12 at 03:15
  • @MichaelPetrotta This is not a LOW level concept ! Look as an assembly man, new register vs XORing ? – Ahmed Ghoneim Jun 05 '12 at 03:21
  • 1
    Don't believe me? Benchmark it, with -O3 or equivalent. Make sure you run a few gazillion iters. – Michael Petrotta Jun 05 '12 at 03:23
  • 1
    By the way, I really appreciated the Rube Goldberg nature of Method III (since deleted). – Michael Petrotta Jun 05 '12 at 03:29
  • 1
    @AhmedGhoneim: It's not a question of whether it's a low level concept, but just that it's a fact that compiler builders are very, very good at emitting the most efficient code for the target platform for this type of common operation. – Eric J. Jun 05 '12 at 03:31
  • I was just wondering by the way! Didn't know that this'll be annoying! – Ahmed Ghoneim Jun 05 '12 at 03:36
  • 1
    I think it's a very valid question to ask. In fact, I often use that as an easy warm-up question when interviewing Engineers (not just how to swap, but various approaches and implications). – Eric J. Jun 05 '12 at 03:49
  • I think [this answer](http://stackoverflow.com/a/249469/445976) addresses why the xor "trick" is not necessarily a useful optimization. As always, profile your code on the target hardware. – Blastfurnace Jun 05 '12 at 05:53

2 Answers2

3

In most cases, using a temporary variable (usually a register at assembly level) is the best choice, and the one that a compiler will tend to generate.

In most practical scenarios, the trivial swap algorithm using a temporary register is more efficient. Limited situations in which XOR swapping may be practical include: On a processor where the instruction set encoding permits the XOR swap to be encoded in a smaller number of bytes; In a region with high register pressure, it may allow the register allocator to avoid spilling a register. In microcontrollers where available RAM is very limited. Because these situations are rare, most optimizing compilers do not generate XOR swap code.

http://en.wikipedia.org/wiki/XOR_swap_algorithm

Also, your XOR Swap implementation fails if the same variable is passed as both arguments. A correct implementation (from the same link) would be:

void xorSwap (int *x, int *y) {
     if (x != y) {
         *x ^= *y;
         *y ^= *x;
         *x ^= *y;
     }
 }

Note that the code does not swap the integers passed immediately, but first checks if their addresses are distinct. This is because, if the addresses are equal, the algorithm will fold to a triple *x ^= *x resulting in zero.

Eric J.
  • 147,927
  • 63
  • 340
  • 553
  • I think you're misinformed about instruction timing on modern processors. See the link that @Blastfurnace provided in his comment: http://stackoverflow.com/a/249469/445976 – Eric J. Jun 05 '12 at 05:58
0

Try this way of swapping numbers

int a,b;

a=a+b-(b=a);

abhi120
  • 278
  • 4
  • 15