비트 마스크(Bit Mask) - 활용(부분집합)

 지난 번에 이어서 마저 작성하려고 한다.

 

 비트 연산을 통해 다양한 연산을 빠르게 실행할 수 있는데,

 

부분집합을 찾는 것도 그 중 하나이다. 

 

0에서 3까지 4개의 요소가 들어가 있는 집합에서 모든 부분 집합을 뽑아낼 수 있는 경우를 비트 마스킹을 통해 찾아보자.

 

우선 코드는 다음과 같다.

 

#include <iostream>
using namespace std;


int main() {
	int n = 4;
	char arr[4] = { 'a','b','c','d' };
	

	for (int i = 0; i < (1 << n); i++) {
		for (int j = 0; j < n; j++) {
			if ((i&(1 << j)) != 0)
				cout <<j << " ";
		}
		cout << endl;
	}
	for (int i = 0; i < (1 << 4); i++) {
		for (int j = 0; j < 4; j++) {
			if ((i&(1 << j)) != 0)
				cout << arr[j] << " ";
		}
		cout << endl;
	}

	



}

 

해당 코드의 실행 결과는 다음과 같다.

 

 전체 요소들의 부분집합을 모두 확인할 수 있다.

 

이는 비트 연산을 통해 도출해 낸 것인데 간단하게 알아보자.

 

우선 int i는 부분집합에 들어갈 수 있는 수의 제한이라고 생각하자.

 

i는 최대 (1<<n)-1 까지 값을 가질 수 있다.

 

여기서 n은 4이기 때문에 i의 최댓값은 10000 -1이다 .

 

즉 i는 1111이라는 값까지 가질 수 있다. 이를 10진수로 나타내면 15이다.

 

여기서는 10진수가 중요한 건 아니니 넘어가고.

 

처음 i에게 주어지는 수는 0, 

 

그리고 다음으로 주어지는 for문은 j인데 j는 n-1 까지 커진다.

 

즉, j의 값 범위는 0~3

 

i는 0~15의 범위를 가지는데 왜 j는 0~3의 범위를 가질까??

 

그 이유는 i는 그 값 그대로 비교를 한다면,

 

j는 1을 시프트하는데 필요한 인자가 된다.

 

즉 j의 범위만큼 1을 왼쪽으로 시프트해서 해당 값을 추출하는 것이다.

 

여기서 이중for문을 돌리는 이유를 알 수 있다.

 

i가 0일 때,

 

j for문에서 비교하는 것은 j가 0~3 범위에서 가지는 값 

 

0 0 0 1, 0 0 1 0, 0 1 0 0, 1 0 0 0 

 

i는 0 0 0 0 이기 때문에 & 연산을 해도 동시에 1을 가지는 위치가 없어서 출력되지 않는다.

 

그렇다면 i가 1이라면?

 

0 0 0 1의 값이 출력될 것이다. 여기서 0 0 0 1 은 j가 0일 때를 말한다. 1을 왼쪽으로 0회 시프트하면 0 0 0 1이기 때문

 

i가 2라면 0 0 1 0 이기 때문에 0 0 1 0의 값이 출력될 것이다. j는 1이다. 

 

하지만 여기는 &연산이기 때문에 j가 0일 때는 출력되지 않는다.

 

i가 3이라면 0 0 1 1 이기 때문에 j for문 0~3 범위 중 0이 출력되고 바로 다음으로 1이 출력된다.

 

이와 동일하게 i가 1 1 1 1인 15까지 가는 동안 반복하면

 

위와 같은 출력값이 나온다.

 

문자열 배열도 마찬가지로 출력할 수 있다.

 

비트 마스킹을 통해 빠르게 부분집합 연산을 끝낼 수 있는 것이다. 

 

라고 이해했다.