XOR 연산

알고리즘 문제풀 때 XOR 연산을 사용한다면 3가지만 기억하자.
^ 기호는 XOR 연산을 말한다.

1. XOR 연산은 순서에 상관없음

a ^ ( b ^ c )  = ( a ^ b  ) ^ c

2. 자기 자신을 XOR 연산하면 0 이 나옴

a ^ a = 0

3. 0 과 XOR 연산하면 자기 자신이 나옴

a ^ 0 = a

 

문제 예시

3개의 점이 주어지고 정사각형을 만들기 위한 나머지 점을 구해라.

예시)

(x1, y1), (x2, y2), (x3, y3) 의 3개의 점과 나머지 하나의 점을 통해 정사각형을 만들려고 한다.
나머지 점을 구해라.
x1 ^ x2 ^ x3 을 했을 때 나오는 수가 나머지 한 점의 x 좌표가 된다.
y1 ^ y2 ^ y3 을 했을 때 나오는 수가 나머지 한 점의 y 좌표가 된다.
따라서, XOR 연산을 통해 나머지 점을 구할 수 있다.