GN⁺: XOR

소개

• 최근에 XOR 연산자를 설명할 기회가 있었음. 과거에는 컴퓨터에서 저수준 비트 조작을 위해 XOR을 배우는 것이 필수였지만, 현재는 고수준 프로그래머에게는 선택 사항이 됨.
• XOR에 대한 강의를 준비하면서 다양한 생각을 정리했으며, 이를 문서로 남기기로 결정함.

XOR의 불리언 논리

XOR란 무엇인가?

• XOR는 두 개의 비트를 입력으로 받아 하나의 비트를 출력하는 논리 연산자임.
• 진리표를 통해 XOR의 동작을 설명할 수 있음.

"배타적 OR"

• XOR는 "배타적 OR"을 의미하며, 두 입력 중 하나만 참일 때 참을 반환함.

'같지 않음' 연산자

• XOR는 두 입력이 다를 때 1을 반환하므로, a ≠ b와 동일하게 작동함.

조건부 반전

• XOR는 하나의 입력이 다른 입력을 반전시킬지 여부를 결정하는 조건부 반전 연산자로 볼 수 있음.

패리티, 또는 2로 나눈 나머지

• XOR는 입력 중 홀수 개의 비트가 참일 때 1을 반환함.

2로 나눈 차이

• XOR는 덧셈과 뺄셈의 2로 나눈 나머지와 동일하게 작동함.

XOR의 성질

• XOR는 교환법칙과 결합법칙을 따르며, 0은 항등원으로 작용하고, 모든 입력은 자기 역원임.

정수에 대한 비트 단위 XOR

• 정수를 이진수로 표현하여 비트 단위로 XOR 연산을 수행할 수 있음.
• 비트 단위 XOR는 불리언 XOR와 동일한 성질을 가짐.

XOR의 응용

암호화: 평문과 키스트림 결합

• XOR는 암호화에서 평문과 키스트림을 결합하는 데 사용됨.
• XOR는 하드웨어에서 덧셈보다 간단하여 효율적임.

픽셀 그래픽: 쉽게 지울 수 있는 그림 그리기

• 1980년대 컴퓨터 그래픽에서는 XOR를 사용하여 쉽게 지울 수 있는 그림을 그렸음.
• XOR를 사용하면 픽셀을 다시 그려서 원래 상태로 복원할 수 있음.

"하프 애더 정체성"

• XOR는 덧셈의 낮은 비트를 나타내며, AND는 높은 비트를 나타냄.
• 정수에 대해 XOR와 AND를 사용하여 덧셈을 수행할 수 있음.

이 문서는 XOR의 다양한 성질과 응용을 설명하며, XOR가 어떻게 작동하고 어디에 유용하게 사용될 수 있는지를 이해하는 데 도움을 줌.