[python] XOR 문제 해결

 

XOR이란 무엇인가?

음이 아닌 정수는 항상 이진법으로 유일하게 표현할 수 있다.

이때, 각 자리 숫자는 0 또는 1이며, 2의 k승 숫자를 k번째 비트라고 한다.

 

XOR은 기호로 '^'방식으로 나타내며 임의의 두 수 x, y가 이진수로 나타냈을 때 k번 비트가 같다면 0, 다르면 1을 부여해서 결과를 얻는다.

 

예시로

xor = 0
nums = [3, 5, 2]

for num in nums:
    xor ^= num

다음과 같은 코드를 짜게 된다면 아래와 같이 동작한다.

xor = 0 ^ 3 = 3 # 00(2) ^ 11(2) = 11(2) 모든 자리 숫자가 다르므로 모든 자리 숫자 1
xor = 3 ^ 5 = 6 # 011(2) ^ 101(2) = 110(2) 1번,2번 비트 숫자가 다른 반면 3번 비트 숫자가 같으므로 110(2)
xor = 6 ^ 2 = 4 # 110(2) ^ 010(2) = 100(2) 1번 비트 숫자가 다르고 2,3번 비트 숫자가 같으므로 110(2)