XOR 교체 알고리즘 - 위키백과, 우리 모두의 백과사전 XOR 교체 알고리즘 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 XOR 교체 알고리즘은 임시 변수를 두지 않고, 두 개의 변수를 배타적 논리합 ( XOR ) 비트 연산을 이용하여 교체하는 알고리즘이다. 이 알고리즘은 컴퓨터 프로그래밍 분야에서 프로세서의 최적화 능력이 부족했을 때 대안으로 자주 사용되었다. 목차 1 개요 2 증명 3 코드 예제 4 실제 사용에서의 장단점 5 같이 보기 6 외부 링크 개요 [ 편집 ] XOR 교체 알고리즘은 세 개의 XOR 연산을 사용하여 임시 변수 없이 두 변수를 교환한다. 의사코드로는 다음과 같이 표현할 수 있다. X [UNK] X XOR Y Y [UNK] X XOR Y X [UNK] X XOR Y 보통 위의 세 줄은 각각 하나씩 세 개의 기계어 명령에 대응될 수 있다. 예를 들어 IBM System / 370에서 위 코드는 다음과 같은 어셈블리 코드로 변환된다 : XR R1, R2 XR R2, R1 XR R1, R2 여기서 R1과 R2는 레지스터이고 XR은 첫째 레지스터와 둘째 레지스터의 값을 XOR해서 그 결과값을 첫째 레지스터에 저장하는 명령이다. 하지만 이 알고리즘은 X와 Y가 같은 기억 장소를 가리
[UNK] otimes B ) [UNK] otimes C = A [UNK] otimes ( B [UNK] otimes C ) } L3. 항등원의 존재 : 어떤 A { [UNK] displaystyle A } 에 대하여서도, A [UNK] Z = A { [UNK] displaystyle A [UNK] otimes Z = A } 가 되는 값 Z = 0 { [UNK] displaystyle Z = 0 } 이 존재한다. L4. 각 원소에 대해 유일한 역원의 존재 : 각 A { [UNK] displaystyle A } 에 대하여, A [UNK] A - 1 = Z { [UNK] displaystyle A [UNK] otimes A ^ { - [UNK]! 1 } = Z } 가 되는 A - 1 { [UNK] displaystyle A ^ { - [UNK]! 1 } } 가 존재한다. L4a. 각 원소의 역원은 사실 자기 자신임 : A [UNK] A = 0 { [UNK] displaystyle A [UNK] otimes A = 0 } L1부터 L4까지의 성질은 아벨 군 ( ablian group ) 의 정의이다. L4a는 XOR 연산의 구조적 성질에 해당하는 것이며, 아벨 군이나 다른 군에 꼭 있는 성질은 아니다. R1과 R2의 두 레지스터에 값 A와 B가 저장되어 있을 때, XOR 교체 알고리즘을
때에만 교체 연산을 수행해서 문제를 제거한다. 이 코드는 종종 다음과 같은 형태로 쓰이기도 한다. if ( x! = y ) * x ^ = * y ^ = * x ^ = * y ; 하지만 이 코드는 [UNK] 포인트의 부재 때문에 올바른 C 코드가 아니며, 이 코드의 수행 결과는 컴파일러에 따라 다를 수 있다. 실제 사용에서의 장단점 [ 편집 ] XOR 교체 알고리즘은 대부분의 현대적인 프로세서에서는 임시 변수를 사용하는 방법보다 더 느린데, 그 이유 중 하나로는 임시 변수를 사용하는 방법은 여러 명령어를 동시에 실행할 수 있도록 ( 명령어 수준 병렬성 ) 최적화하기가 더 쉽기 때문이다. XOR 교체 알고리즘은 3 연산 모두 데이터 의존성 ( Read - After - Write ) 을 만들기에 반드시 순서대로만 실행해야한다. 따라서 현대 비순차 프로세서나 VLIW 컴파일러가 XOR 교체 알고리즘을 최적화할 수 있는 방법은 거의 없다. 반면, XOR 교체 알고리즘은 속도가 그리 빠르지 않아도 되고 메모리 ( 혹은 캐시 ) 사용을 최소화해야 하는 환경에서는 유용하게 사용될 수 있다. 따라서 이 방식은 임베디드 개발 환경에서 많이 이용된다. 같이 보기 [ 편집 ] 교체 연산 외부 링크 [ 편집 ] 두 변수 값 바꾸기에
다른 군에 꼭 있는 성질은 아니다. R1과 R2의 두 레지스터에 값 A와 B가 저장되어 있을 때, XOR 교체 알고리즘을 수행할 때 각각의 결과는 다음과 같다. 과정 수행된 명령 R1의 값 R2의 값 사용된 성질 1 ( 초기 상태 ) A B - - 2 R1 [UNK] R1 XOR R2 A ^ B B - - 3 R2 [UNK] R1 XOR R2 A ^ B = B ^ A ( A ^ B ) ^ B = A ^ ( B ^ B ) = A ^ 0 = A L1, L2, L4, L3 4 R1 [UNK] R1 XOR R2 ( B ^ A ) ^ A = B ^ ( A ^ A ) = B ^ 0 = B A L2, L3, L4 코드 예제 [ 편집 ] 다음은 XOR 교체 알고리즘을 구현한 C 코드이다. void swap ( int * x, int * y ) { if ( x! = y ) { * x ^ = * y ; * y ^ = * x ; * x ^ = * y ; } } 이 코드는 두 포인터가 서로 다른 메모리 공간을 가리킬 때에만 교체 연산을 수행해서 문제를 제거한다. 이 코드는 종종 다음과 같은 형태로 쓰이기도 한다. if ( x! = y ) * x
와 둘째 레지스터의 값을 XOR해서 그 결과값을 첫째 레지스터에 저장하는 명령이다. 하지만 이 알고리즘은 X와 Y가 같은 기억 장소를 가리킬 경우 제대로 동작하지 않는다. 예상했던 대로라면 두 값이 같으므로 아무 일도 일어 나지 않아야 하지만, 위 알고리즘은 첫 문장에서 X와 Y를 모두 0으로 초기화해 버리기 때문에 기억 장소에는 0이 저장된다. 만약 위의 알고리즘을 임의의 경우에도 쓸 수 있게 하려면 다음과 같은 수정이 필요하다. 만약 X [UNK] Y이면, X [UNK] X XOR Y Y [UNK] X XOR Y X [UNK] X XOR Y 증명 [ 편집 ] 비트 문자열에 대한 XOR 이항 연산은 다음과 같은 성질을 갖는다. 여기서 [UNK] { [UNK] displaystyle [UNK] otimes } 는 XOR 연산자를 뜻한다. L1. 교환법칙 : A [UNK] B = B [UNK] A { [UNK] displaystyle A [UNK] otimes B = B [UNK] otimes A } L2. 결합법칙 : ( A [UNK] B ) [UNK] C = A [UNK] ( B [UNK] C ) { [UNK] displaystyle ( A [UNK] otimes B ) [UNK] otimes C = A [UNK] otimes ( B [UNK] otimes C ) } L3. 항등원의 존재 : 어떤 A {
수 있다. 따라서 이 방식은 임베디드 개발 환경에서 많이 이용된다. 같이 보기 [ 편집 ] 교체 연산 외부 링크 [ 편집 ] 두 변수 값 바꾸기에 대한 고찰 swap 원본 주소 " " 분류 : 컴퓨터 프로그래밍 둘러보기 메뉴 개인 도구 로그인하지 않음토론기여계정 만들기로그인 이름공간 문서토론 변수 보기 읽기편집역사 보기 더 보기 검색 둘러보기 대문사용자 모임요즘 화제최근 [UNK] 문서 보기임의 문서로도움말기부 도구 여기를 가리키는 문서가리키는 글의 최근 [UNK] 올리기특수 문서 목록고유 링크문서 정보위키데이터 항목이 문서 인용하기 인쇄 / 내보내기 책 만들기PDF로 다운로드인쇄용 판 다른 언어 [UNK] 日 本 語 [UNK] / [UNK] 링크 편집 이 문서는 2019년 1월 10일 ( 목 ) 11 : 30에 마지막으로 편집되었습니다. 모든 문서는 크리에이티브 커먼즈 저작자표시 - 동일조건변경허락 3. 0에 따라 사용할 수 있으며, 추가적인 조건이 적용될 수 있습니다. 자세한 내용은 이용 약관을 참고하십시오. [UNK] 미국 및 다른 국가에 등록되어 있는 Wikimedia Foundation, Inc. 소유의 등록 상표입니다. 개인정보 정책 위키백과 소개 면책 조항 개발자 쿠키 정책 모바일 보기
XOR 교체 알고리즘(XOR swap algorithm) 또는 XOR 스왑 알고리즘은 임시 변수를 두지 않고, 두 개의 변수를 배타적 논리합(XOR) 비트 연산을 이용하여 교체(swap)하는 알고리즘이다. 이 알고리즘은 컴퓨터 프로그래밍 분야에서 프로세서의 최적화 능력이 부족했을 때 대안으로 자주 사용되었다.