비트마스크

비트의 위치가 1이면 켜져 있는 것, 0이면 꺼져 있는 것

 

🍟 비트마스크를 사용하면 얻는 장점

1. 더 빠른 수행 시간 : O(1)
2. 더 간결한 코드
3. 더 작은 메모리 사용량
4. 연관 배열을 배열로 대체 : map<vector<bool>, int>를 int[]로 대체

 

🦘 비트마스크를 이용한 집합의 구현

N비트 정수 변수는 0부터 N-1까지의 정수 원소를 가질 수 있는 집합이 된다.

원소 i가 집합에 속해 있다면 2^i 비트가 1이다.

상수 0은 공집합

int num=(1<<20)-1;

꽉 찬 집합의 예

num |= (1<<p);

원소 추가의 예

if(num & (1<<p))

원소 포함 여부 확인

& 연산의 결과는 0 또는 1<<p

 

num -= (1<<p);
num &= ~(1<<p);

원소의 삭제

num -= (1<<p);는 없는 원소를 삭제하려고 하면 에러가 난다.

 

num ^= (1<<p);

원소의 토글

XOR 연산

원소가 num에 있으면 삭제, 없으면 추가

 

 

🦘 비트마스크 사용 예시

# 백준 '1182. 부분수열의 합' 문제에서
N, S=map(int, (input().split()))  # 정수의 개수, 정수
lst=list(map(int, input().split()))     # N개의 정수
answer=0

for i in range(1,1<<N) :     # 부분집합의 개수
    total=0
    for j in range(N) :
        if i & 1<<j :
            total+=lst[j]
    if total == S :
        answer+=1

print(answer)

 

// 백준 문제 '11723 : 집합'중에서
switch(op){
                case "add" :
                    num=Integer.parseInt(st.nextToken());
                    bitset|=(1<<(num-1));
                    break;
                case "remove" :
                    num=Integer.parseInt(st.nextToken());
                    bitset=bitset & ~(1 << (num-1));
                    break;
                case "check" :
                    num=Integer.parseInt(st.nextToken());
                    sb.append((bitset & (1<<(num-1))) != 0 ? "1\n" : "0\n");
                    break;
                case "toggle" :
                    num=Integer.parseInt(st.nextToken());
                    bitset^=(1<<(num-1));
                    break;
                case "all" :
                    bitset |= (~0);
                    break;
                case "empty" :
                    bitset &= 0;
                    break;
            }
        }

 

 

참고 👉 프로그래밍 대회에서 배우는 알고리즘 문제해결전략