XOR 연산자(Bit Manipulation) - LeetCode 136. Single Number

오늘은 2018년부터 함께 해오고 있는 스터디 모임에서 알고리즘 문제를 풀었다.
코로나가 심해져서 이번주는 줌으로 만났다. (물론 어제도 스타에서 만났지만..)

오늘 푼 문제는 LeetCode 136번 Single Number 다.

Given a non-empty array of integers nums, every element appears twice except for one. 
Find that single one.

You must implement a solution with a linear runtime complexity 
and use only constant extra space.

정수 숫자들의 값들로 채워진 array가 주어졌을 때, 하나의 element 빼고는 모두 두 번씩 들어있다.
그 하나의 element를 찾아라.

무조건 linear runtime complexity(O(N)의 시간 복잡도)로 풀어야하며 오직 하나의 추가 변수만 사용가능하다. 

답을 구하는게 어려워보이진 않았는데, 저 조건에 맞게 해야한다는게 까다로웠다.
indexOf로 풀어볼까 하다가 O(N)에 맞게 하기가 어려워서 혹시 sort를 쓰면 어떨까 하고 아래처럼 풀었다.

var singleNumber = function(nums) {
    nums.sort();
    for (let i = 0; i < nums.length;) {
        if (nums[i] !== nums[i+1]) return nums[i];
        else i = i+2;
    }
};

하지만 찾아보니 브라우저에서는 보통 merge sort를 쓰는데 머지소트는 O(NlogN)이라 조건에 부합하지 못했다.
다른 팀원의 설명을 들었는데, 이 문제는 비트 연산자를 통해 푸는 문제라고 한다! (띠용)

정처기 공부할때 비트 연산자에 대해서 공부했었는데, 이렇게 알고리즘에 풀 수 있을 거라곤 생각 못했다.
출처

AND(&)는 두 개의 비트가 모두 1일 때만 1반환, 나머지는 0
OR(|)은 두 개의 비트 중 한 개라도 1이면 1반환, 나머지는 0
XOR(^)은 두 개의 비트가 서로 다른 경우에만 1반환, 나머지는 0

그래서 아래처럼 풀 수 있는 것이다.

var singleNumber = function(nums) {
    let result = nums[0];
    for(var i = 1; i < nums.length; i++) {
        result = result^nums[i];
    }
    return result;
};

혹은

var singleNumber = function(nums) {
    return nums.reduce((acc, cur) => {
        return acc^cur; //XOR
    }, 0);
};

유용한 비트 연산자였다! ^