[Algorithm] 비트마스킹(bitmasking)

비트마스킹?

컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다.

이와 같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스크라고 한다.

비트 마스크를 이용하면 더 빠른 수행시간, 간결한 코드, 적은 메모리 사용의 효과를 얻을 수 있다.

 

비트 연산자

• a & b: AND 연산
• a | b: OR 연산
• a ^ b: XOR 연산
• ~a: NOT 연산
• a << b: a를 b비트 만큼 왼쪽으로 시프트
• a >> b: a를 b비트 만큼 오른쪽으로 시프트

 

집합 표현

비트마스크를 이용하면 집합을 쉽게 표현할 수 있다.

 

원소 추가

현재 상태 cur이 있을 때, p번째에 원소를 추가한다고 하면 다음과 같다

cur = cur | (1 << p)

 

원소 삭제

현재 상태 cur이 있을 때, p번째에 원소를 삭제한다고 하면 다음과 같다

cur = cur & ~(1 << p);

 

원소 토글

현재 상태 cur이 있을 때, p번째에 원소 상태를 변경한다고 하면 다음과 같다

cur = cur ^ (1 << p);

 

집합 연산

a | b // 합집합
a & b // 교집합
a & ~b // a - b 차집합
a ^ b // a와 b중 하나에만 포함된 원소들의 집합

 

집합의 크기 구하기

집합의 크기를 구하려면, 현재 1로 켜져있는 비트의 수를 count 해야한다. 따라서 모든 비트를 순회해야 하고 재귀적으로 다음과 같이 구현할 수 있다.

int bitCount(int x) {
  if (x == 0) {
    return 0;
  }
  return x % 2 + bitCount(x / 2);
}

 

모든 부분집합 순회하기

어떤 집합의 모든 부분 집합을 순회하는 과정도 정말 간단하게 구현할 수 있다.

for (int subset = set; subset >= 0; subset = (subset - 1) & set) {
  // subset은 set의 부분집합 중 하나.
}