BitMask(비트마스크)

비트마스크란 정수의 이진수 표현을 자료구조로 사용하는 기법입니다.

부호없는 N비트 정수형 변수는 N자리의 이진수로 사용할 수 있습니다. 이때 각 비트가 표현하는 값은 2^0 부터 2^k-1 까지입니다. 2^k-1 에 해당하는 비트를 최상위 비트(most significant bit)라고 부르고, 2^0를 나타내는 비트를 최하위 비트(least significant bit) 라고합니다. 어떤 정수를 이진수로 표현했을 때 어떤 비트의 위치가 1이라면 해당비트가 "켜져있다"라고 말하고, 0이라면 꺼져있다고 말합니다.

비트 관련 연산 정의

• 비트별 AND 연산(&) 두 정수에 해당 비트가 모두 켜져있을때만 결과의 비트를 켭니다. (같의 위치에 있는 두 비트가 전부 1인 경우 결과가 1이고 그 이외에는 0입니다.)

      1100 = 12
  AND 1010 = 10
  ㅡㅡㅡㅡㅡㅡㅡ
      1000 = 8
  

• 비트별 OR 연산(|) 두 비트 중 하나라도 켜져 있을 경우 결과 비트를 켭니다.

      1100 = 12
  OR  1010 = 10
  ㅡㅡㅡㅡㅡㅡㅡ
      1110 = 14
  

• 비트별 XOR 연산(^) 하나는 켜져 있고 하나는 꺼져 있을 경우 결과 비트를 켭니다.

      1100 = 12
  XOR 1010 = 10
  ㅡㅡㅡㅡㅡㅡㅡ
      0110 = 6
  

• 비트별 NOT 연산(~) 정수 하나를 입력받아 켜져 있는 비트는 끄고, 꺼져 있는 비트는 켠 결과를 반환합니다. 이 연산은 short (16bit 정수형)과 unsigned short (부호없는 16bit 정수형)의 결과가 다릅니다.

  (unsigned short) ~12 = 2^16 - 1 - 4 - 8 = 65523 // unsigned short(부호없는 16bit 정수형)
  ~12 = -13 // short(16bit 정수형)
  ~(0000 0000 0000 1100) = 1111 11111 111 0011 
  

• Shift 연산(>> <<) 예를 들어 우측 쉬프트 연산(>>)은 좌측의 정수를 우측에 입력한 정수 만큼 bit 를 이동시킵니다. 좌측에 빈공간은 0 으로 채웁니다.

  13(1101) >> 2 = 3(0011) // 12 를 우측으로 2만큼 비트 이동하였습니다.
  

비트마스크를 사용한 집합 표현 예시

크기가 20인 boolean 동적 배열을 비트마스크로 표현하여 int(32bit) 정수 1개로 표현하는 예로 다루어보겠습니다.

vector<bool> arr = { true, false, false, ....  true, true }; // 총 20개 

공집합(전부 false)

상수 0 은 공집합을 표현합니다. vector 의 원소들이 전부 false 인 경우입니다.

vector<bool> arr = { false, false, false, .... , false }; //전부 false  

int null_set = 0;
0000 0000 0000 0000 0000 0000 0000 0000 // 32bit 0 의 이진수 표현
// 뒤에 20bit 만 집합을 표현하는데 사용되고 12개 bit 사용않습니다. 

꽉찬 집합(전부 true)

vector 의 원소 20개가 전부 true 인 경우 입니다.

vector<bool> arr = { true, true, true, ....  true, true }; // 전부 true 

int full_set = (1 << 20) - 1; // 쉬프트 연산후 1뒤에 0이 20개인데 여기서 1을 제거 하였습니다. 
0000 0000 0000 1111 1111 1111 1111 1111 // full_set 의 이진수 표현

원소 추가(특정 원소를 true로 전환)

크기가 20인 배열의 원소의 번호는 0<= p < 20 (반열린구간) 의 범위에 있습니다.

set |= (1 << p); // set 집합에서 p 번째 원소를 true 로 바꿉니다. 

전부 false 인 집합에 세번째 원소만 true 로 바꾸는 예시입니다.

int set = 0; // 공집합
set |= (1 << 2); // 1을 2 좌측 shif 하면 이진수 100 이고, 0과 or 연산하면 그대로 이진수 100이된다. 
0000 0000 0000 0000 0000 0000 0000 0100 // set의 이진수 표현 (4)

처음에 set 0 이외의 어떠한 수가 되도 상관없습니다. p 를 2로 준 이유는 index 가 0부터 시작이기 때문입니다.

원소 포함 여부 확인(특정 원소가 true인지 확인)

set & (1 << p)) // 이 값이 0이 아니면 p번째 원소는 true입니다.

위에서 추가한 원소가 포함되었는지 확인해보겠습니다.

int set = 4; // 세번째 원소만 true인 집합
set & (1 << 2)) = 4 // p 가 2가 아닌 경우는 전부 0이 나옵니다. 

아래는 부호없는 64비트 정수형(unsigned long long) 비트 마스크 a 의 b 번 비트가 켜져있는지 확인 함수입니다.

bool isBitSet(unsigned long long set, int p){
  return (set & (1ull << p)) > 0; // 1뒤에 ull 점미사를 붙혀서 이 상수가 부호 없는 64비트 정수라는 것을 표현하였습니다.
  // 접미사를 생략하는 경우 32bit 가 넘어가는 경우 오류가 생긴다고합니다. 
}

c++ 에서 N 비트 정수를 N 비트 이상 왼쪽으로 시프트 하는 경우 오류를 볼 수 있습니다. 얼핏 생각하면 이와 같은 연산의 결과로 는 0이 나와야 할것 같지만 c++ 언어 명세에는 이 결과가 정의되어 있지 않으므로 이런 코드는 환경에 따라 다른 결과를 낼 수 있습니다.

원소의 삭제(특정 원소를 false로 전환)

set -= (1 << p) // 원래 원소가 true일 때무나 결과가 정상입니다... 사용 X
set &= ~(1 << p) 

c++의 ~(NOT) 연산자는 비트별 not 연산을 수행하므로, ~(1<

원소의 토글(특정 원소를 false이면 true 로 true이면 false 로 변환)

해당 비트가 켜져있으면 끄고, 꺼져 있으면 켜는 것입니다. 이때 XOR 연산을 사용합니다. (비트별 XOR 연산은 두 비트가 서로 다른 경우만 결과 비트를 켭니다.)

set ^= (1 << p)

두 집합 연산

int added = (set1 | set2);  // set1와 set2의 합집합입니다.
int intersection = (set1 & set2);  // set1와 set2의 교집합입니다.
int removed = (set1 & ~set2); // set1 집합에서 set2의 원소들을 뺀 차집합입니다.
int toggled = (set1 ^ set2); // set1과 set2 중에 하나에만 포함된 원소들의 집합입니다. 

집합의 크기(true 의 갯수)

int bitCount(int x){
  if(x == 0) return 0;
  return x % 2 + bitCount(x/2); // 2로 나누는 것은 >> 1(우측 쉬프트 1) 하는것과 같습니다. 
}

재귀 호출을 통해서 켜져있는 bit 의 수를 계산합니다. 이것은 여러 컴파일러에서 내장 함수로 제공합니다.

__builtin_popcount(set) // gcc,g++
__popcnt(set) // visual c++
Integer.bitCount(set)// java

위 함수들은 다양한 최적화를 이용해 구현되어서 매우 빠릅니다.

최소 원소 찾기(값이 true 가장 작은 번호 찾기)

여러 컴파일러가 제공하는 내장 함수입니다.

__builtin_ctz(set) // gcc,g++
_BitScanForward(&index,set) // visual c++
Integer.numberOfTrainingZeros(set)// java

_builtinctz() 의 경우 입력으로 0이 주어졌을 때의 결과가 정의되어 있지 않으므로 주의합니다.

가장 작은 번호 대신에 해당 해당 값을 바로 구하는 방법은 아래와 같습니다. 최소 원소만 들어 있는 집합을 바로 구하는 것입니다.

int min_set = (set & -set); // (set & (~set + 1)) 과 같습니다. 

2의 보수를 사용하는 시스템에서는 음수 -a 를 표현하기 위해서 a에 비트별 연산을 적용하고 그 결과에 1을 더합니다.

최소원소 지우기

set &= (set - 1); // set-1 의 이진수 표현은 set에서 켜져있는 최하위 비트를 끄고 밑에 비트들을 전부 켠 것입니다.

이 방법은 어떤 정수가 2의 거듭제곱 값인지 확인할 때도 유용하게 쓰입니다. 2의 거듭제곱 값들의 이진수 표현에는 켜진 비트가 하나밖에 없기 때문입니다. 최하위 비트를 지웠을 때 0이 된다면 주어진 수는 2의 거듭제곱 수입니다.

모든 부분 집합 순회

for (int subset = set; subset ; subset = ((subset-1) & set) )
{
    // subset은 set의 부분 집합입니다.
}

(set-1) 과 set 의 교집합(비트별 AND 연산)을 구하면 그 중 set에 속하지 않는 비트들은 모두 꺼지게 됩니다. for문은 subset=0인 시점에서 종료하므로 공집합은 방문하지 않는다는 점을 깜박하지 않도록 합시다. 만약 vector<bool> 을 사용했다면 재귀 호출을 사용해야 하지만 비트마스크를 사용하여서 훨씬 간단해졌습니다.

연산자 우선순위

아래는 비트마스크 기법에서 자주는 사용하는 연산자들의 우선순위입니다. 다른 연산자들도 더 있지만 그것들은 우선순위를 헷갈리는 경우가 많이 없어 생략하겠습니다.

1. 단항연산자 : ~(비트별 not 연산자)

2. 산술연산자 : * / % + -

3. shift 연산자 : <<(좌측으로 bit 이동) >>(우측으로 bit 이동)

4. 관계 연산자 : > < <= >= == !=

5. bit 연산자 : &(비트별 and) ^(비트별 xor) |(비트별 or)

6. 논리 연산자 : &&(and) ||(or)

   이러한 연산자들을 같이 사용할 경우 괄호를 사용해주는 것이 좋습니다.

int c = (6 & 4 == 4); // c는 0
int d = ((6 & 4) == 4); // d는 1

장점

1. 빠른 수행시간 - 물론 비트마스크를 사용할 수 있다는 말은 원소의 수가 많지 않다는 뜻입니다.

2. 간결한 코드

3. 작은 메모리 사용

4. 연관배열을 배열로 대체 - 다음과 같이 boolean값 배열을 key 로 사용하는 경우가 있습니다.

   map<vector<bool>, int> 
   

   이때 비트 마스크를 써서 같은 정보를 정수 변수로 나타내면 단순한 배열 int[]을 사용해 같은 정보를 나타낼수 있습니다.

표준 라이브러리

비트 집합을 구현한 표준 라이브러리로 c++ 의 bitset, java의 java.util.BitSet 등이 있습니다. 이 클래스들는 정수형을 비트마스크로 사용하는 것보다 가독성 면에서 좋습니다. 하지만 일부 trick 을 사용할수 없으므로 적절히 선택하여 사용하도록 합니다.

참고 문서 - visual algo

참고서적 - 알고리즘 문제해결 전략(구종만)