비트마스크(BitMask)

비트 연산을 이용하여 문제를 효율적으로 해결하는 기법

비트 연산자

• AND (&): 두 비트가 모두 1이면 1을 반환
• OR (|): 두 비트 중 하나라도 1이면 1을 반환
• XOR (^): 두 비트가 서로 다르면 1을 반환
• NOT (~): 비트 반전
• Left Shift (<<): 비트를 왼쪽으로 이동
• Right Shift (>>): 비트를 오른쪽으로 이동

활용

• 삽입

let flags = 0b0000;  // 초기 상태: 0000
flags |= (1 << 3);   // 1로 설정: 0000 | 1000

• 삭제

let flags = 0b1000;  // 초기 상태: 1000
flags &= ~(1 << 3);  // 0으로 설정: 0111 & 1000

• 조회

let flags = 0b1000;  // 현재 상태: 1000
let isSet = (flags & (1 << 3)) === 1;  // true 반환

특징

1. 부분 집합 표현: 집합의 각 요소가 있는지 없는지를 비트로 표현하여, 모든 부분 집합을 간단한 정수로 표현 가능
2. 효율적인 메모리 사용
3. 빠른 연산과 간결한 코드

예제: 부분 집합 생성

function generateSubsets(set) {
    const n = set.length;
    const totalSubsets = 1 << n; // 2^n
    let result = [];

    for (let bitmask = 0; bitmask < totalSubsets; bitmask++) {
        let subset = [];
        for (let i = 0; i < n; i++) {
            if (bitmask & (1 << i)) { // i번째 비트가 1인지 확인
                subset.push(set[i]);
            }
        }
        result.push(subset);
    }

    return result;
}

const set = [1, 2, 3];
const subsets = generateSubsets(set);
console.log(subsets); // 모든 부분 집합 출력