XOR 변수 교환은 어떻게 작동합니까?

StackOverflow https://stackoverflow.com/questions/249423

문제

누군가가 온도 변수가없는 두 변수를 어떻게 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 개 (또는 SO) 단계가 있었는데, 여기서 레지스터에 대한 읽기와 쓰기 사이의 의존성은 모든 것이 실속 될 수 있습니다. 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 트릭을 조금 더 쉽게 이해할 수 있습니다. ^ AS를 생각할 수 있습니다 + 또는 -. 그냥:

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 단일 "포인터"로 2 방향 링크 목록을 인코딩하기위한 오래된 트릭이 있습니다. 주소 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의 주소를 제공합니다. 그것은 뒤로 잘 작동합니다. 목록을 따라 실행하려면 포인터를 두 개의 연속 블록으로 유지해야합니다. 물론 추가/꼭대기 대신 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를 남겨두고 스왑이 완료되었습니다!

컴퓨터에는 실제로 레지스터에 다시 작성하기 전에 중간 결과를 저장하는 암시 적 "온도"변수가 있습니다. 예를 들어, 레지스터에 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 명령어가있어 두 개의 레지스터를 교환합니다.

@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 '= a xor b (1)
b '= a'xor b (2)
A”= A 'XOR B'(3)

이해하다 왜 이것은 먼저 작동합니다.

  1. Xor는 정확히 피연산자 중 하나가 1이고 다른 하나는 0 인 경우에만 1을 생산합니다.
  2. xor입니다 정류 그래서 a xor b = b xor a;
  3. xor입니다 연관성 SO (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가 연관적이기 때문에
= 위의 [4] 때문에 xor 0
= 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 위에)

보다 자세한 정보는 다음과 같습니다.필요하고 충분합니다

부수적으로 나는 몇 년 전에이 바퀴를 독립적으로 재창조하여 정수를 교환하는 형태로 다음을 수행했습니다.

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

도움이 되었기를 바랍니다. 이 설명은 이미 주어졌지만 분명히 IMO는 아닙니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top