비트마스크 (Bitmask)

비트마스크 (Bitmask)에 대해 정리한 페이지입니다.

Posted Mar 25, 2024

By HyunJinNo

Tags

Algorithm

1. 개요

비트마스크(Bitmask)에 대해 정리한 페이지입니다.

2. 비트마스크 (Bitmask)

2.1. 개념

비트마스크(Bitmask)란 정수의 이진수 표현을 자료 구조로 사용하는 기법을 말합니다.

Info.

비트(Bit): 이진수의 한 자리를 비트(Bit)라고 합니다.

최상위 비트(Most Significant Bit): 2^{N - 1}에 해당하는 비트를 말합니다.

최하위 비트(Least Significant Bit): 2⁰에 해당하는 비트를 말합니다.

2.2. 특징

비트마스크의 특징은 다음과 같습니다.

• 간결한 코드

  다양한 집합 연산들을 반복문 없이 한 줄에 작성할 수 있습니다.

• 더 작은 메모리 사용량

  비트마스크를 이용하는 코드들은 같은 데이터를 더 적은 메모리를 사용해 표현할 수 있습니다. 특히 Boolean 값 배열을 키로 갖는 연관 배열 객체 Map<Boolean[], Integer>을 비트마스크를 이용하여 int[] 배열로 대체할 수 있어서 시간과 메모리를 절약할 수 있습니다.

• 시간 복잡도(Time Complexity)

  대부분의 비트마스크 연산은 O(1)의 시간 복잡도를 갖으므로 적절히 사용할 경우 다른 자료 구조를 사용하는 것보다 훨씬 빠르게 동작합니다.

2.3. 비트 연산자

2.4. 비트마스크를 이용한 집합 구현

2.4.1. 꽉 찬 집합

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

2.4.2. 공집합

1int emptySet = 0;

2.4.3. 원소 추가

1bitSet |= (1 << p);

2.4.4. 원소의 포함 여부 확인

1// & 연산의 결과 값이 0 또는 (1 << p) 라는 점을 주의해야 합니다.
2if (bitSet & (1 << p)) {
3  System.out.println("원소가 포함되어 있음.");
4}

2.4.5. 원소의 삭제

1bitSet &= ~(1 << p);

2.4.6. 원소의 토글

1bitSet ^= (1 << p);

2.4.7. 두 집합에 대한 연산

1int added = (a | b); // a와 b의 합집합
2int intersection = (a & b); // a와 b의 교집합
3int removed = (a & ~b); // a에서 b를 뺀 차집합
4int toggled = (a ^ b); // a와 b중 하나에만 포함된 원소들의 집합

2.4.8. 집합의 크기

1int bitCount(int x) {
2  if (x == 0) return 0;
3  return x % 2 + bitCount(x / 2);
4}

2.4.9. 최소 원소 지우기

1bitSet &= (bitSet - 1);

2.4.10. 2의 거듭제곱 값인지 여부 확인

1// 2의 거듭제곱 값들의 이진수 표현에는 켜진 비트가 하나 밖에 없습니다.
2if ((num & (num - 1)) == 0) {
3  System.out.println("2의 거듭제곱 값입니다.");
4}

2.4.11. 모든 부분 집합 순회

1for (int subset = bitSet; subset > 0; subset = ((subset - 1) & bitSet)) {
2  // subset은 bitSet의 부분 집합
3  // (subset > 0): 공집합은 방문하지 않습니다.
4}

3. Example

• 비트마스크를 사용하는 에라토스테네스의 체

  javascript

  1// 비트마스크(Bitmask)를 사용하는 에라토스테네스의 체의 구현
  2
  3const n = 1000000; // n개의 원소
  4
  5/**
  6 * Uint8Array와 비트마스크를 사용하여 메모리 사용량을 8분의 1로 줄인다.
  7 * 0: 합성수, 1: 소수
  8 */
  9const sieve = new Uint8Array(Math.floor((n + 7) / 8)).fill(255);
  10
  11/**
  12 * 비트를 0으로 바꿔서 x가 소수가 아니라고 표시한다.
  13 * @param {number} x
  14 */
  15const setComposite = (x) => {
  16  sieve[x >> 3] &= ~(1 << (x & 7));
  17};
  18
  19/**
  20 * x가 소수인지 확인한다
  21 * @param {number} x 판정할 값
  22 * @returns {Boolean} 소수 여부
  23 */
  24const isPrime = (x) => {
  25  if (sieve[x >> 3] & (1 << (x & 7))) {
  26    return true;
  27  } else {
  28    return false;
  29  }
  30};
  31
  32setComposite(0);
  33setComposite(1);
  34for (let x = 2; x <= n; x++) {
  35  if (isPrime(x)) {
  36    for (let y = x * x; y <= n; y += x) {
  37      setComposite(y);
  38    }
  39  }
  40}
  41
  42for (let x = 2; x <= n; x++) {
  43  if (isPrime(x)) {
  44    console.log(x);
  45  }
  46}

• 1311번: 할 일 정하기 1

  javascript

  1const path =
  2  process.platform === "linux" ? "/dev/stdin" : "./JavaScript/input.txt";
  3const input = require("fs").readFileSync(path).toString().split("\n");
  4
  5const n = Number(input[0]); // 사람과 일의 수, 1 <= n <= 20
  6const cache = Array.from(Array(n), () => new Array(1 << n).fill(-1));
  7const arr = [];
  8
  9for (let i = 1; i <= n; i++) {
  10  arr.push(input[i].split(" ").map(Number));
  11}
  12
  13/**
  14 * 모든 일을 하는데 필요한 비용의 최솟값을 구하는 함수
  15 * @param {number} index (index)번째 사람
  16 * @param {number} visited 지금까지 한 일
  17 * @returns 최소 비용 값
  18 */
  19const solve = (index, visited) => {
  20  if (index >= n) {
  21    return 0;
  22  } else if (cache[index][visited] !== -1) {
  23    return cache[index][visited];
  24  }
  25
  26  let result = Number.MAX_SAFE_INTEGER;
  27
  28  for (let i = 0; i < n; i++) {
  29    if ((~visited & (1 << i)) === 1 << i) {
  30      visited |= 1 << i;
  31      result = Math.min(
  32        result,
  33        arr[index][n - 1 - i] + solve(index + 1, visited),
  34      );
  35      visited &= ~(1 << i);
  36    }
  37  }
  38
  39  cache[index][visited] = result;
  40  return result;
  41};
  42
  43console.log(solve(0, 0));

4. 참고 자료

• 알고리즘 문제 해결 전략 세트 | 구종만 | 인사이트(insight) - 예스24