XOR 변수 스와핑은 어떻게 작동합니까?

XOR 변수 스와핑은 어떻게 작동합니까?

---

누군가 임시 변수가없는 두 변수의 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 xor x == 0어떤 X 용,

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

그리고 x xor 0 == x모든 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은 반전 작업이며 두 번 수행하는 것은 미러입니다.

     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!

---

조금 더 쉽게 구할 수있는 방법이 있습니다.

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

---

작동하는 이유는 XOR이 정보를 잃지 않기 때문입니다. 오버플로를 무시할 수 있다면 일반적인 덧셈과 뺄셈으로 똑같은 일을 할 수 있습니다. 예를 들어, 변수 쌍 A, B에 원래 값 1,2가 포함 된 경우 다음과 같이 바꿀 수 있습니다.

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

BTW 단일 "포인터"에서 양방향 연결 목록을 인코딩하는 오래된 트릭이 있습니다. 주소 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를 뺍니다. 거꾸로도 잘 작동합니다. 목록을 따라 실행하려면 두 개의 연속 블록에 대한 포인터를 유지해야합니다. 물론 더하기 / 빼기 대신 XOR을 사용하므로 오버플로에 대해 걱정할 필요가 없습니다.

재미를 원한다면 이것을 "링크 된 웹"으로 확장 할 수 있습니다.

---

대부분의 사람들은 다음과 같이 임시 변수를 사용하여 두 개의 변수 x와 y를 교환합니다.

tmp = x
x = y
y = tmp

임시를 사용하지 않고 두 값을 바꾸는 깔끔한 프로그래밍 트릭은 다음과 같습니다.

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

XOR을 사용하여 두 변수 교체에 대한 자세한 내용

1 행에서 x와 y를 결합하여 (XOR 사용)이 "하이브리드"를 얻고 x에 다시 저장합니다. XOR은 XOR을 다시 수행하여 제거 할 수 있으므로 정보를 저장하는 좋은 방법입니다.

2 행. y로 하이브리드를 XOR하면 모든 y 정보가 취소되고 x 만 남습니다. 이 결과를 y에 다시 저장하므로 이제 서로 바뀝니다.

마지막 줄에서 x에는 여전히 하이브리드 값이 있습니다. 하이브리드에서 x의 모든 흔적을 제거하기 위해 y (이제 x의 원래 값으로)로 다시 XOR합니다. 이것은 우리에게 y를 남겨두고 스왑이 완료되었습니다!

---

The computer actually has an implicit “temp” variable that stores intermediate results before writing them back to a register. For example, if you add 3 to a register (in machine-language pseudocode):

ADD 3 A // add 3 to register A

The ALU (Arithmetic Logic Unit) is actually what executes the instruction 3+A. It takes the inputs (3,A) and creates a result (3 + A), which the CPU then stores back into A’s original register. So, we used the ALU as temporary scratch space before we had the final answer.

We take the ALU’s implicit temporary data for granted, but it’s always there. In a similar way, the ALU can return the intermediate result of the XOR in the case of x = x xor y, at which point the CPU stores it into x’s original register.

Because we aren’t used to thinking about the poor, neglected ALU, the XOR swap seems magical because it doesn’t have an explicit temporary variable. Some machines have a 1-step exchange XCHG instruction to swap two registers.

---

@VonC has it right, it's a neat mathematical trick. Imagine 4 bit words and see if this helps.

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

---

Basically there are 3 steps in the XOR approach:

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

To understand why this works first note that:

1. XOR will produce a 1 only if exactly one of it’s operands is 1, and the other is zero;
2. XOR is commutative so a XOR b = b XOR a;
3. XOR is associative so (a XOR b) XOR c = a XOR (b XOR c); and
4. a XOR a = 0 (this should be obvious from the definition in 1 above)

After Step (1), the binary representation of a will have 1-bits only in the bit positions where a and b have opposing bits. That is either (ak=1, bk=0) or (ak=0, bk=1). Now when we do the substitution in Step (2) we get:

b’ = (a XOR b) XOR b
= a XOR (b XOR b) because XOR is associative
= a XOR 0 because of [4] above
= a due to definition of XOR (see 1 above)

Now we can substitute into Step (3):

a” = (a XOR b) XOR a
= (b XOR a) XOR a because XOR is commutative
= b XOR (a XOR a) because XOR is associative
= b XOR 0 because of [4] above
= b due to definition of XOR (see 1 above)

More detailed information here: Necessary and Sufficient

---

As a side note I reinvented this wheel independently several years ago in the form of swapping integers by doing:

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

(This is mentioned above in a difficult to read way),

The exact same reasoning applies to xor swaps: a ^ b ^ b = a and a ^ b ^ a = a. Since xor is commutative, x ^ x = 0 and x ^ 0 = x, this is quite easy to see since

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

and

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

Hope this helps. This explanation has already been given... but not very clearly imo.

참고URL : https://stackoverflow.com/questions/249423/how-does-xor-variable-swapping-work