비트마스킹 기법 구현

정의

비트마스크(BitMask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법.
이진수는 0 또는 1을 이용하므로 하나의 비트(bit)가 표현할 수 있는 경우는 두 가지이다.

 

문제

비트마스킹 기법을 C++로 구현하거나 혹은 아래와 같이 구현된 코드를 해석해서 정리해주세요.

 

코드

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

int main()
{
	vector<int> arr = { 1, 2, 3 };
	int n = arr.size();

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

		cout << "}\n";
	}

	return 0;
}

 

풀이

int n은 벡터의 크기를 저장해둔 것이다.

for문을 돌릴때, 0부터 시작하며 n의 시프트 연산만큼 순회한다. 왜 시프트 연산을 사용하는가에 대해 생각해보았다. 시프트 연산은 비트를 이동시키는 연산이다. 즉 1 << n은 n만큼 왼쪽으로 이동하라는 것이다. 여기서 n은 arr의 사이즈. 즉 3이기에 1의 비트를 3번 왼쪽 이동한 것이다.

 

그래서 1의 비트를 3번 왼쪽 이동한게 무슨 값인데?! -> 2의 제곱을 곱해준다.

이게 무슨 소리지??하고 찾아보니 시프트 연산자의 비트를 이동한 값을 구하는것이 1 << 3이면 1 x (2x2x2)라는 의미 같다. 그래서 값은 8이다.

근데 왜 1 << 3로 계산해야되는거지?는 앞에 부분 집합을 전부 순회하는 전형적인 방법 중 하나가 bitmasking이다.

 

그 뒤로 배열의 크기만큼 순회하면서, i와 (1 << j)는 i의 j번째 비트가 1인지 확인하는 연산이다.

두 수가 둘 다 1인 경우에 arr의 j 값을 출력한다.