80

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

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

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

4

11 に答える 11

135

置換を行うことで、それがどのように機能するかを確認できます。

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 xor x == 0任意の x に対して、

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

そして、x xor 0 == x任意の x に対して、

y2 = x0
x2 = y0

そして交換完了です。

于 2008-10-30T06:45:44.777 に答える
98

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

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

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

于 2008-10-30T07:15:39.600 に答える
57

数値よりもグラフで考えるのが好きです。

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!
于 2009-02-09T16:51:38.630 に答える
36

これは、理解するのが少し簡単なはずです。

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

ここで、 ^が+ または -と考えられることを理解することで、XOR のトリックをもう少し簡単に理解できます。同じように：

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

、 それで：

x ^ y ^ ((x ^ y) ^ x) == x
于 2008-10-30T06:50:43.880 に答える
14

なぜそれが機能するのかというと、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 を使用するため、オーバーフローを心配する必要はありません。

楽しみたい場合は、これを「リンクされた Web」に拡張できます。

于 2009-02-09T15:25:31.177 に答える
14

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

tmp = x
x = y
y = tmp

これは、temp を必要とせずに 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 にはまだハイブリッド値があります。ハイブリッドから x のすべての痕跡を削除するために、y (現在は x の元の値) でもう一度 XOR します。これで y が残り、スワップは完了です。

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

ADD 3 A // add 3 to register A

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

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

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

于 2008-10-30T06:40:07.583 に答える
7

@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
于 2008-10-30T08:16:56.933 に答える
5

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

a' = a XOR b (1)
b' = a' XOR b (2)
a” = a' XOR b' (3)

これが機能する理由を理解するには、まず次のことに注意してください。

  1. XOR は、そのオペランドの 1 つだけが 1 で、もう 1 つがゼロの場合にのみ 1 を生成します。
  2. XOR は可換であるため、a XOR b = b XOR a;
  3. XOR は連想なので (a XOR b) XOR c = a XOR (b XOR c); と
  4. a XOR a = 0 (これは上記の1の定義から明らかなはずです)

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

b' = (a XOR b) XOR b
= a XOR (b XOR b) XOR は連想的だから
= XOR 0 上記の [4] のため
= XOR の定義による (上記1を参照)

これで、ステップ (3) に代入できます。

a” = (a XOR b) XOR a
= (b XOR a) XOR a XOR は交換可能であるため
= b XOR (a XOR a) XOR は結合可能であるため
= b XOR 0 上記の [4]
により = b の定義によるXOR (上記の1を参照)

詳細については、こちらをご覧ください: 必要かつ十分

于 2009-01-05T11:16:13.320 に答える