xor 연산을 이용한 간단한 코딩 스킬들

이 글은 학회 회원 랑이집사님의 허락을 받아 에브리타임 게시글을 그대로 가져왔습니다.

 

 

알아두면 언젠간 쓸데가 있을지도 몰라요

우선 시작하기 전에 xor의 성질 하나만 보고 들어갈게요.
편의상 xor기호는 c언어에서 사용하는 ^ 기호를 사용할건데, 이 글에서 나오는 모든 ^는 제곱의 의미가 아니라 xor입니다!

a ^ b ^ c = a ^ c ^ b
xor연산은 순서를 바꿔도 같은 결과가 나옵니다.

a ^ a = 0
자기자신과 xor연산을 하면 0이 됩니다.

a ^ 0 = a
0과 xor하면 자기자신이 나옵니다.

세가지만 기억하시면 돼요


1. temp 없이 두 수 교환하기
보통 두 변수의 값을 교환하는건 아래처럼 사용하죠
temp = a
a = b
b = temp

하지만 xor의 성질을 이용하면 아래처럼 temp없이도 교환이 가능합니다.

a = a ^ b
b = b ^ a
a = a ^ b

첫번째 연산의 결과로 a에는 a^b가 들어가고, 두번째 연산의 결과로 b에 b^a^b가 들어가는데, 이 값은 순서를 바꿔서 b^b^a = 0^a = a가 됩니다. 따라서 두번째줄까지 실행하면 a에는 a^b가, b에는 a가 들어가게 되고, 세번째줄을 실행하면 같은 원리로 a에 b가 들어가게 돼서 둘의 위치가 서로 변하게 됩니다.
어디 면접에서 추가 메모리 없이 두 변수 바꾸는법 물어보면 편하게 대답하시면 됩니당

--->
a와 b가 같으면 둘 다 0이 되어 버립니다! 주의해주세요!!

2. 세 변수 중 두개가 같을 때 다른 하나 찾기
변수 a, b, c가 있고 셋중 둘은 같은 값이, 나머지 하나는 다른 값이 들어있다고 할게요. 어떤게 같은지는 모르는 상황에 셋중 다른 하나의 값이 궁금하면 다음과 같은 코드로 알 수 있습니다.
a ^ b ^ c
서로 같은 둘이 사라져서 0이 되고, 달랐던 나머지 하나가 나오게 되는거죠. x축에 평행한 두 선분과 y축에 평행한 두 선분으로 이루어진 직사각형의 꼭짓점 중 세 점을 알 때 나머지 하나의 점을 찾으라는 문제가 나온다면 저걸 x값에 한번, y값에 한번 적용하는걸로 딱 두줄만에 해결 가능합니다.
작년 카카오 블라인드채용 마지막 문제에 응용할만한 부분이 나옵니다.