[알고리즘] 비트마스킹

이번 포스팅에서는 비트마스킹에 대해 다루겠습니다. 비트마스킹을 이해하려면 비트에 대한 기본적인 이해가 필요합니다. 따라서 비트연산, 이진수의 표현과 변환 방법, 부분집합에 대해 이해가 선행되어야 합니다.

일반적으로 C++의 <bitset>헤더에는 비트마스킹의 여러 기능을 지원합니다. 하지만 비트연산을 통해 직접 구현할 줄 알아야 합니다. 따라서 이번 포스팅에서는 직접 구현하고 원리를 알아보는 것을 위주로 다룹니다.

 

1. 개념

비트마스킹이란?

컴퓨터로 처리하는 모든 정보는 0과 1의 이진수로 이루어져 있습니다. 비트마스킹은 이진수의 비트 표현을 이용하여 자료구조(주로 집합)를 표현하는 기법입니다. 0은 해당 비트에 원소가 없음을, 1은 해당 비트에 원소가 있음을 나타냅니다.

예를 들어 10진수 14를 이진수로 변환하고 비트를 이용하여 집합을 표현해 보면 다음과 같습니다.

14 = 2³ + 2² + 2¹ = 1110(2)
→ 1 1 1 0

비트마스킹을 이용하면 위처럼 크기가 4인 { 1, 1, 1, 0 }집합을 int형 정수 14로 표현할 수 있습니다.

 

특징

• 수행 시간이 빠르다.
  비트연산은 이진수를 직접 다루기 때문에 대부분 O(1)로 처리할 수 있습니다.
• 코드가 간결하다.
  집합을 다룰 때에 복잡한 조건문, 반복문을 이용하는 것과 달리 비트연산 하나로 연산을 구현할 수 있습니다.
• 메모리를 최소한으로 사용할 수 있다.
  비트마스킹을 사용하는 주된 이유입니다. 예를 들어 50칸짜리 배열을 비트마스킹으로 구현하면 8Byte long long형 정수 하나로 표현할 수 있습니다.

따라서 비트마스킹을 이용하면 집합의 연산을 대부분O(1)에 처리할 수 있습니다. 예를 들어 백트래킹으로 구현했던 부분집합 나열 문제를 비트 연산으로 훨씬 빠르게 간결하게 구현할 수 있습니다. 아래에는 백트래킹을 이용한 부분집합 나열 코드입니다. 참고해 주세요.

백트래킹을 이용한 부분집합 나열

#include<iostream>

using namespace std;

bool check[4];

void backtracking(int k) {
	if (k == 4) {
		cout << "{";
		for (int i = 0; i < 4; i++) {
			if (check[i]) cout << i;
		}
		cout << "}\n";
		return;
	}
	//k번째 원소를 선택하지 않는 경우
	backtracking(k + 1);
	//k번째 원소를 선택하는 경우
	check[k] = true;
	backtracking(k + 1);
	check[k] = false;
}

int main(void) {

	backtracking(0);
	return 0;
}

 

 

2. 알고리즘 구현

크기가 n인 집합을 비트마스킹을 이용하여 구현해 보겠습니다. 

비트를 나타내는 변수 선언

//bitset이용시 bitset<n> state
int state = 0;

먼저 비트의 상태를 나타내는 변수를 선언합니다. 

 

집합을 모두 채우기(set)

//bitset이용시 state.set();
state = (1 << n) - 1;

state = 0xffffff;

전체 비트를 1로 초기화하는 연산입니다. 첫 번째 방법은 2의 보수 표현을 이용였고 두 번째 방법은 2진수로 직접 채워주었습니다. 2의 보수와 진수에 대한 자세한 설명은 접은 글로 작성했으니 궁금하면 읽어보세요.

첫 번째 방법에 대해 자세히 살펴보면, 1을 왼쪽으로 n칸 비트 이동 연산하여 n+1번째 칸은 1로 채우고 n ~ 1칸은 0으로 채워줍니다. 그 다음 1을 빼주면 2의 보수 표현법에 의해 상위 한칸은 0으로 나머지 칸들은 모두 1로 채워지게 됩니다. n = 5일 때 자세히 살펴봅시다.

1. (1 << n)의 결과 → 1 0 0 0 0 0
2. 위의 결과에서 -1을 한 결과 → 0 1 1 1 1 1

두 번째 방법에 대해 자세히 살펴보면, 0xffffffff은 16진수의 최댓값입니다. 따라서 state = 0xffffffff을 이용하면 간단하게 int의 최대값을 저장할 수 있습니다. 이를 이진수로 표현하면 0b1111111111111111111111111111111이고 10진수는 int형의 최댓값인 2,147,483,647입니다.

일반적으로 두 번째 방법이 한 번에 비트를 업데이트할 수 있어 첫 번째 방법보다 n배 빠르게 All연산을 수행할 수 있습니다. 이에 대해 더 자세하게 알고싶으면 2진수의 덧셈, 뺄셈, 2의 보수표현, 16진수, 2진수, 10진수의 표현과 변환 방법에 대해 자세히 알아보세요.

 

공집합 구하기(reset)

//bitset 이용시 state.reset();
state = 0;

모든 비트를 0으로 초기화하는 연산입니다. 상수 0은 어떤 진수이던 모든 bit가 꺼져 있음을 의미합니다. 따라서 statd을 0으로 만들면 됩니다.

 

원소 추가하기(add)

//bitset 이용시 state.set(n-1, 1);
state |= (1 << (n - 1));

Add연산은 1을 n번째 칸으로 비트이동시킨 뒤에 OR연산해주면 됩니다.

 

원소 제거하기(remove)

//bitset 이용시 state.set(n-1, 0);
state &= ~(1 << (n - 1));

Remove연산은 1을 n번째 칸으로 비트이동시킨 뒤에 NOT연산과 AND연산을 해주면 됩니다.

 

원소 확인하기(test)

//state.test(n-1);
cout << (bool)(state & (1 << (n-1))) << "\n";

cout << ((state >> (n - 1)) & 1) << "\n";

test연산은 두 가지 방법이 있습니다. 첫 번째 방법은 stat을 오른쪽으로 n-1칸 밀어서 비교하는 것이고, 두 번째 방법은 1을 왼쪽으로 n-1칸 밀어서 비교하는 것입니다. 하지만 첫 번째 방법은  AND연산하는 과정에서 해당 원소가 직접 반환되므로 강제 형변환을 해주어야 합니다. 따라서 보통 두 번째 방법을 사용하는 것이 좋습니다.

 

원소 전환하기(flip)

//bitset 이용시 state.flip(n-1);
state ^= (1 << (n - 1));

flip 연산은 1을 왼쪽으로 n-1칸 비트이동시킨 뒤에 XOR연산해주면 됩니다.

 

원소 개수 세기(count)

//bitset 이용시 state.count();
int bitCount(int x) {
	if (!x) return 0;
	return x % 2 + bitCount(x / 2);
}

count연산은 모든 비트를 순회하며 1의 개수를 세주면 됩니다. 위와 같이 간단하게 재귀함수로 구현할 수 있습니다.

 

최소 원소 찾기

int first = state & (-state);

가장 오른쪽 비트를 찾는 연산입니다. 2의 보수를 이용하면 간단하게 구현할 수 있습니다.

 

최소 원소 지우기

state & (state - 1);

state에서 1을 빼준 뒤에 AND연산하면 됩니다.

 

 

 

전체 코드

비트마스킹을 연습할 수 있는 간단한 문제가 있습니다. [백준 11723] 집합문제를 풀며 비트마스킹을 연습할 수 있습니다. 정답은 접은글로 작성했으니 참고해 주세요.

#include<iostream>
using namespace std;

int state;

int main(void) {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int m;
	cin >> m;
	while (m--) {
		string order;
		int x;
		cin >> order;
		if (order == "add") {
			cin >> x;
			state |= (1 << (x - 1));
		}
		else if (order == "remove") {
			cin >> x;
			state &= ~(1 << (x - 1));
		}
		else if (order == "check") {
			cin >> x;
			cout << (bool)(state & (1 << (x-1))) << "\n";
			//cout << ((state >> (x - 1)) & 1) << "\n";
		}
		else if (order == "toggle") {
			cin >> x;
			state ^= (1 << (x - 1));
		}
		else if (order == "all") {
			//state = 0xfffff
			state = (1 << 20) - 1;
		}
		else {
			state = 0;
		}
	}

}

 

 

#include<iostream>
using namespace std;

int a[4] = { 1, 3, 5, 7 };

int main(void) {
	for (int tmp = 0; tmp < 16; tmp++) {
		int brute = tmp;
		cout << "{";
		for (int i = 0; i < 4; i++) {
			if (brute % 2) cout << a[i];
			brute /= 2;
		}
		cout << "}\n";
	}
	return 0;
}

3. 연습 문제