XOR swap algorithm

Apr 22, 2026 - 05:19
0 0
XOR swap algorithm

Link suggestions feature: 3 links added.

← Previous revision Revision as of 23:48, 21 April 2026
Line 15: Line 15:


Since XOR is a [[commutative operation]], either X XOR Y or Y XOR X can be used interchangeably in any of the foregoing three lines. Note that on some architectures the first operand of the XOR instruction specifies the target location at which the result of the operation is stored, preventing this interchangeability. The algorithm typically corresponds to three [[machine code|machine-code]] instructions, represented by corresponding pseudocode and assembly instructions in the three rows of the following table:
Since XOR is a [[commutative operation]], either X XOR Y or Y XOR X can be used interchangeably in any of the foregoing three lines. Note that on some architectures the first operand of the XOR instruction specifies the target location at which the result of the operation is stored, preventing this interchangeability. The algorithm typically corresponds to three [[machine code|machine-code]] instructions, represented by corresponding [[pseudocode]] and assembly instructions in the three rows of the following table:


{| class="wikitable" style="width: 45em;"
{| class="wikitable" style="width: 45em;"
Line 130: Line 130:
However, the implementation of AddSwap above in the C programming language always works even in case of integer overflow, since, according to the C standard, addition and subtraction of unsigned integers follow the rules of [[modular arithmetic]], i. e. are done in the [[cyclic group]] \mathbb Z/2^s\mathbb Z where s is the number of bits of unsigned int. Indeed, the correctness of the algorithm follows from the fact that the formulas (x + y) - y = x and (x + y) - ((x + y) - y) = y hold in any [[abelian group]]. This generalizes the proof for the XOR swap algorithm: XOR is both the addition and subtraction in the abelian group (\mathbb Z/2\mathbb Z)^{s} (which is the [[direct sum]] of ''s'' copies of \mathbb Z/2\mathbb Z).
However, the implementation of AddSwap above in the C programming language always works even in case of integer overflow, since, according to the C standard, addition and subtraction of unsigned integers follow the rules of [[modular arithmetic]], i. e. are done in the [[cyclic group]] \mathbb Z/2^s\mathbb Z where s is the number of bits of unsigned int. Indeed, the correctness of the algorithm follows from the fact that the formulas (x + y) - y = x and (x + y) - ((x + y) - y) = y hold in any [[abelian group]]. This generalizes the proof for the XOR swap algorithm: XOR is both the addition and subtraction in the abelian group (\mathbb Z/2\mathbb Z)^{s} (which is the [[direct sum]] of ''s'' copies of \mathbb Z/2\mathbb Z).


This doesn't hold when dealing with the signed int type (the default for int). Signed integer overflow is an undefined behavior in C and thus modular arithmetic is not guaranteed by the standard, which may lead to incorrect results.
This doesn't hold when dealing with the signed int type (the default for int). Signed integer overflow is an [[undefined behavior]] in C and thus modular arithmetic is not guaranteed by the standard, which may lead to incorrect results.


The sequence of operations in AddSwap can be expressed via matrix multiplication as:
The sequence of operations in AddSwap can be expressed via matrix multiplication as:
Line 146: Line 146:
On architectures lacking a dedicated swap instruction, because it avoids the extra temporary register, the XOR swap algorithm is required for optimal [[register allocation]]. This is particularly important for [[compilers]] using [[static single assignment form]] for register allocation; these compilers occasionally produce programs that need to swap two registers when no registers are free. The XOR swap algorithm avoids the need to reserve an extra register or to spill any registers to main memory.{{cite book |last1=Pereira |first1=Fernando Magno Quintão |last2=Palsberg |first2=Jens |chapter=SSA Elimination after Register Allocation |title=Compiler Construction |series=Lecture Notes in Computer Science |date=2009 |volume=5501 |pages=158–173 |doi=10.1007/978-3-642-00722-4_12 |isbn=978-3-642-00721-7 |chapter-url=http://compilers.cs.ucla.edu/fernando/publications/papers/CC09.pdf |access-date=17 April 2022}} The addition/subtraction variant can also be used for the same purpose.{{cite book |last1=Hack |first1=Sebastian |last2=Grund |first2=Daniel |last3=Goos |first3=Gerhard |chapter=Register Allocation for Programs in SSA-Form |title=Compiler Construction |series=Lecture Notes in Computer Science |date=2006 |volume=3923 |pages=247–262 |doi=10.1007/11688839_20|isbn=978-3-540-33050-9 |doi-access=free }}
On architectures lacking a dedicated swap instruction, because it avoids the extra temporary register, the XOR swap algorithm is required for optimal [[register allocation]]. This is particularly important for [[compilers]] using [[static single assignment form]] for register allocation; these compilers occasionally produce programs that need to swap two registers when no registers are free. The XOR swap algorithm avoids the need to reserve an extra register or to spill any registers to main memory.{{cite book |last1=Pereira |first1=Fernando Magno Quintão |last2=Palsberg |first2=Jens |chapter=SSA Elimination after Register Allocation |title=Compiler Construction |series=Lecture Notes in Computer Science |date=2009 |volume=5501 |pages=158–173 |doi=10.1007/978-3-642-00722-4_12 |isbn=978-3-642-00721-7 |chapter-url=http://compilers.cs.ucla.edu/fernando/publications/papers/CC09.pdf |access-date=17 April 2022}} The addition/subtraction variant can also be used for the same purpose.{{cite book |last1=Hack |first1=Sebastian |last2=Grund |first2=Daniel |last3=Goos |first3=Gerhard |chapter=Register Allocation for Programs in SSA-Form |title=Compiler Construction |series=Lecture Notes in Computer Science |date=2006 |volume=3923 |pages=247–262 |doi=10.1007/11688839_20|isbn=978-3-540-33050-9 |doi-access=free }}


This method of register allocation is particularly relevant to [[GPU]] shader compilers. On modern GPU architectures, spilling variables is expensive due to limited memory bandwidth and high memory latency, while limiting register usage can improve performance due to dynamic partitioning of the [[register file]]. The XOR swap algorithm is therefore required by some GPU compilers.{{cite web |last1=Abbott |first1=Connor |last2=Schürmann |first2=Daniel |title=SSA-based Register Allocation for GPU Architectures |url=https://indico.freedesktop.org/event/1/contributions/7/attachments/8/11/SSA-based%20Allocation%20for%20GPU%20Architectures.pdf |access-date=17 April 2022}}
This method of register allocation is particularly relevant to [[GPU]] shader compilers. On modern GPU architectures, spilling variables is expensive due to limited [[memory bandwidth]] and high memory latency, while limiting register usage can improve performance due to dynamic partitioning of the [[register file]]. The XOR swap algorithm is therefore required by some GPU compilers.{{cite web |last1=Abbott |first1=Connor |last2=Schürmann |first2=Daniel |title=SSA-based Register Allocation for GPU Architectures |url=https://indico.freedesktop.org/event/1/contributions/7/attachments/8/11/SSA-based%20Allocation%20for%20GPU%20Architectures.pdf |access-date=17 April 2022}}


== See also ==
== See also ==
Read More