XORスワップアルゴリズム

コンピュータ プログラミングにおいて、排他的論理和スワップ( XOR スワップと略されることもあります) は、通常必要な一時変数を使用せずに、排他的論理和ビット演算を使用して 2 つの変数の値を交換するアルゴリズムです。

このアルゴリズムは、主に目新しいものであり、排他的論理和演算の特性を示す方法です。プログラムの最適化として議論されることもありますが、排他的論理和によるスワップが標準の明白な手法よりも有利になるケースはほとんどありません。

従来のスワッピングでは一時記憶変数を使用する必要があります。しかし、XORスワップアルゴリズムを使用すると、一時記憶は必要ありません。アルゴリズムは次のとおりです。^{[1] [2]}

X := Y XOR X ; // 値の XOR をとり、結果を X に格納しますY := X XOR Y ; // 値の XOR をとり、結果を Y に格納しますX := Y XOR X ; // 値の XOR をとり、結果を X に格納します     
     
     

XOR は交換可能な演算であるため、前述の 3 行のいずれにおいても、X XOR Y または Y XOR X のどちらも互換的に使用できます。一部のアーキテクチャでは、XOR 命令の最初のオペランドが演算結果が格納されるターゲット位置を指定するため、この互換可能性が妨げられることに注意してください。アルゴリズムは通常、次の表の 3 行の対応する疑似コードおよびアセンブリ命令によって表される 3 つのマシン コード命令に対応します。

上記の System/370 アセンブリ コード サンプルでは、​​R1 と R2 は別個のレジスタであり、各XR演算は最初の引数で指定されたレジスタに結果を出力します。x86 アセンブリを使用すると、値 X と Y はそれぞれレジスタ eax と ebx にあり、xor演算の結果は最初のレジスタに配置されます。RISC-V アセンブリでは、値 X と Y はレジスタ X10 と X11 にあり、xor演算の結果は最初のレジスタに配置されます (X86 と同じ)。

ただし、擬似コードまたは高水準言語バージョンまたは実装では、xとy が同じストレージ ロケーションを使用する場合、そのロケーションに格納された値は最初の XOR 命令によってゼロにされ、その後ゼロのままになるため、アルゴリズムは失敗します。つまり、その値は「それ自体とスワップ」されません。これは、xとy が同じ値を持つ場合とは異なります。問題は、xとy が同じストレージ ロケーションを使用する場合にだけ発生します。この場合、それらの値は既に等しい必要があります。つまり、xとyが同じストレージ ロケーションを使用する場合、次の行は次のようになります。

X := X排他的論理和Y    

x をゼロに設定し( x = yなので、X XOR Y はゼロ) 、y をゼロに設定します(同じストレージの場所を使用するため)。これにより、xとyの元の値が失われます。

長さのビット列に対する二項演算XORは、以下の特性を示す（ここでXORを表す）：^[a]${\displaystyle N}$${\displaystyle \oplus}$

• L1. 可換性:${\displaystyle A\oplus B=B\oplus A}$
• L2. 結合性:${\displaystyle (A\oplus B)\oplus C=A\oplus (B\oplus C)}$
• L3. 恒等式が存在する:任意の${\displaystyle A\oplus 0=A}$${\displaystyle A}$
• L4.各要素はそれ自身の逆要素です。つまり、各 に対して、です。${\displaystyle A}$${\displaystyle A\oplus A=0}$

下の表のように、それぞれ初期値AとB を持つ2 つの異なるレジスタがあるとしますR1。以下の操作を順番に実行し、上記のプロパティを使用して結果を減らします。 R2

XOR は 2 進加算として解釈でき、ビットのペアは2 つの要素を持つ体上の 2 次元ベクトル空間のベクトルとして解釈できるため、アルゴリズムの手順は 2 つの要素を持つ体上の 2×2 行列による乗算として解釈できます。簡単にするために、最初はxとy がそれぞれビット ベクトルではなく単一のビットであると 仮定します。

たとえば、次の手順:

X := X排他的論理和Y    

これには暗黙的に次の意味も含まれています:

Y := Y  

行列は次のよう になる。${\displaystyle \left({\begin{smallmatrix}1&1\\0&1\end{smallmatrix}}\right)}$

${\displaystyle {\begin{pmatrix}1&1\\0&1\end{pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}={\begin{pmatrix}x+y\\y\end{pmatrix}}.}$

操作のシーケンスは次のように表現されます。

${\displaystyle {\begin{pmatrix}1&1\\0&1\end{pmatrix}}{\begin{pmatrix}1&0\\1&1\end{pmatrix}}{\begin{pmatrix}1&1\\0&1\end{pmatrix}}={\begin{pmatrix}0&1\\1&0\end{pmatrix}}}$

(バイナリ値を扱うため、) は、 2 つの行 (または列) を切り替える基本行列を、 1 つの要素を他の要素に追加する トランスベクション(せん断)の観点から表現します。${\displaystyle 1+1=0}$

XとYが単一のビットではなく長さnのビットベクトルである場合に一般化するには、これらの2×2行列を2 n ×2 n ブロック行列に置き換えます。${\displaystyle \left({\begin{smallmatrix}I_{n}&I_{n}\\0&I_{n}\end{smallmatrix}}\right).}$

これらの行列は、変数(保存場所を持つ)ではなく値に対して動作するため、この解釈により、保存場所の問題と、両方の変数が同じ保存場所を共有するという問題が抽象化されます。

XOR スワップ アルゴリズムを実装する C関数:

void XorSwap ( int * x , int * y ) { if ( x == y ) return ; * x ^= * y ; * y ^= * x ; * x ^= * y ; }     

      
    
    
    

コードは、まずアドレスが異なっているかどうかをチェックし、等しい場合はガード句を使用して関数を早期に終了します。このチェックを行わないと、アドレスが等しい場合、アルゴリズムはトリプルに折りたたまれ、*x ^= *x結果はゼロになります。

XOR スワップ アルゴリズムは、マクロを使用して定義することもできます。

#define XORSWAP_UNSAFE(a, b) \ 
  ((a) ^= (b), (b) ^= (a), \ 
   (a) ^= (b)) /* a と b が同じオブジェクトの場合には動作しません。
                  その場合にはオブジェクトにゼロ \ (0) を割り当てます */ 
#define XORSWAP(a, b) \ 
  ((&(a) == &(b)) ? (a) /* 異なるアドレスをチェックします */                     \ 
                  : XORSWAP_UNSAFE(a, b))

現代のCPUアーキテクチャでは、XOR手法は一時変数を使用してスワップを行うよりも遅くなることがあります。少なくともAMDとIntelの最近のx86 CPUでは、レジスタ間の移動で定期的に発生するレイテンシはゼロです。（これはMOV除去と呼ばれます。）使用可能なアーキテクチャレジスタがない場合でも、命令はXCHG少なくとも3つのXORを合わせた速度と同じぐらい速くなります。もう1つの理由は、現代のCPUが命令パイプラインを介して命令を並列に実行しようとしていることです。XOR手法では、各操作への​​入力は前の操作の結果に依存するため、厳密に順番に実行する必要があり、命令レベルの並列性の利点が打ち消されます。^[3]

XOR スワップは、エイリアシングによって実際には複雑になります。ある場所の内容をそれ自体と XOR スワップしようとすると、その場所はゼロにされ、その値は失われます。したがって、エイリアシングが可能な場合は、高級言語で XOR スワップを盲目的に使用しないでください。この問題は、この手法がアセンブリで 2 つのレジスタの内容をスワップするために使用される場合は当てはまりません。

Jensen の Deviceの場合と同様に、call by nameでも同様の問題が発生します。一時変数を介してとを交換すると、引数が関連しているために誤った結果が生成されます。を介して交換すると、2 番目のステートメントのの値が変わり、3 番目のステートメントのの値が誤っています。 iA[i]temp = i; i = A[i]; A[i] = tempiiA[i]

XORスワップアルゴリズムの基本原理は、上記の基準L1からL4を満たすあらゆる操作に適用できます。XORを加算と減算に置き換えると、わずかに異なるがほぼ同等のさまざまな定式が得られます。例: ^[4]

void AddSwap ( unsigned int * x , unsigned int * y ) { * x = * x + * y ; * y = * x - * y ; * x = * x - * y ; }        

        
        
        

XOR スワップとは異なり、このバリエーションでは、基礎となるプロセッサまたはプログラミング言語がモジュラー演算やbignumsなどの方法を使用して、の計算で整数オーバーフローX + Yによるエラーが発生しないことを保証する必要があります。そのため、実際には XOR スワップよりもまれにしか見られません。

しかし、C プログラミング言語での上記の実装はAddSwap、整数オーバーフローの場合でも常に機能します。これは、C 標準によれば、符号なし整数の加算と減算はモジュラ演算の規則に従うためです。つまり、 は巡回群 で実行されます。ここで、は のビット数です。実際、アルゴリズムの正しさは、式および が任意のアーベル群で成り立つという事実から得られます。これは、XOR スワップ アルゴリズムの証明を一般化したものです。XOR は、アーベル群(のs個のコピーの直和) での加算と減算の両方です。 ${\displaystyle \mathbb {Z} /2^{s}\mathbb {Z} }$${\displaystyle s}$unsigned int${\displaystyle (x+y)-y=x}$${\displaystyle (x+y)-((x+y)-y)=y}$${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{s}}$${\displaystyle \mathbb {Z} /2\mathbb {Z} }$

signed intこれは、 型 ( のデフォルト)を扱う場合には当てはまりませんint。符号付き整数オーバーフローは C では未定義の動作であるため、標準ではモジュラー演算が保証されず、誤った結果が生じる可能性があります。

の演算シーケンスは、行列AddSwap乗算によって次のように表現できます。

${\displaystyle {\begin{pmatrix}1&-1\\0&1\end{pmatrix}}{\begin{pmatrix}1&0\\1&-1\end{pmatrix}}{\begin{pmatrix}1&1\\0&1\end{pmatrix}}={\begin{pmatrix}0&1\\1&0\end{pmatrix}}}$

専用のスワップ命令がないアーキテクチャでは、余分な一時レジスタを回避するため、XORスワップアルゴリズムが最適なレジスタ割り当てに必要となる。これは、レジスタ割り当てに静的単一割り当て形式を使用するコンパイラにとって特に重要である。これらのコンパイラは、空きレジスタがない場合に2つのレジスタを交換する必要があるプログラムを生成することがある。XORスワップアルゴリズムは、余分なレジスタを予約したり、レジスタをメインメモリに流したりする必要性を回避する。^[5]加算/減算バリアントも同じ目的で使用できる。^[6]

このレジスタ割り当て方法は、GPUシェーダコンパイラに特に関係しています。現代のGPUアーキテクチャでは、メモリ帯域幅が限られておりメモリレイテンシが高いため、変数のスピルにはコストがかかりますが、レジスタの使用を制限すると、レジスタファイルの動的パーティション分割によりパフォーマンスが向上します。そのため、一部のGPUコンパイラではXORスワップアルゴリズムが必要です。^[7]

• 対称差
• XORリンクリスト
• Feistel 暗号(XOR スワップ アルゴリズムは Feistel 暗号の退化した形式です)