XOR 비트 연산의 특징 및 코딩 문제들

코딩 문제를 풀다보면 XOR 연산을 활용하는 부류가 꽤 있다. 이는 XOR 비트 연산이 가지고 있는 몇가지 특징 때문인데, 이들을 잘 활용하면 Time Complexity와 Space Complexity를 각각 O(n)과 O(1)으로 줄일 수 있다. 따라서 특정 문제들에 대해서는 굉장히 효율적인 답안이 될 수 있다.

 

XOR 비트 연산 특징

1. A ^ B = C  -> A ^ C = B. (^ : XOR 연산) 

위 식에서 A와 C를 알고 있을 때 B를 구하는 것이 목표이다. 이때 XOR의 연산 특성 사, A와 C 를 XOR 연산한 것이 바로 B이다. ex) 4 ^ 2 = 6 (100 ^ 010 = 110) -> 4 ^ 6 = 2 (100 ^ 110 = 010)

이는 다른 비트 연산들 (AND, OR, NOT)에는 적용이 안되고 XOR 비트 연산에만 있는 특징이다.

아래 Leet Code 문제를 풀어보자.

[LeetCode] 1720 Decode XORred Array

 

1. A ^ A = 0
2. A ^ B ^ A = B
3. (A ^ A  ^B) = (B ^ A ^ A) = (A ^ B ^ A) = B

 위 특징을 활용하면 다음 문제를 풀 수 있다. Int 배열에 모든 서로 다른 값의 원소가 2개씩 저장되어 있다. 그리고 1개의 원소만 단 1개 저장되어 있다. 이 원소를 어떻게 찾을 수 있을까?

 위 문제는 얼핏 보면 쉬워 보인다. Map을 활용해 배열 원소를 순차적으로 접근하여 Counting 하는 방법이 있다. 혹은 배열을 Sorting 한 후, 2개씩 연속되지 않는 숫자를 찾아보면 된다. 위와 같은 방법은 Time Compelxity가 각각 O(N), O(NlogN)이고 Space Complexity가 각각 O(N), O(1)이다.

 이 문제는 위에 명시한 XOR 연산의 3개의 특징을 활용하면 Time Complexity와 Space Complexity가 각각 O(N), O(1)인 알고리즘을 짤 수 있따. 배열의 모든 원소를 XOR 연산 해주면 그 결과가 바로 1개의 원소 값이 된다. (와우!)

 LeetCode 문제는 136. Single Number 이다.

Single Number - LeetCode