비트마스크

 비트마스크 1<<k는 뒤에서 k번째 위치에만 비트 1이 있고, 나머지 위치에는 비트 0이 있는 정수이다. 이를 이용하여 정수의 특정한 비트 하나에 접근할 수 있다.

 예를 들어,  x & (1<<k)의 값을 확인하여, 정수 x의 k번째 비트가 0인지 1인지 확인할 수 있다.

 

- 활용 방법

// int형 정수 x의 비트 표현을 출력
for (int k = 31; k >= 0; k--) {
    cout << (x&(1<<k) ? "1" : "0");
}

// 정수 x의 뒤에서 k번째 비트를 1로 바꾸기
x|(1<<k)

// 정수 x의 뒤에서 k번째 비트를 0으로 바꾸기
x&~(1<<k)

// 정수 x의 뒤에서 k번째 비트를 뒤집기(toggle)
x^(1<<k)

// x의 가장 오른쪽의 비트 1을 0으로 바꾸기
x&(x-1)

// x의 가장 오른쪽의 비트 1만 남기고 나머지 비트를 모두 0으로 바꾸기
x&-x

 

 만약 양의 정수 x에 대해 x&(x-1)이 0이라면 x는 2의 거듭제곱임을 의미한다.

 비트마스크를 사용할 때 주의해야 할 점은 1<<k가 항상 정수형이라는 것이고, long long형 비트마스크를 사용하려면 1LL<<k를 사용해야 한다.

 

[ 집합 표현 ]

 집합 {0, 1, 2, ... , n-1}의 모든 부분집합을 n비트 정수로 표현할 수 있다.

 예를 들어, {0, 1, 2, ... 31}의 모든 부분집합을 32비트 정수로 표현할 수 있기 때문에, int형 정수로 표현할 수 있다.

 

 이 때, 정수의 비트 1은 그에 대응되는 원소가 부분집합에 속해있음을 의미한다.

 예를 들어, 집합 {1, 3, 4}의 비트 표현은 5비트의 정수로 표현할 수 있으며, 11010와 같다.

int x = 0;
x |= (1<<1);
x |= (1<<3);
x |= (1<<4);
    
for (int k = 8; k >= 0; k--) {
    cout << (x&(1<<k) ? "1" : "0");
}
// 000011010
// 가장 뒤에 있는 비트를 0번째 비트라고 보았을 때, 1, 3, 4번째 비트가 1, 나머지 비트는 0인 것을 확인할 수 있다.

 

 이처럼 비트를 이용하여 집합을 표현한다면, 각 원소마다 비트 한 개 만큼의 메모리를 사용하고, 집합에 대한 연산을 비트 연산을 이용해 구현할 수 있기 때문에 효율적이다.

 

- 모든 부분 집합 구하기

 

 집합 x={1, 2, 3}의 모든 부분 집합을 구하는 코드는 다음과 같다.

2진수	subset	10진수
000	{}	0
001	{1}	1
010	{2}	2
011	{1, 2}	3
100	{3}	4
101	{1, 3}	5
110	{2, 3}	6
111	{1, 2, 3}	7

vector<int> x = {1, 2, 3};
int n = int(x.size());
    
vector<vector<int>> subsets;
for (int i = 0; i < (1<<n); i++) {
    vector<int> v;
    for (int j = 0; j < n; j++) {
        if(i & (1 << j)) {
            v.push_back(x[j]);
        }
    }
    subsets.push_back(v);
}
    
for (int i = 0; i < subsets.size(); i++) {
    cout << "{";
    for(int j = 0; j < subsets[i].size(); j++) {
        if(j != subsets[i].size()-1) cout << subsets[i][j] << ",";
        else cout << subsets[i][j];
    }
    if(i != subsets.size()-1) cout << "}, ";
    else cout << "}";
}
// {}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}

 

- 집합에 대한 연산

// 교집합(a ∩ b)
a & b

// 합집합(a ∪ b)
a | b

// 여집합(a^c)
~a

// 차집합(a - b)
a & (~b)

 

 예를 들어, 집합 x={1, 3, 4, 8}, y={3, 6, 8, 9}를 만든 후, 집합 i=a∩b={3, 8}, u=a∪b={1, 3, 4, 6, 8, 9}를 만드는 코드는 다음과 같다.

int x = (1<<1)|(1<<3)|(1<<4)|(1<<8);
int y = (1<<3)|(1<<6)|(1<<8)|(1<<9);
int i = x&y;
int u = x|y;
    
for (int k = 10; k >= 0; k--) {
    cout << (i&(1<<k) ? "1" : "0");
}
cout << '\n';
// 00100001000
    
for (int k = 10; k >= 0; k--) {
    cout << (u&(1<<k) ? "1" : "0");
}
cout << '\n';
// 01101011010

 

 

[ 참고 자료 ]

안티 라크소넨, ⌜알고리즘 트레이닝 2판 - 프로그래밍 대회 입문 가이드⌟, 인사이트, 2022, 26~29쪽

개발자영맨, (2023, Jul 5), [Algorithm] 모든 조합(부분집합) 구하기(1/2) [Video], Yutube, https://www.youtube.com/watch?v=wy678Yc5iqE&list=PL-OC--HdIAXMXZ3IXSeLaO9Rl6qJNGc6g&index=63