XOR을 이용한 간단한 트릭들

XOR 연산은 비트를 기준으로 연산을 하게 되는데 두 비트가 같으면 0 다르면 1이다. 다시말해 자기 자신과 xor 연산을 하게 된다면 모든 비트가 같으므로 0이 나오게 되고 0과 xor연산을 하게 되면 자기 자신이 나오게 된다는 뜻이다.

 

 

이 것을 이용해서 한번 값을 스왑해보자.

 

맨 처음 x=n, y=m이 들어있다고 가정해보자. (n,m은 정수) x에 x^y값을 넣어준다. 따라서 현재 x에는 n^m이 들어있는 상태이다.

 

그 상태에서 y에 x^y값을 넣어주자. 그렇게 된다면 y에는 (n^m)^m 값이 들어가게 되고 m^m은 0이고 0^n=n이므로 y에는 n이 들어가게 된다.

 

마지막으로 x에 x^y값을 넣어주게 된다면 (n^m)^n이므로 n^n=0 0^m은 m으로 x에는 m이 들어가게 된다. 최종적으로 y=n, x=m으로 두 값을 스왑할 수 있었다.

 

 

다음은 xOR 누적합이다. n개의 원소가 있는 배열에서 x~y까지 xor한 값을 얻고싶은 경우 이다.

 

일반적 누적합 구하듯이 XOR prefix sum을 구해준다. 그렇게 되면 최종적으로 0(일반적으로 N+1의 크기를 갖고 맨 앞이 0 인 누적합을 구현하므로 ) , a1, a1^a2, a1^a2^a3 ... a^n-1^an 이런 배열을 얻을 수 있다.

 

여기서 누적합 배열의 x는 1~x까지의 a1^a2..^ax를 가지고 있을 것이고 y는 1~y까지의 a1^a2..^ay를 가지고 있을 것이다. 이때 중요한 것은 x<y이므로 y의 중간에는 a1^a2..^ax-1^ax^ax+1...^ay가 있다는 것이다.

 

즉 y는 x를 포함하고 있고 이 둘을 xor하게 된다면 자기 겹치는 a1^a2..^ax는 모두 사라지게 된다. 그러므로 일반적으로 누적합을 구하듯이 x-1까지의 누적합과 y를 xor하게 된다면 ax^ax+1^...^ay를 구할 수 있게 된다.

 

xor은 꽤나 재미있는 연산이다.