비트마스크 (Bitmask)

비트마스크

정수의 이진수 표현(Bit)을 자료 구조로 쓰는 기법

현대의 모든 CPU는 이진수를 이용해도 모든 자fy 표현

내부적으로 이진수를 사용하는 컴퓨터들은 이진법 관련 연산들을 아주 빨리 할 수 있다.

- 더 빠른 수행 시간

  비트마스크를 활용하는 것이 원소의 수가 많지 않겠지만, 큰 속도 향상이 없을 수는 있다.

  하지만 연산을 여러 번 수행할 때는 괴장히 효율적이다.

 

- 더 작은 공간 복잡도(메모리)

 

- 비트 연산자를 활용한 가독성(간결한 코드)

  다양한 집합 연산들을 반복문 없이 사용

 

ex) 8개의 비트를 사용할 때, 아래와 같이 표현.

※ [BOJ] 11723 집합

arr[8] = {1, 2, 4, 8, 16, 32, 64, 128} 

arr[i] = 1 << i

이진수는 십진수 표현도 가능하며 0,1 / true, false 등으로 표현할 수 있다.

 

ex) arr = 에서 원소를 선택하는 경우의 수

아래와 같이 별도 배열로 표시

int a[] = {0, 1, 2, 3, 4}

int a[] = {0, 1}

int a[] = {2, 3, 4}

 

비트마스크를 이용한 표시(+ 십진법)

{0, 1, 2, 3, 4} → 11111 → 31

{0, 1} → 11000 → 24

{2, 3, 4} → 00111 → 7

i 번째 비트 값 변경으로 원소 존재 유무를 쉽게 알 수 있습니다.

그리고 비트 연산은  AND(&) / OR( | ) / XOR( ^ ) / NOT( ~ ) SHIFT( <<, >> ) 등이 존재한다.

※ [BOJ] 12813 이진수 연산

 

NOT 연산의 경우 자료형에 따라 결과가 달라집니다.

ex)  A = 83 = 10100112

- 8비트 자료형의 경우 ~A = 101011002

- 32비트 자료형인 경우 ~A = 11111111 11111111 11111111 101011002

// AND

1010 & 1111 = 1010

// OR

1010 | 1111 = 1111

// XOR

1010 | 1111 = 0101

// NOT

~1010 = 0101

// SHIFT

00001010 << 2 = 101000

00001010 >> 2 = 000010

 

// 공집합 (모든 Bit가 0인 상태)

int empty = 0;

// 전체집합 (모든 Bit가 1인 상태)

int full = (1 << N) - 1;

 

SHIFT 연산의 경우 

- 왼쪽 시프트 → A × 2B

- 오른쪽 시프트 →  A / 2B

ex) (A + B) / 2 = (A + B) >> 2로 계산할 수도 있습니다.

 

주의사항

- 연산자 우선순위가 낮기 때문에 괄호 쳐주는 습관을 가지는 것이 좋습니다.

    ex) int c = ( 6 & 4  == 4); 의 경우 4 == 4가 먼저 계산된다.

          → ( (6 & 4)  == 4);

    

- 1은 부호있는 32bit 상수로 취급합니다. 때문이 32bit 를 넘어가는 수표현에서는 오류가 날 수 있습니다.

- 부호 있는 정수형에서 최상위 비트가 켜진 숫자는 음수를 표현합니다.

- 같이 보면 좋은 내용 ▶ [C++] [STL] bitset

[C++] [STL] bitset

 

다양한 예시

원소 추가

원소를 추가한다는 것은, 해당 비트를 켜는 것입니다.

sample bit에서 p번째 bit 켜기

{sample bit} | (1 << p)

 

ex) 0010일 때, 1번째 비트 값을 1로 변경해보기

0010 | (1 << 3)

0010 | 1000 = 1010

 

원소의 포함 여부 확인

{sample bit} & (1 << p) > 0

ex) 1011 & 0100 = 0000

ex) 0010 & 0010 = 0010 > 0

ex) if ({sample bit} & (1 << p)) cout << "There is 'p'th element" << endl;

　

원소 변경

{samplebit} &= ~(1 << p);

ex) 0010일 때, 3번째 비트 값을 0으로 변경해보기

0010 & ~ 1 << 1  

0010 & 1101 = 0000

 

 

원소 찾기

ex) 첫번째 원소를 찾아봅시다.

      컴퓨터가 음수를 표현하기 위해 2의 보수를 이용한다는 점을 이용합니다.

int firstbit = ({sample bit} & -{sample bit});

　

 

최소 원소 지우기

ex) 40(= 10010002)과 39(= 1001112)의 AND을 하면 32(=1000002)가 되어

      최하위 비트가 꺼진것을 알 수 있습니다.

amplebit &= ({sample bit} - 1);

　

 

원소 토글

해당 비트(p)가 켜져 있으면 끄고, 꺼져 있으면 킵니다.

samplebit ^= (1 << p);

　

 

모든 부분집합 순회하기

ex) 의 부분집합은 , , , , , , 입니다. (공집합 제외)

for (int subset = fullset; subset; subset = ((subset - 1) & fullset)) {

    cout << subset << endl;

}

 

 

집합의 크기 구하기

각 비트를 순회하면서 켜져 있는 비트의 수를 셉니다.(재귀 호출 방식)

int bitcount(int x){

    if (x == 0) return 0;

    return x % 2 + bitcount(x / 2);

}

　

Reference

★ [Jungol] 3293 비트연산 1 

- [BOJ] 11723 집합 

- [Jungol] 1274 2진수를 10진수로...  

- [BOJ] 3449 해밍 거리 

- [BOJ] 12813 이진수 연산 

- [BOJ] 11811 데스스타 

- [BOJ] 2098 외판원 순회 

- [Algospot] GRADUATION 졸업학기 

- [Jungol] 3292 집합관리 

- [BOJ] 13701 중복 제거