XOR交換アルゴリズム 実際の使用法

ウィキペディア

XOR交換アルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/01/06 13:42 UTC 版)

実際の使用法

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

しかし、レジスタ・リネーミングを行い、命令を並行して実行する（スーパースカラー参照）プロセッサでは、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 の部分でオーバフローが発生しないことを保証する必要がある。従って、この方式はあまり使われない。