XOR연산(⊕로 많이 표기 된다.)은 논리 이항 연산자이고, 두 입력이 다를 때만 참을 반환하는 연산자이다. 다음 그림은 XOR연산의 진리표이다.
그리고 이 연산은 Z2(Z/2Z라고도 표기한다)와 깊은 관련이 있다. Z2란, 어떤 정수를 2로 나눈 나머지인 0과 1에만 관심을 가지는 체계를 말한다. 예를 들면, 우리는 X와 Y가 어떤 수이든 관계 없이, X가 짝수이고, Y가 짝수이면 X+Y도 짝수임을 알 수 있다. 이 XOR연산은 Z2에서의 덧셈과 일치한다. 즉 홀짝성이 다른 두 수를 더해야만 홀수가 나온다.
이 xor을 비트단위로 나눠서 확장한게 bitwise-xor 이고(C, C++, Python 등에서 ^ 연산자로 많이 표기된다.), 이진법으로 표현했을 때의 각 자리마다 비트를 표기한다. 예를들면 1100(2)⊕1010(2)=0110(2) 같이, 1(2)의 자리가 0⊕0 = 0이므로 0이고, 10(2)의 자리가 0⊕1=1 인 등등.. 으로 계산한 결과이다. 이 비트단위 xor은 각 자리마다 연산이 보존 되기 때문에 우리는 각 자리를 따로 생각할 수 있고, 결론적으로 bitwise-xor 연산은 Z2n에서의 덧셈이 된다. 그리고 이것을 우리는 스칼라가 Z2이고, 각 벡터가 Z2n인, 벡터 공간으로 생각할 수 있다.
그래서 우리는 다양한 xor이 연관된 문제들을 벡터 공간으로 바꾸어서 해결 할 수 있다. 예를들면, 숫자들이 여러개 있는데 몇 개를 xor해서 최대가 되게하라는 문제를, 벡터 공간에서 최댓값을 찾아라 같은 문제들로 적당히 바꿀 수 있고, 벡터 공간은 여러가지 좋은 성질들이 많기 때문에 유용하게 사용될 수 있다. 그리고, Row space를 벡터 공간으로 가지는 행렬을 생각할 때 가장 먼저 고려되는 연산인 Reduced Row Echelon Form을 구할 때, 숫자들을 비트단위로 관리할 수 있어, 상수를 크게 줄이는데(32~64배 정도 계산량을 줄일 수 있다.) 도움을 줄 수 있다.
이 사실로 풀 수 있는 문제를 몇 개 남기려고 한다. 대부분의 문제가 어렵기 때문에, 문제를 해결 할 수 있다면 자신감을 가져도 좋다고 생각한다. 질문이 있으면 덧글로 남겨주면 된다.
