XOR交換アルゴリズム

標準的な交換アルゴリズムでは一時的な格納場所が必要となる。x と y の値を交換する場合、以下のようになる。

1. y の値を一時格納域にコピーする：temp ← y
2. y に x の値を代入する：y ← x
3. x に一時格納域の値を代入する：x ← temp

あるいは、x と y が整数ならば、以下のようなアルゴリズムで交換することができる。

1. x := x + y
2. y := x - y
3. x := x - y

ただし、このアルゴリズムをシステムで使用すると算術オーバーフロー例外を起こしてしまう可能性がある。XOR交換アルゴリズムを使うと、一時格納域も必要ないし、オーバーフローが発生することもない。

アルゴリズムは以下のようになる。

1. x := x XOR y
2. y := x XOR y
3. x := x XOR y

このアルゴリズムは一般にそのまま3つの機械語命令に対応する。例えばIBMのシステム/370のアセンブリ言語コードは以下のようになる。

XOR R1, R2

XOR R2, R1

XOR R1, R2

ここで R1 と R2 はレジスタであり、XOR命令の結果はひとつめの引数に格納される。

しかし現代のプロセッサでは、このテクニックによる得失のうち、失うほうが大きいかもしれない（後述）。

二項演算 XOR をビット列に対して行う場合、次のような特性がある（XOR を ${\displaystyle \otimes }$ で表す）。

• L1. 交換法則: ${\displaystyle A\otimes B=B\otimes A}$
• L2. 結合法則: ${\displaystyle (A\otimes B)\otimes C=A\otimes (B\otimes C)}$
• L3. 単位元の存在: ${\displaystyle Z=0}$ という値があり、任意の ${\displaystyle A}$ について ${\displaystyle A\otimes Z=A}$ が成り立つ。
• L4. 各要素は逆元を持つ: 任意の ${\displaystyle A}$ について、${\displaystyle A\otimes A^{-\!1}=Z}$ となる値 ${\displaystyle A^{-\!1}}$ が存在する。
  • L4a. 実際、各要素は自身の逆元である: ${\displaystyle A\otimes A=0}$

最初の4つの特性はアーベル群の定義である。最後の特性は XOR 特有のものである。

以下の表で、2つのレジスタ R1 と R2 があり、それぞれの初期値が A と B であるとする。この表では、XOR交換アルゴリズムをステップ単位に実施したとき、各ステップで上記特性のどれが適用されるかを示している。

PascalのプロシージャでXOR交換アルゴリズムを使ったふたつの整数の交換は次のようになる。

procedure XorSwap(var X, Y: integer);
begin
	if X <> Y then begin
		X := X xor Y;
		Y := X xor Y;
		X := X xor Y
	end
end

C言語コードによるXOR交換の実装は以下のようになる。

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

一時格納域に使える場所も限られている組み込み用途のアセンブリ言語でのプログラミングではこのアルゴリズムを使うのは珍しいことではない。また、この交換を使えばメモリアクセス回数も節約できる。いくつかの最適化されたコンパイラではこのようなコードを生成することができる。

しかし、レジスタ・リネーミングを行い、命令を並行して実行する（スーパースカラー参照）プロセッサでは、XOR交換は一時変数を使った交換よりもずっと遅くなってしまう。XOR交換では引数が必ず直前の演算結果に依存しているため、逐次的にしか実行できないのである。性能が最大の問題である場合は、XOR交換と一時変数を使った交換の両方を実際に実行してみて計測してみた方がよい。

また、多くの最近のプロセッサは XCHG (exchange、交換) 命令を持っていて、交換をひとつの命令で実行してしまう。

プログラミング言語によるプログラミングでは、仕様上可能なら、マクロやインライン関数で交換アルゴリズムの実装を隠すこともできる。コードを読みやすくするだけでなく、速さに問題がある場合に簡単に実装を置換できる。一方でそのように掩蔽すると、2個の引数が同じ場所を表す式であった場合に、両方とも0になってしまう、という意図しない結果になることがわかりづらくなり、また前述のように現代では有効性が限られた手法でもあることから、そのように手の込んだことをする意味は薄れている。