XOR 연산에 대한 짧은 글

문제풀이에서 XOR 연산과 관련한 흥미로운 내용이 있어 찾아보았습니다.

 

XOR연산이란?

논리연산으로 둘이 다른 값을 가질때 true, 같은 값을 가질때 false를 가집니다.

A	B	A xor B
0	0	0
0	1	1
1	0	1
1	1	0

 

컴퓨터에서 XOR연산을 한다는 것은 두 데이터의 비트(bit)들 중 서로 일치하지 않는 것들의 모임이라고 할 수 있습니다.

 

따라서 같은 숫자를 XOR연산하게 되면 모든 비트들이 일치하기 때문에 0이 나오게 됩니다.

3	3	3 ^ 3
0011	0011	0000

이런 특성을 이용해 다음과 같은 문제를 해결할 수 있습니다.

 

N개의 정수가 주어질 때 딱 한개의 숫자만 한번 나타나고 나머지는 두번씩 나타난다고 가정할 때, 한번만 나타나는 숫자를 구한다.

 

이 문제를 Set이나 Map같은 자료구조를 이용해 풀고자 할 경우에는 O(N/2)의 공간복잡도를 갖습니다. 하지만 XOR연산의 특성을 이용하면 O(1)의 공간복잡도를 가지고 해결할 수 있게 됩니다.

왜냐하면 두번씩 나타나는 모든 수들은 XOR연산으로 사라지게 되고 한번만 나타나는 수만 남게 되기 때문입니다.

5개의 정수 3, 5, 7, 3, 5 가 주어졌을 때 XOR연산을 통해 다음과 같이 구할 수 있습니다.

3	3 ^ 5	3 ^ 5 ^ 7	3 ^ 5 ^ 7 ^ 3	3 ^ 5 ^ 7 ^ 3 ^ 5
0011	0110	0001	0010	0111

신기하게도 모든 수들을 XOR연산하니 한번만 나타나는 수가 마지막 결과로 나타나는 것을 확인할 수 있습니다.

 

또한 두 수의 XOR연산 결과에 대해 각 수로 분리할 수 있습니다.

두 수의 XOR결과는 두 수가 다른 값을 가지는 비트들의 모음이기 때문에 1로 나타나지는 비트들은 두 수중 하나에만 존재하는 비트일 것입니다.

따라서 해당 비트와의 AND연산 결과가 0이라면 결합된 두 수중 하나일 가능성이 존재하게 됩니다.

 

예를 들어 3과 5를 XOR연산한다면 다음과 같습니다.

3	5	3 ^ 5
0011	0101	0110

이때 xor의 결과로 나타나는 0110은 3과 5에서 일치하지 않는 비트들의 모임입니다.

 

이를 두개의 수로 나눌 수 있습니다. 0100, 0010입니다.

0100은 오직 0101(5)에만 1로 존재하는 비트이고 0010은 0011(3)에만 1로 존재하는 비트입니다.

따라서 5와 0010을 AND연산하면 0이 나올 것이고, 이것은 5가 XOR결과 0110의 피연산자일 수 있다는 의미가 됩니다.