[구현 팁] Parity bit을 이용한 짝수 홀수 구별법

BOJ 20056 마법사 상어와 파이어볼 문제에서는, 여러 파이어볼이 합쳐질 때, 방향에 해당하는 d 값이 모두 짝수 혹은 홀수인지 아닌지를 판별해야 한다.

 

비트 연산을 활용해서 깔끔하게 해당 문제를 해결할 수 있다!

 

int parity = init_fireball.dir & 1; // partiy -> bit for checking odd/even consistency
bool mixed = false; // true if odd and even are mixed
for (FB& fireball : v) {
  ...
  
  // once changed to true, no more checking
  if(!mixed) 
  	mixed = parity ^ (fireball.dir & 1);
}

parity는 1 bit로 취급하며, 0 혹은 1의 값만 가진다.

짝수는 맨 마지막 비트가 항상 0이고, 홀수는 항상 1이다. 

따라서, parity = N & 1 은 N이 짝수일 때 0, 홀수일 때 1이다.

즉, parity bit으로 숫자의 짝수 홀수 여부를 나타낼 수 있다!!

 

위 내용을 이해했으면,

이제 다른 숫자 M이 왔을 때 N/M이 둘다 짝/홀 인지 아닌지 parity끼리의 XOR 연산으로 체크할 수 있다.

 

bool bothEvenOrOdd = parity ^ (M & 1); 

 

단순히 M의 parity를 구해서, 기존에 구해놓은 N의 parity와 XOR 연산을 해준다.

만약 둘 다 1 혹은 0이라면 (N과 M 모두 짝수 혹은 홀수) XOR 연산은 0을 뱉을 것이고,

다르다면 (N과 M이 각각 짝수/홀수) 1을 뱉는다.

 

x ^ y 의 결과 (XOR)

 

이런 식으로, 여러 수의 짝홀 여부를 간단히 체크할 수 있다!