In
computer programming
Computer programming is the process of performing a particular computation (or more generally, accomplishing a specific computing result), usually by designing and building an executable computer program. Programming involves tasks such as anal ...
, the act of swapping two
variable
Variable may refer to:
* Variable (computer science), a symbolic name associated with a value and whose associated value may be changed
* Variable (mathematics), a symbol that represents a quantity in a mathematical expression, as used in many ...
s refers to mutually exchanging the values of the variables. Usually, this is done with the data in
memory
Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remembered ...
. For example, in a
program
Program, programme, programmer, or programming may refer to:
Business and management
* Program management, the process of managing several related projects
* Time management
* Program, a part of planning
Arts and entertainment Audio
* Progra ...
, two variables may be defined thus (in
pseudocode):
data_item x := 1
data_item y := 0
swap (x, y);
After swap() is performed, ''x'' will contain the value 0 and ''y'' will contain 1; their values have been exchanged. This operation may be generalized to other types of values, such as
strings
String or strings may refer to:
*String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects
Arts, entertainment, and media Films
* ''Strings'' (1991 film), a Canadian anim ...
and aggregated
data types.
Comparison sorts use swaps to change the positions of data.
In many
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
s the swap
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
is built-in. In
C++
C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
,
overloads are provided allowing std::swap to exchange some large structures in O(1) time.
Using a temporary variable
The simplest and probably most widely used method to swap two variables is to use a third
temporary variable
In computer programming, a temporary variable is a variable with short lifetime, usually to hold data that will soon be discarded, or before it can be placed at a more permanent memory location. Because it is short-lived, it is usually declared ...
:
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 in
object-oriented
Object-oriented programming (OOP) is a programming paradigm based on the concept of " objects", which can contain data and code. The data is in the form of fields (often known as attributes or ''properties''), and the code is in the form of p ...
languages such as
C++
C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
may involve one call to the
class
Class or The Class may refer to:
Common uses not otherwise categorized
* Class (biology), a taxonomic rank
* Class (knowledge representation), a collection of individuals or objects
* Class (philosophy), an analytical concept used differentl ...
constructor and
destructor for the temporary variable, and three calls to the
copy constructor
In class-based, object-oriented programming, a constructor (abbreviation: ctor) is a special type of subroutine called to create an object. It prepares the new object for use, often accepting arguments that the constructor uses to set required ...
. 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 an
array
An array is a systematic arrangement of similar objects, usually in rows and columns.
Things called an array include:
{{TOC right
Music
* In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...
, may even need to copy the data manually.
XOR swap
:
XOR swap uses the
XOR operation to swap two numeric variables. It is generally touted to be faster than the naive method mentioned above; however it does have
disadvantages. XOR swap is generally used to swap low-level data types, like
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
s. However, it is, in theory, capable of swapping any two values which can be represented by fixed-length
bitstring
A bit array (also known as bitmask, bit map, bit set, bit string, or bit vector) is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level ...
s.
Swap through addition and subtraction
This method swaps two variables by adding and subtracting their values. This is rarely used in practical applications, mainly because:
* It can only swap numeric variables; it may not be possible or logical to add or subtract complex data types, like
containers
A container is any receptacle or enclosure for holding a product used in storage, packaging, and transportation, including shipping.
Things kept inside of a container are protected on several sides by being inside of its structure. The term ...
.
* When swapping variables of a fixed size,
arithmetic overflow
Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers—addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th ce ...
becomes an issue.
* It does not work generally for floating-point values, because
floating-point arithmetic is
non-associative
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement ...
.
Swapping containers
Containers
A container is any receptacle or enclosure for holding a product used in storage, packaging, and transportation, including shipping.
Things kept inside of a container are protected on several sides by being inside of its structure. The term ...
which allocate memory from the
heap using
pointers
Pointer may refer to:
Places
* Pointer, Kentucky
* Pointers, New Jersey
* Pointers Airport, Wasco County, Oregon, United States
* The Pointers, a pair of rocks off Antarctica
People with the name
* Pointer (surname), a surname (including a lis ...
may be swapped in a single operation, by swapping the pointers alone. This is usually found in programming languages supporting pointers, like
C or
C++
C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
. The
Standard Template Library
The Standard Template Library (STL) is a software library originally designed by Alexander Stepanov for the C++ programming language that influenced many parts of the C++ Standard Library. It provides four components called ''algorithms'', '' ...
overloads its built-in swap function to exchange the contents of containers efficiently this way.
As pointer variables are usually of a fixed size (e.g., most desktop computers have pointers 64
bit
The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represente ...
s long), and they are numeric, they can be swapped quickly using
XOR swap.
Parallel assignment
Some languages, like
Ruby
A ruby is a pinkish red to blood-red colored gemstone, a variety of the mineral corundum ( aluminium oxide). Ruby is one of the most popular traditional jewelry gems and is very durable. Other varieties of gem-quality corundum are called ...
or
Python
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (pro ...
support
parallel 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, a tuple; in Ruby, an array.
Javascript 6+ supports destructuring operators which do the same thing:
, b
The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline o ...
= , a
The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline ...
Function swap
Here, two globally scoped variables are passed by value through a function, eliminating the need for a temporary storage variable.
Facilitation of swapping in modern computers
Dedicated instructions
Because of the many applications of swapping data in computers, most
processor
Processor may refer to:
Computing Hardware
* Processor (computing)
**Central processing unit (CPU), the hardware within a computer that executes a program
*** Microprocessor, a central processing unit contained on a single integrated circuit (I ...
s now provide the ability to swap variables directly through built-in instructions.
x86
x86 (also known as 80x86 or the 8086 family) is a family of complex instruction set computer (CISC) instruction set architectures initially developed by Intel based on the Intel 8086 microprocessor and its 8088 variant. The 8086 was intr ...
processors, for example, include an ''XCHG'' instruction to swap two
register
Register or registration may refer to:
Arts entertainment, and media Music
* Register (music), the relative "height" or range of a note, melody, part, instrument, etc.
* ''Register'', a 2017 album by Travis Miller
* Registration (organ), th ...
s directly without requiring that a third temporary register is used. A
compare-and-swap
In computer science, compare-and-swap (CAS) is an atomic instruction used in multithreading to achieve synchronization. It compares the contents of a memory location with a given value and, only if they are the same, modifies the contents of tha ...
instruction is even provided in some processor architectures, which compares and conditionally swaps two registers. This is used to support
mutual exclusion
In computer science, mutual exclusion is a property of concurrency control, which is instituted for the purpose of preventing race conditions. It is the requirement that one thread of execution never enters a critical section while a concurrent ...
techniques.
''XCHG'' may not be as efficient as it seems. For example, in
x86
x86 (also known as 80x86 or the 8086 family) is a family of complex instruction set computer (CISC) instruction set architectures initially developed by Intel based on the Intel 8086 microprocessor and its 8088 variant. The 8086 was intr ...
processors, ''XCHG'' will implicitly lock access to any operands in
memory
Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remembered ...
to ensure the operation is
atomic, and so may not be efficient when swapping memory. Such locking is important when it is used to implement thread-safe synchronization, as in
mutex
In computer science, a lock or mutex (from mutual exclusion) is a synchronization primitive: a mechanism that enforces limits on access to a resource when there are many threads of execution. A lock is designed to enforce a mutual exclusion concur ...
es. However, an ''XCHG'' is usually the fastest way to swap two machine-size words residing in
register
Register or registration may refer to:
Arts entertainment, and media Music
* Register (music), the relative "height" or range of a note, melody, part, instrument, etc.
* ''Register'', a 2017 album by Travis Miller
* Registration (organ), th ...
s.
Register renaming
In computer architecture, register renaming is a technique that abstracts logical registers from physical registers.
Every logical register has a set of physical registers associated with it.
When a machine language instruction refers to a partic ...
may also be used to swap registers efficiently.
Parallel execution
With the advent of
instruction pipelining
In computer engineering, instruction pipelining or ILP is a technique for implementing instruction-level parallelism within a single processor. Pipelining attempts to keep every part of the processor busy with some instruction by dividing incom ...
in modern computers and
multi-core processors facilitating
parallel 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, the
XOR 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 := Y
Step 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.
References
{{DEFAULTSORT:Swap (Computer Science)
Programming idioms