비트마스킹

1. 비트마스킹

• 불리언 값으로 이루어진 집합에 대해서 굉장히 빠르게 연산하는 기법.
• 완전탐색의 속도를 빠르게 하기 위해 쓰이기도 함.
• DP의 한 인자로 사용되기도 함
  • 예를 들어 TSP의 경우 지금까지 어떤 곳을 방문했는가에 대한 집합으로 쓰임.

2. 비트의 연산

• 예제

const t1 = (t) => {
    let idx = 0;
    let temp = t;
  // ~ : 비트를 뒤집는다
  // 1<<0 -> 1 001
  // ~001 = 100
  // 5 & ~1 = 101 & 100 = 100 => 4
    temp &= ~(1<<idx);
    console.log(`불좀꺼줄래 T1: ${temp}\n`);
}
t1(5); // temp값 4 출력

// 1<<0 === 001
// 5 ^ 1 -> 101^001 === 100 = 4
const t2 = (t) => {
    let idx = 0;
    let temp = t;
    temp ^= (1<<idx);
    console.log(`XOR T2: ${temp}\n`);
}
t1(5); // temp값 4 출력

// t=5인경우 101 1인 최하위의 인덱스인 2^0 = 1 출력
// t=4인경우 100 1인 최하위의 인덱스인 2^1 = 4 출력
const t3 = (t) => {
  let idx = (t&-t);
  console.log(`최하위 켜져있는 인덱스 T3: ${idx}\n`);
}

const t4 = (t) => {
  let n = t;
  console.log(`크기가 n인 모든 집합의 모든 비트켜기 T4: ${(1<<n)-1}\n`)
}

const t5 = (t) => {
  let idx = 1;
  let temp = t;
  temp |= (1<<idx);
  console.log(`idx번째 불켜기 T5: ${temp}`);
}

const t6 = (t) => {
  let idx = 0;
  let temp = t;
  let a = temp & (1<<idx) ? 'yes':'no';
  console.log(`idx번째 비트가 있는지 확인하기 T6: ${a}\n`)
}

3. 비트마스킹 들어가기

• 배열의 어떤 요소를 찾을 때
  • 선형검색: O(N)
  • 이분검색: O(logN)
  • 해싱테이블: O(1)
• 불리언 배열에서 비트 연산을 통해 탐색, 수정 등의 작업을하는 것

3.1 이진수

1 : 1
2 : 10
3 : 11
4 : 100

• 2진수는 아래의 2진수가 그 범위를 침범하지 못하는 성질을 이용하면 마친 2진수 자체의 비트를 하나의 배열에 있는 요소처럼 쓸 수 있음.

• 즉, 101은 1과 4의 합집합, 111은 1과 2와 4의 합집합
  이로써 배열의 효과를 지니면서 매번 배열 전체를 탐색하지 않아도 &연산 하나로 이 집합에 포함되어 있음을 알 수 있음.

• 예를 들어, let a = {1,1,0}이라고 할 때 2번째 요소에 값이 들어있나? 확인하려면 for문을 통해 확인 그러나 이를 2진수로 표현하면,

  111(2) = 6
  6 & 1 = 0

• 즉, AND연산으로 값을 조회 가능.

참고

• DP(동적계획법)
• TSP(Traveling Salesman problem)
  • 외판원 순회 문제의 약자로. 컴퓨터과학분야에서 가장 중요하게 취급되는 문제 중 하나.
• 삽입: OR연산, 삭제: AND,NOT연산, 조회: AND연산을 사용