비트마스킹 (Bitmask)

정의

비트마스킹 (Bitmask) 은 집합 / 상태 를 정수의 비트 패턴 으로 인코딩해 집합 연산을 비트 연산으로 처리하는 기법.

{0, 2, 3} 같은 집합을 0b1101 = 13 으로 표현하면, 멤버 확인 / 추가 / 제거 / 합집합 / 교집합 모두 &, |, ^, ~ 한 줄.

크기 N ≤ 20 (또는 25) 인 작은 집합의 모든 부분집합 순회 + DP 의 정형. Bitfield DP, SOS DP 의 기반.

문제 상황과 동기

“N 명을 선택하는 방법은 2^N 개. N=20 이면 약 10^6. 모든 부분집합을 보고 점수 최대 / 최소를 구하라”

• naive set / vector: 한 부분집합당 메모리 / 시간 O(N). 총 O(N · 2^N) = 2·10^7. 빡빡.
• bitmask: 한 부분집합을 int 하나 로. O(1) operations. 총 O(2^N) ~ O(N · 2^N).

핵심 통찰: 원소 N 이 32 이하면, 한 부분집합 = 한 정수 = 한 캐시 라인 안에서 모든 연산.

시각화

핵심 아이디어

각 원소를 비트 위치 에 대응. 집합 S 의 비트 표현:

S = {0, 2, 3, 5}  →  mask = (1<<0) | (1<<2) | (1<<3) | (1<<5) = 0b101101 = 45

핵심 연산

모든 부분집합 순회

for mask = 0..(1<<N)-1:
    // mask = 한 부분집합

부분집합의 부분집합 순회 (SOS 의 기반)

sub = mask
while sub > 0:
    // sub = mask 의 부분집합 중 하나
    sub = (sub - 1) & mask
// sub = 0 한번 더 처리

총 시간 O(3^N) (각 원소가 in/out/없음 3 상태).

알고리즘

// 모든 부분집합에서 어떤 값을 최대화
best = 0
for mask = 0..(1<<N)-1:
    score = 0
    for i = 0..N-1:
        if (mask >> i) & 1:
            score += value[i]
    best = max(best, score)

구현

// N 개 아이템 중 무게합 ≤ W 인 부분집합의 최대 가치합 (N ≤ 20)
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, W; cin >> n >> W;
  vector<int> w(n), v(n);
  for (auto& x : w) cin >> x;
  for (auto& x : v) cin >> x;
  int best = 0;
  for (int mask = 0; mask < (1 << n); mask++) {
      int sw = 0, sv = 0;
      for (int i = 0; i < n; i++) if ((mask >> i) & 1) {
          sw += w[i]; sv += v[i];
      }
      if (sw <= W) best = max(best, sv);
  }
  cout << best << "\n";
}

# 모든 부분집합 순회, N ≤ 20
import sys
input = sys.stdin.readline
​
n, W = map(int, input().split())
w = list(map(int, input().split()))
v = list(map(int, input().split()))
best = 0
for mask in range(1 << n):
  sw = sv = 0
  for i in range(n):
      if (mask >> i) & 1:
          sw += w[i]; sv += v[i]
  if sw <= W and sv > best:
      best = sv
print(best)

// 비트마스크로 부분집합 순회
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int W = Integer.parseInt(st.nextToken());
      int[] w = new int[n], v = new int[n];
      st = new StringTokenizer(br.readLine());
      for (int i = 0; i < n; i++) w[i] = Integer.parseInt(st.nextToken());
      st = new StringTokenizer(br.readLine());
      for (int i = 0; i < n; i++) v[i] = Integer.parseInt(st.nextToken());
      int best = 0;
      for (int mask = 0; mask < (1 << n); mask++) {
          int sw = 0, sv = 0;
          for (int i = 0; i < n; i++) if (((mask >> i) & 1) == 1) {
              sw += w[i]; sv += v[i];
          }
          if (sw <= W) best = Math.max(best, sv);
      }
      System.out.println(best);
  }
}

4 10
2 3 4 5
3 4 5 6

13

(N=4 아이템, 무게합 ≤ 10. 최적: {0,1,2,3} 다 못 담으니 {0,2,3} 무게 11 안 됨, {0,1,3} 무게 10, 가치 13)

복잡도

변형 / 활용

함정

1. 32-bit overflow

N = 32 이상이면 1 << N 이 int overflow. 1LL << N 사용 (long long).

2. 음수 shift

1 << 31 의 결과는 signed int 의 부호 비트, undefined-ish 행동. unsigned 또는 long long 사용.

3. popcount 가 느린 환경

Java < 5 또는 일부 임베디드 환경에서는 Integer.bitCount 가 SW 구현. PS 에서는 보통 hardware popcnt.

4. 부분집합 순회의 중첩

for mask in 0..(1<<N)-1 안에서 또 for i in 0..N-1 로 비트 검사하면 O(N · 2^N). 이걸 막으려면 popcount + table 또는 SOS 변환.

표준 라이브러리

BOJ 연습 문제

참고

• 비트필드 DP
• Bitset Optimization
• FWHT