XOR 変数のスワップはどのように機能しますか?

https://stackoverflow.com/questions/249423

05-07-2019
|

質問

誰かが一時変数を持たない 2 つの変数の XOR スワッピングがどのように機能するかを説明してもらえますか?

void xorSwap (int *x, int *y)
{
    if (x != y) {
        *x ^= *y;
        *y ^= *x;
        *x ^= *y;
    }
}

それが何をするのかは理解していますが、誰かがそれがどのように機能するかのロジックを説明してもらえますか?

解決

置換を行うことで、どのように機能するかを見ることができます：

x1 = x0 xor y0
y2 = x1 xor y0
x2 = x1 xor y2

置換、

x1 = x0 xor y0
y2 = (x0 xor y0) xor y0
x2 = (x0 xor y0) xor ((x0 xor y0) xor y0)

xorは完全に結合的で可換であるため：

y2 = x0 xor (y0 xor y0)
x2 = (x0 xor x0) xor (y0 xor y0) xor y0

xについて x xor x == 0 であるため、

y2 = x0 xor 0
x2 = 0 xor 0 xor y0

そして、任意のxに対して x xor 0 == x であるため、

y2 = x0
x2 = y0

そして、スワップが完了しました。

他のヒント

他の人がそれを説明したので、今ではなぜそれが良いアイデアだったのか説明したいのですが、今はそうではありません。

単純なシングルサイクルまたはマルチサイクルCPUを使用していた当時、高価なメモリの逆参照やスタックへのレジスタの流出を避けるために、このトリックを使用する方が安価でした。ただし、今では代わりに大規模なパイプラインを備えたCPUがあります。 P4のパイプラインは、パイプラインに20から31（またはそこら）のステージがあり、レジスタへの読み取りと書き込みの依存関係が原因で全体が停止する可能性がありました。 xorスワップには、AとBの間に非常に重い依存関係がありますが、実際にはまったく問題ではありませんが、実際にはパイプラインが停止します。パイプラインが停止するとコードパスが遅くなり、このスワップが内部ループにある場合、非常にゆっくりと移動します。

一般的に、コンパイラーは、一時変数を使用してスワップを実行するときに実際に何をしたいかを把握し、それを単一のXCHG命令にコンパイルできます。 xorスワップを使用すると、コンパイラーが意図を推測するのがはるかに難しくなり、そのため、それを正しく最適化する可能性がはるかに低くなります。コードのメンテナンスなどは言うまでもありません

数値ではなくグラフィカルに考えるのが好きです。

x = 11およびy = 5から始めましょうバイナリ（仮想4ビットマシンを使用します）では、xとy

を使用します

       x: |1|0|1|1|   -> 8 + 2 + 1
       y: |0|1|0|1|   -> 4 + 1

今、XORは反転演算であり、2回実行することはミラーです：

     x^y: |1|1|1|0|
 (x^y)^y: |1|0|1|1|   <- ooh!  Check it out - x came back
 (x^y)^x: |0|1|0|1|   <- ooh!  y came back too!

これは、もう少し簡単に理解できるはずの1つです。

int x = 10, y = 7;

y = x + y; //x = 10, y = 17
x = y - x; //x = 7, y = 17
y = y - x; //x = 7, y = 10

今、 ^ は + または -。次のように：

x + y - ((x + y) - x) == x

、そのため：

x ^ y ^ ((x ^ y) ^ x) == x

XORが機能する理由は、XORが情報を失わないためです。オーバーフローを無視できる場合は、通常の加算と減算で同じことを行うことができます。たとえば、変数ペアA、Bに元々値1,2が含まれている場合、次のようにそれらを交換できます。

 // A,B  = 1,2
A = A+B // 3,2
B = A-B // 3,1
A = A-B // 2,1

ところで、単一の「ポインタ」で双方向リンクリストをエンコードするための古いトリックがあります。アドレスA、B、Cにメモリブロックのリストがあるとします。各ブロックの最初の単語は、それぞれ

です。

 // first word of each block is sum of addresses of prior and next block
 0 + &B   // first word of block A
&A + &C   // first word of block B
&B + 0    // first word of block C

ブロックAにアクセスできる場合、Bのアドレスが提供されます。Cに到達するには、「ポインター」を取得します。 BでAを引くなど。逆方向にも機能します。リストに沿って実行するには、2つの連続したブロックへのポインターを保持する必要があります。もちろん、加算/減算の代わりにXORを使用するので、オーバーフローについて心配する必要はありません。

これを「リンクされたウェブ」に拡張できます。楽しみたいなら。

ほとんどの人は、次のように一時変数を使用して 2 つの変数 x と y を交換します。

tmp = x
x = y
y = tmp

これは、一時を必要とせずに 2 つの値を交換するための巧妙なプログラミングのトリックです。

x = x xor y
y = x xor y
x = x xor y

詳細については、 XOR を使用して 2 つの変数を交換する

1 行目では、x と y を (XOR を使用して) 組み合わせてこの「ハイブリッド」を取得し、それを x に格納します。XOR は、再度 XOR を実行することで情報を削除できるため、情報を保存する優れた方法です。

2号線にあります。ハイブリッドを y と XOR します。これにより、すべての y 情報がキャンセルされ、x だけが残ります。この結果を y に保存し直すと、それらは交換されます。

最後の行では、x は依然としてハイブリッド値を持っています。y と (今度は x の元の値を使用して) XOR をもう一度実行して、ハイブリッドから x のすべての痕跡を削除します。これで y が残り、交換が完了しました。

コンピューターには実際には、レジスタに書き戻す前に中間結果を保存する暗黙の「temp」変数があります。たとえば、(機械語の擬似コードで) レジスタに 3 を追加すると、次のようになります。

ADD 3 A // add 3 to register A

実際に命令 3+A を実行するのは ALU (算術論理演算装置) です。入力 (3,A) を受け取り、結果 (3 + A) を作成し、CPU がその結果を A の元のレジスタに格納します。そこで、最終的な答えが得られる前に、ALU を一時的なスクラッチスペースとして使用しました。

私たちは ALU の暗黙的な一時データを当然のことと考えていますが、それは常に存在します。同様に、ALU は、x = x xor y の場合に XOR の中間結果を返すことができ、その時点で CPU はそれを x の元のレジスタに保存します。

私たちは貧弱で無視されている ALU について考えることに慣れていないため、XOR スワップには明示的な一時変数がないため、魔法のように見えます。一部のマシンには、2 つのレジスタを交換する 1 ステップ交換 XCHG 命令があります。

@VonC が正しく、それはきちんとした数学的なトリックです。 4ビットの単語を想像して、これが役立つかどうかを確認してください。

word1 ^= word2;
word2 ^= word1;
word1 ^= word2;


word1    word2
0101     1111
after 1st xor
1010     1111
after 2nd xor
1010     0101
after 3rd xor
1111     0101

基本的に、XORアプローチには3つのステップがあります：

a＆＃8217; = a XOR b（1）
b＆＃8217; = a＆＃8217; XOR b（2）
a＆＃8221; = a＆＃8217; XOR b＆＃8217; （3）

なぜを理解するために、これが最初に機能することに注意してください：

XORは、オペランドの1つだけが1で、もう1つがゼロの場合にのみ1を生成します。
XORは可換なので、a XOR b = b XOR a;
XORは連想なので、（a XOR b）XOR c = a XOR（b XOR c）;および
a XOR a = 0（これは 1の定義から明らかです。 a>上記）

ステップ（1）の後、aのバイナリ表現は、aとbが反対のビットを持つビット位置にのみ1ビットを持ちます。それは（ak = 1、bk = 0）または（ak = 0、bk = 1）です。ステップ（2）で置換を行うと、次のようになります。

b＆＃8217; =（a XOR b）XOR b
    = a XOR（b XOR b）XORは結合的であるため
   =上記の[4]のためXOR 0
   = XORの定義による（上記 1 を参照）

これで、ステップ（3）に置き換えることができます：

a＆＃8221; =（a XOR b）XOR a
    =（b XOR a）XORは可換であるため、XOR a
    = b XOR（a XOR a）XORは結合性であるため
    = b XOR 0 [4]上記のため
    = bはXORの定義による（上記 1 を参照）

詳細情報はこちら：必要かつ十分な

補足として、数年前にこのホイールを独自に再発明しました。

a = a + b
b = a - b ( = a + b - b once expanded)
a = a - b ( = a + b - a once expanded).

（これは上記で読みにくい方法で言及されています）、

まったく同じ推論がxorスワップに適用されます：a ^ b ^ b = aおよびa ^ b ^ a = a。 xorは可換であるため、x ^ x = 0およびx ^ 0 = xであるため、これは非常に簡単にわかります。

= a ^ b ^ b
= a ^ 0
= a

and

= a ^ b ^ a 
= a ^ a ^ b 
= 0 ^ b 
= b

これが役立つことを願っています。この説明はすでに与えられています...しかし、あまり明確ではありません。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow