XOR 연산에 대한 메모 (LeetCode 136. Single Number)

XOR 연산의 특징 4가지

1. 같은 숫자를 XOR 연산하면 0이 된다.

예시)
5를 바이너리로 바꾸면 101
같은 숫자를 XOR 연산하면

101
101
--
000

2. 0으로 XOR 연산하면 원래 숫자를 반환한다.

예시)

101
000
---
101

3. 교환법칙 (순서는 상관없다)

예시)
5와 3
3과 5 이렇게 바꿔서 연산해도 값은 같다

// 5와 3
101
011
---
110

// 3과 5
011
101
---
110

4.결합법칙 (괄호를 묶어서 계산해도 값이 같다)

(5^3)^2 = 100
5^(3^2) = 100

따라서, 136번의 문제를 풀기 위해서는 다음과 같은 풀이를 할 수 있다.
[2,1,2,1,3]이 주어졌을 때, 먼저 3번에 따라 같은 숫자끼리 모은다. -> [2,2,1,1,3]
4번에 따라, 괄호나 연산 순서는 상관없다. 또한 1번에 따라, 같은 숫자는 연산하면 0이 된다.
2와 2, 1과 1을 각각 연산하면 0이 된다.[0,0,3]
마지막으로 2번에 따라 0과 연산하는 숫자는 원래 숫자를 반환하므로, 배열안에 있는 모든 숫자를 XOR로 연산하여 나오는 값이 혼자 있는 값이 된다.

이것을 코드로 옮기면 다음과 같이 된다.

class Solution:
  def singleNumber(self, nums: List[int]) -> int:
    res = 0

    for n in nums:
      res ^= n

    return n

참고영상
https://www.youtube.com/watch?v=nMC78grcvGw&t=35s