XOR交換アルゴリズム

XOR交換(エックスオアこうかん、XOR swap)は、コンピュータ・プログラミングのアルゴリズムの一種であり、排他的論理和(XOR)を使用して一時変数を使わずに同じデータ型のふたつの変数の(異なる)値を交換する操作である。このアルゴリズムはXORの対称差という性質を利用したものである。すなわち、任意のA, Bについて、(A XOR B) XOR B = A が成立することである。

アルゴリズム

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

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

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

x := x + y
y := x - y
x := x - y

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

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

x := x XOR y
y := x XOR y
x := x XOR y

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

XOR R1, R2

XOR R2, R1

XOR R1, R2

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

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

動作原理の証明

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

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

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

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

ステップ	操作	R1レジスタ	R2レジスタ	適用される項目
1	初期値	A	B	--
2	`R1 := R1 ^ R2`	A^B = B^A	B	L1
3	`R2 := R1 ^ R2`	B^A	(A^B)^B = A^(B^B) = A^0 = A	L2, L4, L3
4	`R1 := R1 ^ R2`	(B^A)^A = B^(A^A) = B^0 = B	A	L2, L3, L4

高水準言語での例

Pascal

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

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

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

実際の使用法

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

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

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

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

ハードウェアによる交換機能を持つマシン

たとえば、排他制御を実装する方法として、不可分操作としてふたつの値を交換する命令を利用する方法がある。これを可能にした最初のマシンのひとつは1970年の Datacraft (後の Harris) 6024 シリーズである。これが一時格納域を使わない値の交換をハードウェアで実装した最初である。この場合はメモリ上の値とレジスタ上の値をひとつの命令で、一回のリード/ライトサイクルだけで実行した。また、1964年のPDP-6も EXCH 命令でレジスタとメモリ(または別のレジスタ)の交換を実現している。また前述しているように x86系マイクロプロセッサも XCHG 命令を持っている。 MC68000の EXG 命令は、レジスタ同士の交換だけを行う。PDP-11にはない。

PDP-11がこのような命令を持っていたら、C言語が変数の値を交換する基本演算子を持つことになっていたかもしれない。^[要出典]

バリエーション

XOR交換アルゴリズムの考え方を他の可逆な二項関係に適用することもできる。XOR を加減算に置き換えると、ほぼ同じ機能が実現できる。

procedure AddSwap(var X, Y: integer); begin 	if X <> Y then begin 		X := X + Y; 		Y := X - Y; 		X := X - Y 	end end

ただし、この場合 X + Y の部分でオーバフローが発生しないことを保証する必要がある。従って、この方式はあまり使われない。