[코딩 테스트 준비 - 기초] 7. 비트마스크(Bitmask)

1. 비트 연산

NOT, AND, OR, XOR

A	B	~A	A & B	A | B	A ^ B
0	0	1	0	0	0
0	1	1	0	1	1
1	0	0	0	1	1
1	1	0	1	1	0

 

not 연산의 경우 자료형에 따라 결과가 달라지는 것을 주의해야 한다.

특히, unsigned와 signed에 따라서 정수로 보여지는 값이 달라진다. (2의 보수 때문)

 

Shift Left, Shift Right

• A << B
  • A를 B비트만큼 왼쪽으로 밀기
  • A x (2^B)
  • ex. 3 << 4 = 3 x 2^4 = 3 x 16 = 48
• A >> B
  • A를 B비트만큼 오른쪽으로 밀기
  • A / (2^B)
  • ex. 2 >> 4 = 2 / 2^4 = 2 / 16 = 1 / 8

 

2. 비트마스크

개요

비트마스크는 비트 연산을 이용해 부분집합을 표현하는 것이다.

• 비트마스크를 통해 집합을 정수로 나타낼 수 있다.
• 단, 이때 집합에 저장할 수 있는 수의 범위가 정해져 있어야 한다.
• 따라서 보통 0부터 N-1까지 N개의 정수로 이루어진 집합을 나태낼 때 사용한다. 

ex) N = 10일때, s = {1, 3, 4, 5, 9}라는 집합에서 각 수의 존재여부를 나타내면 다음과 같다.

9	8	7	6	5	4	3	2	1	0
1	0	0	0	1	1	1	0	1	0

이를 정수로 나타내면, 1000111010(2) = 570와 같다.

 

비트마스크의 장점

1. 공간을 적게 사용할 수 있다.

• 위 예시에서 집합 s를 표현하는 데에는 1, 3, 4, 5, 9라는 5개의 정수가 필요하지만,
• 비트마스크를 통해 표현하면 570 단 하나의 정수만 사용한다.

2. 연산의 시간복잡도가 O(1)로 빠르다. 아래서 살펴보자.

 

cf) 비트마스크가 정수라는 것

이는 장점이 될 수도, 단점이 될 수도 있다.

장: 리스트나 배열로 표현할 때 정수는 간편하다.

단: 정수는 32bits 혹은 64bits로 범위에 제한이 있어, 수의 범위가 너무 크면 사용할 수 없다.

 -> C++의 경우 이러한 단점을 보완하기 위해 bitset이라는 것을 제공한다. (but, 사용할 일 별로 없다고 함)

 

비트마스크의 연산

집합 S에대해 수 X를 검사, 추가, 삭제, 토글하는 방법

cf) 연산을 수행할 때 연산자 우선 순위 때문에 걱정되면 괄호를 사용하자!

 

1. S에 X가 있는지 검사

= S의 X번째 비트가 1인지 0인지 검사

= X번째 비트만 1로 두고 AND 연산 수행

= S & (1 << X)

 

2. S에 X를 추가

= S의 X번째 비트를 1로 변경

= X번째 비트만 1로 두고 OR 연산 수행

= S | (1 << X)

 

3. S에서 X를 삭제

= S의 X번째 비트를 0으로 변경

= X번째 비트만 0으로 두고 AND 연산 수행

= S & ~(1 << X)

 

4. S에서 X를 토글

= S의 X번째 비트가 0이면 1로, 1이면 0으로 변경

= X번째 비트만 1로 두고 XOR 연산 수행

= S ^ (1 << X)

 

결론

• 그냥 배열을 사용하는 것이 편리하지만, 비트마스크를 사용하는 이유는 집합을 배열의 인덱스로 표현할 수 있기 때문이다.
• 상태 다이나믹을 할 때 자주 사용하게 된다.
• 적은 갯수를 저장하는 집합에서 사용하는 것이 적합하다.

 

 

3. 문제를 통해 알아보기

[백준 11723 집합]

• 비트마스크로 풀기 위해서는 0부터 19까지로 생각해야 한다. (즉, x를 -1해서 계산해야 함)
• all과 empty는 x를 입력받지 않는다!! (당연한건데 이것 때문에 1시간 날림..)
• c++로 구현할 경우 입력이 너무 많아서 빠른 입출력을 해줘야 한다.

#include <iostream>
using namespace std;

int n = 20;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int m;
	cin>>m;

	int s = 0; //공집합
	string cmd;
	while(m--){
		cin>>cmd;

		int x;
		if(cmd == "add"){
			cin>>x;
			x--;
			s = (s | (1 << x));
		} else if(cmd == "remove"){
			cin>>x;
			x--;
			s = (s & ~(1 << x));
		} else if(cmd == "check"){
			cin>>x;
			x--;
			int check = (s & (1 << x));
			cout<<(check ? 1 : 0)<<'\n';
		} else if(cmd == "toggle"){
			cin>>x;
			x--;
			s = (s ^ (1 << x));
		} else if(cmd == "all"){
			s = (1 << n) - 1;
		} else{ //empty
			s = 0;
		}
	}

	return 0;
}

 

[백준 1182 부분수열의 합]

• 가능한 모든 부분수열을 만들어 확인한다.
• 수열의 위치(인덱스)를 기준으로, 특정 위치의 값이 부분수열에 포함되는지 아닌지 확인하면 된다
• 즉, 특정 값의 부분수열 포함 여부를 판단하는 것은 0과 1로 충분하므로 비트마스크를 이용할 수 있다. 
• 0부터 n-1까지의 수를 이진수로 표현하면, 배열의 각 위치에 0 또는 1이 들어가게 된다.
  • ex) n = 5일때, 0 = 00000, 1 = 00001, 10 = 01010, 31 = 111111
• 즉, 공집합을 제외하고 1부터 전체집합까지 비트마스크 i로 표현하고
• i에 j가 들어있는지 검사(i를 이진수로 봤을 때 j번째가 0인지 1인지)한다.

#include <iostream>
using namespace std;

int main(){
	int n, s;
	cin>>n>>s;

	int arr[n];
	for(int i=0; i<n; i++) cin>>arr[i];

	int bs = (1<<n) - 1;
	int ans = 0;

	for(int i=1; i<=bs; i++){
		int sum = 0;
		for(int j=0; j<n; j++){
			//비트마스크 i에 j가 들어있는지 check
			int check = (i&(1<<j));
			if(check) sum += arr[j];
		}
		if(sum == s) ans++;
	}

	cout<<ans<<'\n';
	return 0;
}