알고리즘
[python] XOR 문제 해결
Alan_Kim
2025. 4. 12. 13:38
728x90
반응형
XOR이란 무엇인가?
음이 아닌 정수는 항상 이진법으로 유일하게 표현할 수 있다.
이때, 각 자리 숫자는 또는 이며, 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)
728x90
반응형