[알고리즘] 혼자인 값 찾기

2N+1개의 값이 배열에 저장되어 있다.

 

단 하나의 값을 제외한 N개의 값들이 두번씩 나타난다. 한번만 나타나는 값은 무엇인가?

 

답 : 모든 값을 XOR했을 때 나온 값이 정답.

 

이유 : xor은, 비트연산으로 비트가 서로 다를 때 1이 된다.

하지만 같은 값들끼리는 비트도 당연히 같을 것이기 때문에 항상 0이다.

따라서 XOR값이 결국에는 다른 1개의 값만 남게 될 것이다.