XOR交換アルゴリズム

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

アルゴリズム[編集]

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

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

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

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

ただし、このアルゴリズムをシステムで使用すると算術オーバーフロー例外を起こしてしまう可能性がある。 また、xy が実際には同じ格納域を指している場合、この演算をするとゼロになってしまう。 XOR交換アルゴリズムを使うと、一時格納域も必要ないし、オーバーフローが発生することもない。 アルゴリズムは以下のようになる。

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

(しかし、xy が同じ格納域だった場合に値がゼロになってしまう問題は残っている。) このアルゴリズムは一般にそのまま3つの機械語命令に対応する。 例えばIBMのシステム/370のアセンブリ言語コードは以下のようになる。

XOR R1, R2
XOR R2, R1
XOR R1, R2

ここで R1 と R2 はレジスタであり、XOR命令の結果はひとつめの引数に格納される。 このアルゴリズムはアセンブラでのプログラミングでは効果的と言える。 一時的に他のレジスタを使う必要がない。レジスタは機械語のプログラミングでの限られた資源である。 また、メモリを一時格納域として使うとメモリアクセスが2回発生し(ストアとロード)、時間がかかってしまう。

動作原理の証明[編集]

二項演算 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 \otimes A^{-\!1} = Z となる値 A^{-\!1} が存在する。
    • L4a. 実際、各要素は自身の逆元である: A \otimes A = 0

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

以下の表で、2つのレジスタ R1R2 があり、それぞれの初期値が AB であるとする。この表では、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、交換) 命令を持っていて、交換をひとつの命令で実行してしまう。

言語仕様上可能なら、マクロインライン関数で交換アルゴリズムの実装を隠すこともできる。 コードを読みやすくするだけでなく、速さに問題がある場合に簡単に実装を置換できる。

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

たとえば、排他制御を実装する方法として、不可分操作としてふたつの値を交換する命令を利用する方法がある。 これを可能にした最初のマシンのひとつは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 の部分でオーバフローが発生しないことを保証する必要がある。従って、この方式はあまり使われない。

関連項目[編集]