4.bit-masking

Bit-masking

이진수

비트마스킹을 이해하기 위해서는 이진수를 알아야 한다.

평소에 사용하는 수는 0~9를 기반으로 수를 표현하는 십진법이다.

123이라는 숫자는 $310^0 +210^1+1*10^2$이고 각 자리는 0~9로 10개의 숫자로 표현된다.

그렇다면 이진수는 0과 1, 두 개의 숫자로 표현하는 이진법으로 표현된다.

이진수는 오른쪽 끝에서부터 각 자리는 1부터 2가 곱해지며 2배씩 증가하면서 수를 표현한다.

이때, 각각의 자리는 비트라고 할 수 있으며, 0인지 1인지를 기반으로 수를 표현한다.

Boolean 배열

이진수를 통해 Boolean 배열을 표현할 수 있다.

0번째 비트가 켜져있는 경우 001로 표현되고 이는 1이 될 수 있다. 또한 0, 1번째 비트가 켜져있는 경우 011로 표현되고 이는 3이 될 수 있다. 즉, 이진수를 이용해서 하나의 숫자를 기반으로 Boolean 배열을 표현할 수 있다.

비트연산자 활용법

종류	코드
idx번째 비트 끄기	S &= ~(1 << idx)
idx번째 비트 XOR 연산	S ^= (1 << idx)
최하위 켜져있는 비트 찾기	idx = (S & ~S)
크기가 n인 집합의 모든 비트 켜기	(1 << n) - 1
idx번째 비트 켜기	S | = (1 << idx)
idx번째 비트가 켜져 있는지 확인하기	if (S & (1 << idx))

비트마스킹을 이용한 경우의 수

비트마스킹을 통해 경우의 수를 표현할 수 있다.

예를 들어 {A, B, C, D}의 모든 경우의 수는 {A}, {A, B}, … 등으로 총 16가지의 수가 된다.

const int n = 4;
string a[n] = {"A", "B", "C", "D"};

for (int i = 0; i < (1 << n); i++) {
	string ret = "";
	for (int j = 0; j < n; j++) {
		if (i & (1 << j)) {
			ret += (a[j] + " ");
		}
		cout << ret << '\n';
	}
}

위의 코드에서와 같이 모든 집합을 표현할 수 있다.

i는 0000, 0001, 0010을 의미하고, j는 이러한 0, 1, 2, 3을 기반으로 (1 << 0), (1 << 1) 등으로 해당 번째의 비트가 켜져있는지를 통해 집합을 확인한다. 이를 통해 모든 경우의 수를 한번의 for문을 통해 표현이 가능하다.

비트마스킹을 이용한 매개변수 전달

const int n = 4;
string a[n] = {"A", "B", "C", "D"};

void go(int num) {
	string ret = "";
	for (int i = 0; i < 4; i++) {
		if (num & (1 << i)) ret += a[i] + " ";
	}
	cout << ret << '\n';
}

int main() {
	for (int i = 1; i < n; i++) {
		go(1 | (1 << i));
	}
	return 0;
}

이를 통해 A에 대하여 A + B, A + C와 같이 매개변수를 더하는 코드를 구현할 수 있다.

이러한 비트마스킹의 한계는 31개의 경우의 수까지 가능하다. 즉, int형의 범위를 넘어가는 경우 해당 경우의 수를 센다는 것 자체가 시간복잡도를 초과할 가능성이 존재하기 때문이다.