 | This article has multiple issues. Please helpimprove it or discuss these issues on thetalk page.(Learn how and when to remove these messages) (Learn how and when to remove this message)
|
Incomputer programming, the act ofswapping twovariables refers to mutually exchanging the values of the variables. Usually, this is done with the data inmemory. For example, in aprogram, two variables may be defined thus (inpseudocode):
data_item x := 1data_item y := 0swap (x, y);
After swap() is performed,x will contain the value 0 andy will contain 1; their values have been exchanged. This operation may be generalized to other types of values, such asstrings and aggregateddata types.Comparison sorts use swaps to change the positions of data.
In manyprogramming languages the swapfunction is built-in. InC++overloads are provided allowing std::swap to exchange some large structures in O(1) time.
The simplest and probably most widely used method to swap two variables is to use a thirdtemporary variable:
define swap (x, y) temp := x x := y y := temp
While this is conceptually simple and in many cases the only convenient way to swap two variables, it uses extra memory. Although this should not be a problem in most applications, the sizes of the values being swapped may be huge (which means the temporary variable may occupy a lot of memory as well), or the swap operation may need to be performed many times, as in sorting algorithms.
In addition, swapping two variables inobject-oriented languages such asC++ may involve one call to theclassconstructor anddestructor for the temporary variable, and three calls to thecopy constructor. Some classes may allocate memory in the constructor and deallocate it in the destructor, thus creating expensive calls to the system. Copy constructors for classes containing a lot of data, e.g. in anarray, may even need to copy the data manually.
XOR swap uses theXOR operation to swap two numeric variables. It is generally touted to be faster than the naive method mentioned above; however it does havedisadvantages. XOR swap is generally used to swap low-level data types, likeintegers. However, it is, in theory, capable of swapping any two values which can be represented by fixed-lengthbitstrings.
This method swaps two variables by adding and subtracting their values. This is rarely used in practical applications, mainly because:
Containers which allocate memory from theheap usingpointers may be swapped in a single operation, by swapping the pointers alone. This is usually found in programming languages supporting pointers, likeC orC++. TheStandard Template Library overloads its built-in swap function to exchange the contents of containers efficiently this way.[1]
As pointer variables are usually of a fixed size (e.g., most desktop computers have pointers 64bits long), and they are numeric, they can be swapped quickly usingXOR swap.
Some languages, likeRuby,Julia orPython supportparallel assignments, which simplifies the notation for swapping two variables:
a, b = b, a
This is shorthand for an operation involving an intermediate data structure: in Python and Julia, a tuple; in Ruby, an array.
Javascript 6+ supports destructuring operators which do the same thing:
[a, b] = [b, a];
Here, two globally scoped variables are passed by value through a function, eliminating the need for a temporary storage variable.
x=1;y=2;console.log(x+" "+y);// outputs 1 2functionswap(a,b){x=b;y=a;}swap(x,y);console.log(x+" "+y);// outputs 2 1
Because of the many applications of swapping data in computers, mostprocessors now provide the ability to swap variables directly through built-in instructions.x86 processors, for example, include anXCHG instruction to swap tworegisters directly without requiring that a third temporary register is used. Acompare-and-swap instruction is even provided in some processor architectures, which compares and conditionally swaps two registers. This is used to supportmutual exclusion techniques.
XCHG may not be as efficient as it seems. For example, inx86 processors,XCHG will implicitly lock access to any operands inmemory to ensure the operation isatomic, and so may not be efficient when swapping memory. Such locking is important when it is used to implement thread-safe synchronization, as inmutexes. However, anXCHG is usually the fastest way to swap two machine-size words residing inregisters.Register renaming may also be used to swap registers efficiently.
With the advent ofinstruction pipelining in modern computers andmulti-core processors facilitatingparallel computing, two or more operations can be performed at once. This can speed up the swap using temporary variables and give it an edge over other algorithms. For example, theXOR swap algorithm requires sequential execution of three instructions. However, using two temporary registers, two processors executing in parallel can swap two variables in two clock cycles:
Step 1 Processor 1: temp_1 := X Processor 2: temp_2 := YStep 2 Processor 1: X := temp_2 Processor 2: Y := temp_1
More temporary registers are used, and four instructions are needed instead of three. In any case, in practice this could not be implemented in separate processors, as it violates Bernstein's conditions for parallel computing. It would be infeasible to keep the processors sufficiently in sync with one another for this swap to have any significant advantage over traditional versions. However, it can be used to optimize swapping for a single processor with multiple load/store units.
