XOR交換アルゴリズム
たとえば、排他制御を実装する方法として、不可分操作としてふたつの値を交換する命令を利用する方法がある。 これを可能にした最初のマシンのひとつは1970年の Datacraft (後の Harris) 6024 シリーズである。 これが一時格納域を使わない値の交換をハードウェアで実装した最初である。 この場合はメモリ上の値とレジスタ上の値をひとつの命令で、一回のリード/ライトサイクルだけで実行した。 また、1964年のPDP-6も EXCH 命令でレジスタとメモリ(または別のレジスタ)の交換を実現している。 また前述しているように x86系マイクロプロセッサも XCHG 命令を持っている。 MC68000の EXG 命令は、レジスタ同士の交換だけを行う。PDP-11にはない。
PDP-11がこのような命令を持っていたら、C言語が変数の値を交換する基本演算子を持つことになっていたかもしれない。
標準的な交換アルゴリズムでは一時的な格納場所が必要となる。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命令の結果はひとつめの引数に格納される。
しかし現代のプロセッサでは、このテクニックによる得失のうち、失うほうが大きいかもしれない(後述)。
C言語コードによるXOR交換の実装は以下のようになる。