XOR 스왑 알고리즘

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "XOR 스왑 알고리즘" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2012년 2월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

임시 저장소를 사용하지 않고 XOR 스왑 알고리즘을 사용하여 변수 간에 니블 교환

컴퓨터 프로그래밍에서 배타적 또는 스왑(XOR 스왑으로 축약되기도 함)은 일반적으로 필요한 임시 변수를 사용하지 않고 배타적 또는 비트 와이즈 연산을 사용하여 두 변수의 값을 교환하는 알고리즘이다.

알고리즘은 주로 새로움과 배타적 또는 운용의 특성을 입증하는 방법이다.프로그램 최적화로서 논의되기도 하지만, 배타적으로 스와핑을 하거나 표준적이고 명백한 기술에 비해 이익을 제공하는 경우는 거의 없다.

알고리즘

기존 스와핑에는 임시 저장 변수를 사용해야 한다.그러나 XOR 스왑 알고리즘을 사용하면 임시 저장소가 필요하지 않다.알고리즘은 다음과 같다.^[1][2]

X := X XOR Y; /* XOR 그 가치 그리고 저장하다 그 결과 에 X */ Y := Y XOR X; /* XOR 그 가치 그리고 저장하다 그 결과 에 Y */ X := X XOR Y; /* XOR 그 가치 그리고 저장하다 그 결과 에 X */ 

XOR는 상호 작용하기 때문에 XOR Y 또는 Y XOR X 중 하나를 앞의 세 줄에서 서로 교환하여 사용할 수 있지만, 3-XOR 스왑이 어셈블리 언어로 코딩된 경우에는 XOR 지침의 첫 번째 피연산자가 대상 위치를 지정하기 때문에 각 단일 라인 내에서 이 교환성을 사용할 수 없다.작업 결과가 저장된다.알고리즘은 일반적으로 다음 표의 세 행에 해당하는 유사 코드 및 조립 지침으로 표현되는 세 가지 기계 코드 지침에 해당한다.

위의 시스템/370 조립품 코드 샘플에서 R1과 R2는 별개의 레지스터로, 각각XR연산 결과는 첫 번째 변수에 명명된 레지스터에 남겨둔다.x86 어셈블리를 사용하여 값 X와 Y는 레지스터 eax와 ebx에 있다(존중).xor수술 결과를 제1부에 기입하다

그러나 유사코드 또는 고급 언어 버전 또는 구현에서 x와 y가 동일한 저장 위치를 사용하면 알고리즘이 실패하는데, 이는 해당 위치에 저장된 값이 첫 번째 XOR 명령에 의해 영(0) 처리된 후 영(0)으로 유지되기 때문이다. 이 알고리즘은 "자체와의 교환"이 되지 않는다.이것은 x와 y의 값이 같은 것과 같지 않다.문제는 x와 y가 동일한 저장 위치를 사용할 때만 발생하며, 이 경우 해당 값은 이미 동일해야 한다.즉, x와 y가 동일한 저장 위치를 사용하는 경우 다음 행:

X := X XOR Y 

x를 0으로 설정하고(x = y가 0이기 때문에) y를 0으로 설정(같은 저장 위치를 사용하므로) y를 0으로 설정하여 x와 y의 원래 값을 잃게 한다.

정확성 증명

길이 $N{\displaystyle }$ ${\displaystyle N}$의 비트 문자열에 대한 이진 작업 XOR는 다음과 같은 속성을 나타낸다$$(^[a]여기서${\displaystyle }$where$${\$displaystyle \oplus$}은 XOR을$$ 나타낸다).

• L1. 공통점:${\displaystyle A\oplus B=B\oplus A}$
• L2. 연관성:${\displaystyle }$(${\displaystyle A}$ ${\displaystyle \oplus }$ ${\displaystyle B}$) ${\displaystyle \oplus }$ C${\displaystyle }$= ${\displaystyle A}$ ${\displaystyle \oplus }$(${\displaystyle B}$ ${\displaystyle \oplus }$ ${\displaystyle C}$) ${\displaystyle (A\oplus$ B$)\oplus C=A\oplus (B\oplus C)}$
• $L3{\displaystyle }$. ID가 있음: A$${\$displaystyle$A}에 대해 A${\displaystyle 0}$0 = ${\displaystyle A}${\$displaystyle$A\$oplus$0=$A}$과 같은 비트 문자열이 있음
• L4. 각 원소는 그 자체로 반비례한다: $각{\displaystyle }$ A ${\displaystyle A$ ${\displaystyle A}$⊕ A${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle A\oplus A=0$

두 개의 서로 다른 레지스터가 있다고 가정해 보십시오.R1그리고R2아래 표와 같이 각각 초기 값 A와 B를 사용한다.우리는 아래의 작업을 순서대로 수행하고, 위에 나열된 속성을 사용하여 결과를 줄인다.

스텝	작전	1번 등록	등록2길	축소
0	초기값	$(\displaystyle A}$	$B형 표시$	—
1	R1 := R1 XOR R2	$A\oplus B}$	$B형 표시$	—
2	R2 := R1 XOR R2	$A\oplus B}$	$[\displaystyle (A\oplus B)\oplus B=A\oplus (B\oplus B)}$ $#\displaystyle =A\oplus 0}$ $(\displaystyle =A}$	L2 L4 L3
3	R1 := R1 XOR R2	$(A\displaystyle (A\oplus B)\oplus A=(B\oplus A)\oplus A}$ $[\displaystyle =B\oplus(A\oplus A)}$ ${\displaystyle =B\oplus 0}$ ${\displaystyle =B}$	$(\displaystyle \ A}$	L1 L2 L4 L3

선형대수해석

XOR는 이진 덧셈으로 해석할 수 있고 비트 쌍은 두 개의 원소가 있는 필드 위에 있는 2차원 벡터 공간에서 벡터로 해석할 수 있기 때문에 알고리즘의 단계는 두 개의 원소가 있는 필드 위에 2×2 행렬에 의해 곱셈으로 해석할 수 있다.단순성을 위해 처음에는 x와 y가 비트 벡터가 아닌 각 단일 비트라고 가정하십시오.

예를 들어 다음 단계를 참조하십시오.

X := X XOR Y 

또한 다음과 같은 암묵적인 내용을 담고 있다.

Y := Y 

매트릭스1. ) ${\${smallmatrix$}\right}$에 해당한다.

${\displaystyle {\pmatrix}1&#1\0&1\end{pmatrix}{pmatrix}{pmatrix}x\y\end{pmatrix}={\pmatrix}x+y\y\end{pmatrix}}.}$

작동 순서는 다음과 같이 표현된다.

${\displaystyle {\pmatrix}1&#1\0&1\end{pmatrix}{pmatrix}{pmatrix}1&0\1\end{pmatrix}{pmatrix}}}{\nd{pmatrix}}}}{pmatrix}}}}}}:{pmatrix}}}}}}}}}}}}nd}nd}ndata.$

($따라서{\displaystyle \mathrm{}}$ 1${\displaystyle }$+ ${\displaystyle 1}$= ${\displaystyle 0}$ ${\displaystyle 1+1=0})$ 한 요소를 다른 요소에 추가하는 변환(시어) 측면에서 두 행(또는 열)을 전환하는 기본 행렬을 나타낸다.$$

X와 Y가 단일 비트가 아닌 길이 n의 비트 벡터인 곳에 일반화하기 위해, 이러한 2×2 매트릭스는 I 0 )과 같은 2n×2n 블록 매트릭스로 대체된다 ${\displaystyle \left({\be{smallmatrix}).$$I_{n}&I_{n}\\0&$$I_{n}\end{smallmatrix}\오른쪽).$$}$

이러한 행렬은 (저장 위치가 있는) 변수가 아닌 값으로 작동하므로, 이러한 해석은 저장 위치의 문제와 두 변수가 동일한 저장 위치를 공유하는 문제를 추상화한다.

코드 예제

XOR 스왑 알고리즘을 구현하는 C 함수:

공허하게 하다 소르스왑(인트로 *x, 인트로 *y)  {   만일 (x != y)   {     *x ^= *y;     *y ^= *x;     *x ^= *y;   } } 

코드는 먼저 주소가 구별되는지 확인한다.그렇지 않으면 알고리즘이 동일한 경우, 알고리즘이 세 배 *x ^= *x로 접혀 0이 된다.

XOR 스왑 알고리즘도 매크로로 정의할 수 있다.

#정의 XORSWAP_UNSAFE(a, b) \ (a) ^= (b), (b) ^= (a), \ (a) ^= (b)/* a와 b가 동일한 개체일 경우 작동하지 않음 - 0 \ 할당 (0) 이 경우 객체에 */ #정의 XORSWAP(a, b) \ ((&(a) ==(b) ?(a)/* 고유 주소 확인 */\ : XORSWAP_UNSAFE(a, b) 

실무상 기피사유

현대의 CPU 아키텍처에서 XOR 기술은 스와핑을 하기 위해 임시 변수를 사용하는 것보다 느릴 수 있다.적어도 최근의 x86 CPU에서는 AMD와 Intel이 모두 레지스터 사이를 이동하면 지연 시간이 0으로 발생한다. (이것을 MOV-제거라고 한다.)사용할 수 있는 건축 등록부가 없더라도XCHG지시는 적어도 세 개의 XOR를 합친 것만큼 빠를 것이다.또 다른 이유는 현대 CPU가 명령 파이프라인을 통해 병렬로 명령을 실행하려고 하기 때문이다.XOR 기법에서는 각 연산에 대한 입력은 이전 연산의 결과에 따라 달라지기 때문에 엄밀하게 순차적으로 실행해야 하며, 명령 수준 병렬화의 편익을 부정한다.^[3]

앨리어싱

XOR 스왑도 앨리어싱으로 실무적으로 복잡하다.일부 위치의 콘텐츠를 XOR 스와핑하려고 하면 위치가 영점 처리되고 그 가치가 상실된다.따라서 XOR 스와핑은 앨리어싱이 가능하다면 높은 수준의 언어로 맹목적으로 사용되어서는 안 된다.

이름별 호출을 할 때도 비슷한 문제가 발생하는데, 이는 교환하는 젠슨스 장치에서와 같다.i그리고A[i]임시 변수를 통해 관련 인수로 인해 잘못된 결과가 도출됨: 스와핑을 통해temp = i; i = A[i]; A[i] = temp값을 바꾸다i두 번째 문장에서, 그 다음 에 대한 부정확한 i 값을 산출한다.A[i]제3차 진술서에

변형

XOR 스왑 알고리즘의 기본 원리는 위의 L1에서 L4까지의 모든 운용기준에 적용될 수 있다.덧셈과 뺄셈으로 XOR를 대체하면 다음과 같이 약간 다르지만 대체로 동등한 제형을 얻을 수 있다.

공허하게 하다 애드스왑( 서명이 없는 인트로* x, 서명이 없는 인트로* y ) {   만일 (x != y)   {     *x = *x + *y;     *y = *x - *y;     *x = *x - *y;   } } 

XOR 스왑과 달리, 이러한 변동은 기본 프로세서나 프로그래밍 언어가 모듈식 산술이나 비그넘과 같은 방법을 사용하여 계산이 이루어지도록 보장할 것을 요구한다.X + Y정수 오버플로로 인한 오류를 발생시킬 수 없다.따라서 XOR 스왑보다 실전에서 더 드물게 보인다.

단, 의 실시.AddSwap 위의 C 프로그래밍 언어에서는 정수 오버플로의 경우에도 항상 작동하는데, 이는 C 표준에 따라 부호화되지 않은 정수의 덧셈과 뺄셈이 모듈식 산술의 규칙을 따르기 때문이다. 즉$,$ $주기{\displaystyle }$ ${\displaystyle \mathbb{}}$ Z$/$(\displaystyle $\mathb {Z}/2^}{s$$}$s}\$mathb$ ${Z}}$에서 수행되기 때문이다.의 비트 수unsigned int. 실제로 알고리즘의 정확성은 공식$({\displaystyle x}$+ y${\displaystyle }$) -${\displaystyle y}$= ${\displaystyle x}$ ${\displaystyle (x+y)-y=x}$ 및$$${\displaystyle }$( x${\displaystyle }$+ y${\displaystyle }$)${\displaystyle }$-${\displaystyle }$(${\displaystyle x}$+ ${\displaystyle y}$)${\displaystyle }$- ${\displaystyle y}$= y ${\displaystyle (x+y)-(x+y)-y)=y}$이$$ 모든 아벨리아 그룹에서 유지된다는 사실에서 따르게 된다.This is actually a generalization of the proof for the XOR swap algorithm: XOR is both the addition and subtraction in the abelian group ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{s}}$ (which is the direct sum of s copies of ${\displaystyle \mathbb {Z} /2\mathbb {Z} }$).

이 일은 그 일을 처리할 때 버틸 수 없다.signed int타이프(기본값)int부호화된 정수 오버플로는 C에서 정의되지 않은 동작이므로 모듈식 산술은 표준에 의해 보장되지 않는다(표준적합성 컴파일러가 그러한 코드를 최적화하여 잘못된 결과를 초래할 수 있다).

작업 순서:AddSwap행렬 곱셈을 통해 다음과 같이 표현할 수 있다.

${\displaystyle {\pmatrix}1&#1\\0&1\end{pmatrix}{pmatrix}{pmatrix}1&0\1\end{pmatrix}{pmatrix}}}{pmatrix}}}}{pmatrix}}}}}}}{pmatrix}}}}}}}}}}}}}}}nd}$

참고 항목

• 대칭차이
• XOR 연결 목록
• Feistel 암호(XOR 스왑 알고리즘은 Feistel 암호의 퇴보한 형태)

메모들

참조