비트마스킹 입문: 선택한 항목을 숫자에 기록하기

비트마스크는 고정된 항목들의 선택 여부를 숫자 하나에 담는 방법입니다. 위치 0은 값 1, 위치 1은 값 2처럼 항목마다 겹치지 않는 자리를 배정합니다.

선수 지식: 0과 1의 이진수 표기, 정수와 배열 인덱스를 이해하면 좋습니다.

• 항목 번호와 비트의 위치를 구분합니다.
• 선택 추가·확인·제거를 연산으로 표현합니다.

항목 1과 3을 고르면 2+8이 됩니다

항목 번호를 0부터 매기고 i번 항목의 자리를 1<<i로 정합니다. 1번은 이진수 0010, 3번은 1000입니다. 둘을 선택하면 1010, 십진수 10입니다. 숫자 10 자체가 항목 번호인 것이 아니라 여러 자리의 선택 상태를 합쳐 저장한 값입니다.

특정 자리가 켜져 있는지만 묻는다면 AND 결과가 0인지 확인합니다. 비트 위치와 실제 항목 ID가 다르면 두 값을 연결하는 표도 필요합니다. 예를 들어 도시 ID가 100, 200이라면 이를 그대로 시프트하지 말고 0, 1 같은 작은 인덱스로 대응시킵니다.

추가는 OR, 제거는 AND와 반전입니다

OR는 이미 켜진 자리를 다시 추가해도 그대로 둡니다. XOR는 같은 자리를 두 번 처리하면 꺼지므로 “반드시 추가”가 아니라 “선택 상태 뒤집기”에 알맞습니다. 제거할 때는 해당 비트만 0인 마스크와 AND합니다. 없는 항목을 제거해도 나머지 선택은 바뀌지 않습니다.

코드는 mask와 slot을 매번 검사합니다. 전체 마스크를 받고 특정 비트만 바꾸는 함수가 입력 범위를 검사하지 않으면 음수나 소수도 비트 연산 과정에서 다른 값으로 바뀔 수 있습니다. 이 예제의 계약은 20개 위치, 0~19이며 선택 집합에 없는 다른 비트는 허용하지 않습니다.

JavaScript Number의 비트 연산은 큰 정수 저장소가 아닙니다

Number에 쓰는 AND·OR·시프트는 32비트 정수 변환을 따릅니다. 부호 자리까지 무심코 사용하면 양수로 기대한 결과가 음수가 될 수 있고, 시프트 횟수도 임의의 큰 자리로 확장되지 않습니다. 여기서 20개라는 제한은 학습 예제와 이후 상태 수를 관리하기 위한 선택입니다. 언어가 비트를 20개만 지원한다는 뜻은 아닙니다.

항목이 많거나 ID가 드문드문 있으면 Set이 더 읽기 쉬울 수 있습니다. BigInt 비트 연산을 사용할 수도 있지만 Number와 섞을 수 없으며 예제 전체의 숫자형 계약을 바꿔야 합니다. 항목을 마스크로 압축해도 가능한 부분집합 수 2의 n제곱이 작아지는 것은 아닙니다.

전체 코드와 직접 실행

개념을 읽었다면 아래 예제를 직접 실행하며 상태 변화를 확인할 수 있습니다.

function checkMask(mask) {
  if (!Number.isInteger(mask) || mask < 0 || mask >= 2 ** 20) {
    throw new RangeError('mask는 20비트의 음이 아닌 정수여야 합니다.');
  }
}
function checkSlot(slot) {
  if (!Number.isInteger(slot) || slot < 0 || slot >= 20) {
    throw new RangeError('위치는 0부터 19까지입니다.');
  }
}
function addFlag(mask, slot) {
  checkMask(mask); checkSlot(slot);
  return mask | (1 << slot);
}
function removeFlag(mask, slot) {
  checkMask(mask); checkSlot(slot);
  return mask & ~(1 << slot);
}
function hasFlag(mask, slot) {
  checkMask(mask); checkSlot(slot);
  return (mask & (1 << slot)) !== 0;
}
function selectedIds(mask) {
  checkMask(mask);
  const result = [];
  for (let slot = 0; slot < 20; slot++) if (hasFlag(mask, slot)) result.push(slot);
  return result;
}

const selected = addFlag(addFlag(0, 1), 3);
console.log(selected);
console.log(JSON.stringify(selectedIds(selected)));
console.log(removeFlag(selected, 1));

node bitmask-selected-set.mjs

10
[1,3]
8

비용과 적용 범위

시간: 예제의 단일 추가·확인·제거는 고정 폭의 O(1), 전체 선택 목록은 위치 수 k에 대해 O(k)입니다.

공간: 마스크는 O(1), 선택 목록을 반환하면 O(k)까지 필요합니다.

분석 조건: 20개 위치만 허용합니다. 부분집합 전체를 열거하면 여전히 2^k개 상태입니다.

직접 확인해 보기

현재 값 10에서 3번 항목이 선택됐는지 확인하고 3번을 제거하면 얼마인가요?

함께 읽을 글

• Map·Set으로 값 조회와 중복 제거 — 같은 선택 집합을 Set으로 표현하는 방법과 비교합니다.
• 기초 구현 패턴 — 반복에서 어떤 값을 보관하고 갱신하는지 먼저 익힙니다.

참고 자료

• MDN — Bitwise AND — Number 비트 연산의 32비트 변환을 확인합니다. 예제는 부호 비트를 피하는 20개 위치만 허용합니다.