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

누군가 임시 변수가없는 두 변수의 XOR 스왑이 어떻게 작동하는지 설명 할 수 있습니까?

void xorSwap (int *x, int *y)
{
if (x != y) {
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
}
나는 그것이 무엇을하는지 이해하지만 누군가가 그것이 어떻게 작동하는지에 대한 논리를 안내해 줄 수 있습니까?

언어에 구애받지 않는
비트 조작
xor
공유 이 질문을 개선 따르다
생성 30 oct. 082008-10-30 07:24:28 ss

풀다
355,00060골드 배지 60 개443443 은색 배지570브론즈 배지 570 개
생성 30 a.

mmcdole
84.3k60골드 배지 60 개178은색 배지 178 개221청동 휘장 221 개
6
xor 변수 스왑이 비 순차적 실행 코어를 짜증나게한다고 생각합니다. 각 후속 xor에는 쓰기 후 읽기 종속성이 있으며 응답이 완료 될 때까지 기다려야합니다. x86의 경우 평소처럼 코딩하는 것이 좋습니다. 컴파일러는 괜찮은 것을 내 보냅니다. – Calyth 2009 년 1 월 9 일 23:41
의견을 추가하다
10 개의 답변

130

대체를 수행하여 작동 방식을 볼 수 있습니다.

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
그리고 스왑이 완료되었습니다.

공유 이 답변을 개선 따르다
생성 30 oct. 082008-10-30 06:45:22 s.

그렉 휴길
793k168골드 배지 168 개1084 년1084 실버 배지1223 년1223 브론즈 배지
11 년 후에이 댓글을 볼 수 있을지 모르겠지만 감사합니다. – Cantaff0rd Jan 28 '19 14:39
12 년 후 : 스트링 반전에서와 같이 스트링과 어떻게 작동합니까? ASCII 값이 아니라 문자열의 다양한 부분을 포함하는 메모리 주소의 이진 표현을 사용하기 때문입니까? – bluppfisk '19 년 9 월 2 일 21:55
나는 거의 변경 충동에 저항 할 수 y2에를 y1. 그것은 당신이 저를 유발 x0하고 x1그러나 사용 y0하고 y2. :-] – Frerich Raabe '19 -12-13 12:52
의견을 추가하다

95

다른 사람들이 설명해 주 었으니 이제는 왜 그것이 좋은 생각인지 설명하고 싶지만 지금은 그렇지 않습니다.

단순 단일 사이클 또는 다중 사이클 CPU를 사용하던 시절에는 값 비싼 메모리 역 참조 또는 스택에 레지스터 유출을 방지하기 위해이 트릭을 사용하는 것이 더 저렴했습니다. 그러나 이제는 대신 대규모 파이프 라인이있는 CPU가 있습니다. P4의 파이프 라인은 파이프 라인에 20 개에서 31 개 (또는 그 정도)의 단계를 포함하며 레지스터에 대한 읽기와 쓰기 간의 종속성으로 인해 전체가 중단 될 수 있습니다. xor 스왑에는 A와 B 사이에 매우 무거운 종속성이 있지만 실제로는 중요하지 않지만 실제로 파이프 라인을 지연시킵니다. 지연된 파이프 라인은 느린 코드 경로를 유발하며,이 스왑이 내부 루프에있는 경우 매우 느리게 이동하게됩니다.

일반적으로 컴파일러는 임시 변수로 스왑을 수행 할 때 실제로 수행 할 작업을 파악하고이를 단일 XCHG 명령어로 컴파일 할 수 있습니다. xor 스왑을 사용하면 컴파일러가 의도를 추측하기가 훨씬 더 어려워 지므로 올바르게 최적화 할 가능성이 훨씬 적습니다. 코드 유지 관리 등은 말할 것도 없습니다.

공유 이 답변을 개선 따르다
생성 10 apr. 132013-04-10 1:00:01 s.
생성 30 oct. 082008-10-30 07:15:28 s.

패트릭
77.1k10골드 배지 10 개4747 개의 은색 배지6161 개의 브론즈 배지
네-모든 메모리 절약 트릭과 마찬가지로 이것은 요즘 저렴한 메모리에서 그렇게 유용하지 않습니다. – Bruce Alderman 2008 년 11 월 21 일 21:43
1
그러나 동일한 토큰으로 임베디드 시스템 CPU는 여전히 많은 이점을 얻습니다. – Paul Nathan 2009 년 2 월 9 일 15:38
@Paul, 그것은 당신의 도구 체인에 달려 있습니다. 임베디드 컴파일러가 이미 해당 최적화를 수행하고 있지 않은지 확인하기 위해 먼저 테스트하겠습니다. – Patrick 2009 년 2 월 21 일 07:09
2
(크기 관점에서 볼 때 아키텍처에 따라 XOR 3 개가 XCHG 1 개보다 클 가능성이 높습니다. xor 트릭을 사용하지 않으면 더 많은 공간을 절약 할 수 있습니다.) – Patrick Feb 21 '09 at 7:11
의견을 추가하다

53

숫자보다는 그래픽으로 생각하고 싶습니다.

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!
공유 이 답변을 개선 따르다
생성 09 feb. 092009-02-09 16:51:28 s.

주각
44.8k99 개의 골드 배지75은색 배지 75 개115청동 휘장 115 개
매우 명확한. 모든 비트에서 각 XOR 작업을 수행하면 무슨 일이 일어나고 있는지 훨씬 쉽게 이해할 수 있습니다. & 및 |와는 달리 XOR을 이해하기가 더 어렵다고 생각합니다. 머리로하기가 훨씬 더 어렵습니다. XOR 산술은 혼란을 야기합니다. 문제를 시각화하는 것을 두려워하지 마십시오. 컴파일러는 당신이 아니라 수학을 수행합니다. – Martyn Shutt '15 년 1 월 20 일 11:39
의견을 추가하다

35

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

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
공유 이 답변을 개선 따르다
생성 30 a.

매트 J
37.7k77 개의 금 휘장4444 개의 은색 배지5656 개의 브론즈 배지
@Matt J, 빼기 예제에 감사드립니다. 그것은 내가 그것을 찾는 데 도움이되었습니다. – mmcdole 2008 년 10 월 30 일 14:17
삼
많은 수의 오버플로로 인해 더하기 또는 빼기 방법을 사용할 수 없다는 점을 강조 할 가치가 있습니다. – MarkJ 2009 년 2 월 11 일 21:16
그럴까요? 내가 해결 한 작은 예에서는 문제가 없어도 문제가 해결되었습니다 (언더 플로 또는 오버플로의 결과가 (결과 % 2 ^ n)라고 가정). 나는 그것을 테스트하기 위해 무언가를 코딩 할 수 있습니다. – Matt J 2009 년 2 월 12 일 2:32
ADD 및 SUB 명령의 가장 간결한 하드웨어 구현을 가정하면 오버플로 또는 언더 플로가있는 경우에도 제대로 작동한다고 생각합니다. 방금 테스트했습니다. 내가 뭔가를 놓치고 있습니까? – Matt J 2009 년 2 월 12 일 2:59
오버플로 및 언더 플로에 대한 예외가 없다면 확실히 작동 할 것이라고 생각합니다. – MarkJ 2009 년 2 월 13 일 21:01
의견을 추가하다

13

대부분의 사람들은 다음과 같이 임시 변수를 사용하여 두 개의 변수 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를 남겨두고 스왑이 완료되었습니다!

컴퓨터에는 실제로 중간 결과를 레지스터에 다시 쓰기 전에 저장하는 암시 적 "temp"변수가 있습니다. 예를 들어, 레지스터에 3을 추가하는 경우 (기계 언어 의사 코드) :

ADD 3 A // add 3 to register A
ALU (산술 논리 장치)는 실제로 명령 3 + A를 실행하는 것입니다. 입력 (3, A)을 받아 결과 (3 + A)를 생성 한 다음 CPU가 A의 원래 레지스터에 다시 저장합니다. 따라서 최종 답변을 받기 전에 ALU를 임시 스크래치 공간으로 사용했습니다.

우리는 ALU의 암시 적 임시 데이터를 당연하게 생각하지만 항상 거기에 있습니다. 비슷한 방식으로 ALU는 x = x xor y의 경우 XOR의 중간 결과를 반환 할 수 있으며, 이때 CPU는 x의 원래 레지스터에 저장합니다.

우리는 가난하고 무시 된 ALU에 대해 생각하는 데 익숙하지 않기 때문에 XOR 스왑은 명시적인 임시 변수가 없기 때문에 마법처럼 보입니다. 일부 기계에는 두 개의 레지스터를 교환하는 1 단계 교환 XCHG 명령어가 있습니다.

공유 이 답변을 개선 따르다
생성 30 oct. 082008-10-30 06:46:14 ak
생성 30 oct. 082008-10-30 06:40:14 s.

VonC
998k414414 골드 배지34563456 실버 배지40484048 브론즈 배지
4
나는 그것이 어떻게 작동하는지 묻고 있음을 이해합니다. 배타적 또는 값을 사용하면 임시 변수없이 어떻게 바꿀 수 있습니까? – mmcdole 2008 년 10 월 30 일 6:41
이것이 가장 명확하고 가장 상세한 답변이기 때문에 찬성했지만, 임시 변수를 사용한 스왑이 훨씬 더 읽기 쉽고 코드에서 더 많은 가치를 전달한다는 점에 주목하고 싶습니다 – 눈꺼풀이 없음 2008 년 10 월 30 일 6:59
1
원래 답변 (설명 포함)이 마음에 들었지만 ALU에 대한 약간의 잘못된 안내 인 것 같습니다. 여러분이 언급 한 단일 사이클 (파이프 라인이 아닌) 프로세서에서도 1 명령어에서 "x = (op 관련 x)"를 수행하는 기능은 레지스터 파일에 입력 및 출력 포트 가 있다는 사실과 더 관련이 있습니다. – Matt J 2008 년 10 월 30 일 7:38
의견을 추가하다

13

작동하는 이유는 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을 사용하므로 오버플로에 대해 걱정할 필요가 없습니다.

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

공유 이 답변을 개선 따르다
생성 03 mar.
생성 09 feb. 092009-02-09 15:25:28 s.

마이크 던 라비
38.2 천12골드 배지 12 개8484 개의 은색 배지125125 개의 브론즈 배지
단일 포인터 트릭은 꽤 굉장합니다. 이것에 대해 몰랐습니다! 감사! – Gab Royer 2009 년 9 월 27 일 21:20
1
@Gab : 천만에요, 당신의 영어 실력은 제 프랑스어보다 훨씬 낫습니다! – Mike Dunlavey 2009 년 9 월 28 일 0:22
1
+/- 접근 방식 +1 ( int오버플로가 UB 임에도 불구하고 ) – chux-Monica 복원 '15 년 3 월 26 일 15:36
의견을 추가하다

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
공유 이 답변을 개선 따르다
생성 23 may.

커뮤니티 ♦
11은색 배지 1 개
생성 30 a.

케니
18.2 천77 개의 금 휘장4646 개의 은색 배지8282 개의 브론즈 배지
의견을 추가하다

5

기본적으로 XOR 접근 방식에는 3 단계가 있습니다.

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

이것이 작동 하는 이유 를 이해하려면 먼저 다음 사항에 유의하십시오.

XOR은 피연산자 중 정확히 하나가 1이고 다른 하나가 0 인 경우에만 1을 생성합니다.
XOR은 교환 적이므로 a XOR b = b XOR a;
XOR은 연관성이 있으므로 (a XOR b) XOR c = a XOR (b XOR c); 과
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이 연관성이기 때문
= a XOR 0 (위의 [4] 때문에 XOR 0 = XOR의
정의로 인한 a ( 위의 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 참조)

여기에 더 자세한 정보 : 필요 및 충분

공유 이 답변을 개선 따르다
생성 05 jan. 092009-01-05 11:16:49 s.
의견을 추가하다

삼

참고로 몇 년 전에 정수를 바꾸는 형태로이 바퀴를 독립적으로 재발 명했습니다.

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
과

= a ^ b ^ a
= a ^ a ^ b
= 0 ^ b
= b
도움이 되었기를 바랍니다. 이 설명은 이미 주어졌지만 명확하지는 않습니다.

공유 이 답변을 개선 따르다
생성 09 feb. 092009-02-09 16:32:28 s.

제리코
2,9281골드 배지 1 개1919 개의 은색 배지28브론즈 배지 28 개
의견을 추가하다

삼

답을 더 완벽하게 만들기 위해 수학적 설명을 추가하고 싶습니다. 에서 그룹 이론 , XOR은입니다 아벨 군 또한 교환 법칙이 성립 그룹이라고는. 이는 Closure, Associativity, Identity 요소, Inverse 요소, Commutativity의 다섯 가지 요구 사항을 충족 함을 의미합니다.

XOR 스왑 공식 :

a = a XOR b
b = a XOR b
a = a XOR b
공식을 확장하고 a, b를 이전 공식으로 대체합니다.

a = a XOR b
b = a XOR b = (a XOR b) XOR b
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b
교환 성은 "b XOR a"와 같은 "a XOR b"를 의미합니다.

a = a XOR b
b = a XOR b = (a XOR b) XOR b
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b
= (b XOR a) XOR (a XOR b) XOR b
연관성은 "a XOR (b XOR c)"와 같은 "(a XOR b) XOR c"를 의미합니다.

a = a XOR b
b = a XOR b = (a XOR b) XOR b
= a XOR (b XOR b)
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b
= (b XOR a) XOR (a XOR b) XOR b
= b XOR (a XOR a) XOR (b XOR b)
XOR의 역 요소는 그 자체입니다. 즉, XOR 값 자체가 0을 제공함을 의미합니다.

a = a XOR b
b = a XOR b = (a XOR b) XOR b
= a XOR (b XOR b)
= a XOR 0
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b
= (b XOR a) XOR (a XOR b) XOR b
= b XOR (a XOR a) XOR (b XOR b)
= b XOR 0 XOR 0
XOR의 식별 요소는 0입니다. 즉, 0 인 XOR 값은 변경되지 않습니다.

a = a XOR b
b = a XOR b = (a XOR b) XOR b
= a XOR (b XOR b)
= a XOR 0
= a
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b
= (b XOR a) XOR (a XOR b) XOR b
= b XOR (a XOR a) XOR (b XOR b)
= b XOR 0 XOR 0
= b XOR 0
= b
그리고 그룹 이론 에서 더 많은 정보를 얻을 수 있습니다 .