|
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命令の結果はひとつめの引数に格納される。 しかし現代のプロセッサでは、このテクニックによる得失のうち、失うほうが大きいかもしれない（後述）。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「XOR交換アルゴリズム」の詳細全文を読む スポンサード リンク
|