비트 마스킹

비트 마스킹이란 0과 1을 이용해서 연산하는 방식을 말한다.

이 방식을 통해서 효율적인 연산이 가능할 때가 있다.

 

많이 안 써본 방식이기 때문에 관련 수업을 들은 후 내용을 정리하게 되었다.

추가적으로 아래 글을 참고해서 정리해 보았다.

https://blog.encrypted.gg/1093

[실전 알고리즘] 부록 C - 비트마스킹

 

 

1. 비트 연산자

---

• 0은 false 1은 true를 뜻한다.
• AND (둘다 참인 경우 참)
  • 0 & 0 = 0
  • 0 & 1 = 0
  • 1 & 1 = 1
• OR (둘중 하나만 참이어도 참)
  • 0 | 0 = 0
  • 0 | 1 = 1
  • 1 | 1 = 1
• XOR (두 비트가 다르면 참)
  • 0^0 = 0
  • 0^1 = 1
  • 1^1 = 0
• NOT (비트 반전)
  • ~0 = 1
  • ~1 = 0 
• shift
  • 자릿수를 하나씩 밀어주는 연산
  • overflow를 주의해야 하므로, shift 연산은 양의 정수에서만 연산이 이루어질 수 있도록 주의하기

예시) 

• 9 & 14
  • 9      =   0000 1001
  • 14    =   0000 1110
  • 결과 =   0000 1000 (8)
• 11 | 34
  • 11    = 0000 1011
  • 34    = 0010 0010
  • 결과 = 0010 1011 (43)
• signed 자료형에서 
  • ~x = -x - 1
    • ~x + x = 모든 비트가 1
    • signed 자료형에서 1111 1111 은 -1이다.
  • 16   =  0001 0000
  • ~16 =  1110 1111

 

 

2. 비트마스킹

---

비트마스킹은 빅 오의 관점에서 시간복잡도를 줄여주는 방식은 아니다.

그러나 실제 속도나 메모리에서 이득을 볼 수 있다.

 

먼저 부분집합을 구하는 코드를 통해 어떻게 사용하는지 확인할 수 있다.

 

기본적으로 n개를 뽑아내는 문제에 있어서는 back tracking을 사용할 수 있다.

또한 비트마스킹을 사용할 수도 있는데, 아래 bitmasking 함수에서 확인할 수 있다.

 

해당 코드를 설명하자면,

• 가장 바깥의 for문은 총 부분집합의 개수만큼 순환하는 for문이다.
  • 우리가 가진 배열이 크기가 4이므로
  • 각 자리수마다 1 혹은 0 이 올 수 있으므로 2^4을 뜻한다.
  • 2^4은 비트 연산자로 1 << 4로 표현할 수 있다.
  • 1 << 4의 의미는 0000 0001을 4칸 왼쪽으로 시프트 시킨다는 의미이므로
  • 0001 0000이 되어 결론적으로 16이 된다.
• 안쪽에 for문은 우리가 선택할 부분집합의 원소의 갯수만큼 순환하게 된다.
  • 예를 들어 설명하면, 0000 0011 라는 i가 있을 때
  • j는 0, 1, 2,3 이 될 수 있다.
  • 이때 if문에서 i와 (1 << j ) 의 AND 연산을 진행하게 된다.
  • 그러면 (1 << j )는 각각 0000 0001, 0000 0010, 0000 0100, 0000 1000 이 된다.
  • 결과적으로, i값인 0000 0011과 위에서 말한 4개의 값과 비트연산을 한다면
  • 0000 0001과 0000 0010 과 연산에 있어서 참이 되므로 
  • vec[j] 값으로 0과 1을 출력하게 된다. (vec에서 인덱스가 0번째 1번째인 값)
• 정리
  • 1 << j 의 의미는 j번째 수가 1인 수를 나타낸다.
  • i & (1 << j) 의 의미는 i의 j번째 비트가 1인지를 확인하는 코드이다.

#include <iostream>
#include <vector>
using namespace std;

int isused[4];
int n = 4;
vector<int> vec = { 0,1,2,3 };

void backtracking(int cur)
{
	if (cur == n)
	{
		for (int i = 0; i < 4; ++i)
		{
			if (isused[i])
				cout << i << " ";
		}
		cout << "\n";
		return;
	}
	//cur 를 선택하지 않은 경우
	backtracking(cur + 1);

	//cur 를 선택하는 경우
	isused[cur] = 1;
	backtracking(cur + 1);
	isused[cur] = 0;
}

void bitmasking()
{
	for (int i = 0; i < (1 << n); ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if (i & (1 << j))
				cout << vec[j] << " ";
		}
		cout << "\n";
	}
}

int main()
{
	backtracking(0);
	cout << "\n\n";
	bitmasking();
}

 

 

3. 실전 문제

---

백준 1497번 기타 콘서트 문제입니다.

https://www.acmicpc.net/problem/1497

 

내가 푼 방식

• 모든 경우의 수를 구할 때만 비트마스킹 기법을 사용

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int n, m;
vector<pair<string, string>> vec;
char check[52]; //NNNNN
vector<pair<int, int>> result;

void bitmasking()
{
	int answer = INT_MAX;
	int cnt = 0;

	for (int i = 0; i < (1 << vec.size()); ++i)
	{
		fill(check, check + m, 'N');
		cnt = 0;

		for (int j = 0; j < vec.size(); ++j)
		{
			//모든 경우의 수
			if (i & (1 << j))
			{				
				for (int k = 0; k < vec[j].second.size(); ++k)
				{
					//check 배열 바꿔주고
					if(check[k] == 'N')
						check[k] = vec[j].second[k];					
				}				
				//기타 갯수 추가
				cnt++;
			}
		}

		//Y의 갯수
		int cntY = 0;
		for (int k = 0; k < m; ++k)
		{
			if (check[k] == 'Y')
			{
				cntY++;
			}
		}
		result.push_back({ cntY, cnt });
	}

	sort(result.begin(), result.end());
	int maxY = result.back().first;

	for (auto r : result)
	{
		if (r.first == maxY)
			answer = min(answer, r.second);
	}
	
	if (answer == 0)
		cout << -1;
	else
		cout << answer;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		string name, song;
		cin >> name >> song;

		vec.push_back({ name, song });
	}
	
	bitmasking();
}

 

추가 설명) 이 문제의 비트마스킹 풀이 정해

• state라는 비트를 저장하는 배열 존재
  • 해당 배열은 연주할 수 있는 곡에 대한 정보를 | 연산을 통해서 저장한다.
  • 'Y'와의 | 연산이므로 Y인 경우 값을 업데이트 한다.
  • 예를 들어 temp가 YYYNN 인 경우
    • m-1부터 시작이므로 j = m - 1, m - 2 일때는 state[i] = 0
    • j = m - 3 일때, state[i] = 1
    • j = m - 4 일때, state[i] = 1 + 2
    • j = m - 5( = 0) 일때, state[i] = 1 + 2 + 4 
    • 이런식으로 업데이트하게 된다.
• 이후 pair라는 곡과 기타 수를 저장할 배열을 가지고, 위에서 구한 state를 통해 모든 조합 결과를 체크하게 된다.
  • 이 부분은 내가 작성한 코드에서 비트마스킹을 이용한 부분의 내용과 같다.
  • 다른 점은 if(tmp & (1LL << i)) 을 만족한 값에 대해서
    • 내 풀이는 저장해 둔 string값을 돌면서 Y의 갯수를 측정했지만
    • 정해에서는 | 연산을 통해 Y값이 많아지는 방향으로 업데이트 하였다.
      • 이 말뜻은 |은 둘 중 하나만 참이어도 참이 되기 때문에 참이 많아지는 방향이 된다는 뜻이다.
      • 예를들어 YYNNN 과  YYYNY이 만나면 YYYNY가 된다.
• 마지막 처리는 comb값을 통해 곡의 수를 업데이트 해주고, tmp값을 통해 guitar 값을 업데이트 해주었다.
  • bitcount라는 함수를 통해서 해당 수가 가진 1의 갯수를 측정해준다.
  • tmp 가 guitar의 갯수를 나타내는 것의 의미는
    • tmp가 3이라면 비트로 0000 0011이므로, 여기서 1의 위치는 각각 0번째 1번째 기타를 뜻하고
    • 1의 갯수를 세는 것은 guitar의 갯수를 세는 것과 같은 의미이다.

코드

#include <iostream>
using namespace std;

int n, m;
long long state[10];

//x가 가지는 1의 갯수를 반환하는 함수
int bitcount(long long x)
{
	int ret = 0;
	for (int i = 0; i < m; ++i)
	{
		ret += (x >> i) & 1;	
	}
	return ret;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		string name, temp;
		cin >> name >> temp;

		for (int j = m - 1; j >= 0; --j)
		{
			state[i] = (state[i] << 1) | (temp[j] == 'Y');
		}
	}

	pair<int, int> ans = { 0, -1 };//곡의 수, 기타 수
	for (int tmp = 0; tmp < (1 << n); ++tmp)
	{
		long long comb = 0; //조합 결과
		for (int i = 0; i < m; ++i)
		{
			if (!(tmp & (1LL << i)))
				continue;
			comb |= state[i];
		}

		int song = bitcount(comb);
		int guitar = bitcount(tmp);

		//곡의 수가 더 많은 경우
		if (ans.first < song)
			ans = { song, guitar };
		//곡의 수는 같은데 기타가 적은 경우
		else if (ans.first == song && ans.second > guitar)
			ans = { song, guitar };
	}
	cout << ans.second;
}