대부분이 잘 알고 있는 논리 연산은 주로 'AND 연산'과 'OR 연산'이며, 'XOR 연산'도 매우 중요합니다.

본 글에서는 XOR 연산의 의미와 응용을 소개합니다.

1. 의미

XOR은 exclusive OR의 약자입니다. 영어의 exclusive는 '독점적이거나 고유한'이라는 의미로, XOR은 더 순수한 OR 연산이라고 할 수 있습니다.

OR 연산자는 두 가지 경우가 있는데, 계산 결과는true입니다.

(1) 하나는 true이고 다른 하나는 false일 때

(2) 둘 다 true일 때

위의 두 가지 경우를 명확히 구분해야 할 때 XOR이 도입되었습니다.

XOR는 두 번째 경우를 배제하고, 오직 첫 번째 경우(하나의 연산자가 true, 다른 하나가 false인 경우)만 true를 반환하므로, 더 순수한 OR 연산으로 볼 수 있습니다. 즉, XOR은 주로 두 값이 다른지 여부를 판단하는 데 사용됩니다.

XOR은 일반적으로 삽입 기호(caret) ^로 표시됩니다. 만약 0을 false로, 1을 true로 합의한다면, XOR의 연산 진리표는 다음과 같습니다.

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

이.2. 연산 법칙

XOR 연산은 다음과 같은 연산 법칙을 가집니다. 매우 간단하기 때문에 여기서는 증명을 생략합니다.

（1） 하나의 값과 자기 자신의 연산은 항상 false입니다.

x ^ x = 0

(2) 하나의 값과 0의 연산은 항상 자기 자신과 같습니다.

x ^ 0 = x

(3) 교환 법칙

 x ^ y = y ^ x

(4) 결합 법칙

x ^ (y ^ z) = (x ^ y) ^ z

세 번째, 응용

위의 연산 법칙을 바탕으로 XOR 연산의 많은 중요한 응용을 얻을 수 있습니다.

3.1 계산 단순화

여러 값의 XOR 연산은 연산 법칙을 통해 단순화할 수 있습니다.

a ^ b ^ c ^ a ^ b
= a ^ a ^ b ^ b ^ c
= 0 ^ 0 ^ c
= c

3.2 값 교환

두 변수를 연속으로 세 번 XOR 연산을 하면 값이 서로 교환됩니다.

두 변수가 x 와 y 라고 가정하고, 각각의 값이 a 와 b 이라고 합니다. 아래는 x 와 y 이 세 번의 XOR 연산을 수행하는 과정으로, 주석 부분은 각 연산 후 두 변수의 값입니다.

x = x ^ y // (a ^ b, b)
y = x ^ y // (a ^ b, a ^ b ^ b) => (a ^ b, a)
x = x ^ y // (a ^ b ^ a, a) => (b, a)

이 두 변수의 값을 교환하는 가장 빠른 방법이며, 추가적인 공간이 필요하지 않습니다.

3.3 암호화

XOR 연산은 암호화에 사용될 수 있습니다.

첫 번째 단계, 평문(text)과 키(key)를 XOR 연산하면 암호문(cipherText)을 얻을 수 있습니다.

text ^ key = cipherText

두 번째 단계, 암호문과 키를 다시 XOR 연산하면 평문으로 원래의 내용을 복원할 수 있습니다.

cipherText ^ key = text

원리는 간단합니다. 평문이 x이고 키가 y라면, x가 y와 연속해서 두 번 XOR 연산을 하면 자기 자신이 됩니다.

(x ^ y) ^ y
= x ^ (y ^ y)
= x ^ 0
= x

3.4 데이터 백업

XOR 연산은 데이터 백업에 사용할 수 있습니다.

파일 x와 파일 y를 XOR 연산하여 백업 파일 z를 생성합니다.

x ^ y = z

그 후, 파일 x 또는 파일 y가 손상되더라도 두 원본 파일이 동시에 손상되지 않는 한 다른 파일과 백업 파일을 통해 복원할 수 있습니다.

x ^ z
= x ^ (x ^ y) 
= (x ^ x) ^ y
= 0 ^ y
= y

위 예시에서는 y가 손상되었고, x와 z를 XOR 연산하면 y를 얻을 수 있습니다.

네, 면접 문제

일부 면접 알고리즘 문제도 XOR 연산을 사용하여 빠르게 해결할 수 있습니다.

아래 문제를 보세요.

배열에는 n-1개의 멤버가 포함되어 있으며, 이 멤버들은 1부터 n까지의 정수이고 중복되지 않습니다. 빠진 숫자를 찾아보세요.

가장 빠른 해결 방법은 배열의 모든 멤버(A[0]부터 A[n-2]까지)와 1부터 n까지의 정수를 모두 합쳐서 배타적 논리곱(비트 XOR)을 수행하는 것입니다.

A[0] ^ A[1] ^ ... ^ A[n-2] ^ 1 ^ 2 ^ ... ^ n

위 식에서 배열의 각 멤버는 두 번 나타납니다. 같은 값의 멤버들을 배타적 논리곱하면 0이 됩니다. 빠진 숫자는 한 번만 나타나므로, 마지막으로 얻는 값이 바로 이 값입니다.

당신은 덧셈으로도 이 문제를 풀 수 있다는 것을 생각해 볼 수 있을 것입니다.

1 + 2 +  ... + n - A[0] - A[1] - ... - A[n-2]

하지만 덧셈은 배타적 논리곱보다 느리며, 추가적인 공간이 필요합니다. 숫자가 크다면 오버플로우가 발생할 수 있습니다.

아래는 유사한 문제로, 연습을 위해 참고해 보세요.

배열에는 n+1개의 멤버가 포함되어 있으며, 이 멤버들은 1부터 n까지의 정수입니다. 하나의 멤버는 두 번 나타나고 다른 멤버들은 한 번만 나타납니다. 반복되는 멤버를 찾아보세요.

5. 참고 링크

• XOR 기법

（끝）