비트마스킹(BitMask)

*️⃣ 정의

• 0 또는 1로 표현되는 이진수 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법

 

*️⃣ 장점

1. 수행 시간이 빠르다. 

비트마스크 연산은 bit 연산이기 때문에 대부분 O(1)에 구현된다.

비트마스크를 이용하는 경우에는 비트의 개수만큼 원소를 다룰 수 있기 때문에 연산 횟수가 적은 경우에는 속도에 큰 차이가 없지만, 연산 횟수가 늘어날수록 차이가 매우 커지게 된다. 

 

2. 코드가 짧다.

다양한 집합 연산들을 비트연산자로 한 줄로 작성할 수 있기 때문에 반복문, 조건문 등을 이용한 코드보다 훨씬 간결한 코드를 작성할 수 있다.

 

3. 메모리 사용량이 적다.

bit가 10개인 경우에는 각 bit당 두 가지 경우를 가지기 때문에 210210가지의 경우를 10bit 이진수 하나로 표현이 가능하다. 

이처럼 하나의 정수로 매우 많은 경우의 수를 표현할 수 있기 때문에 메모리 측면에서 효율적이며, 더 많은 데이터를 미리 계산해서 저장해 둘 수 있는 장점이 있다. (DP에 매우 유용하다)

 

 

*️⃣ 비트 연산자

A & B	a의 모든 비트와 b의 모든 비트를 AND연산 둘다 1이라면 1, 아니면 0 반환	00010110 (AND) & 00001110 ------------------                00000110
A | B	a의 모든 비트와 b의 모든 비트를 OR연산 둘다 0이라면 0, 아니면 1 반환	00010110 (OR) | 00001110 ------------------            00011110
A ^ B	a의 모든 비트와 b의 모든 비트를 XOR연산 둘이 다르다면 1, 아니면 0 반환	00010110 (XOR) ^ 00001110 ------------------                00011000
~A	a의 모든 비트에 NOT 연산 0이면 1, 1이면 0	(not) ~ 00010110 ------------------               11101001
A << B	a를 b비트 만큼 왼쪽으로 SHIFT	14 : 00001110 14 << 2 == 00111000  //우측 빈자리는 0으로 채워진다.
A >> B	a를 b비트 만큼 오른쪽으로 SHIFT	14 >> 2 == 00000011  //왼쪽 빈자리는 A의 최상위 부호비트와 같은 값으로 채워진다.

 

 

ℹ️ 응용 문제

https://www.acmicpc.net/problemset?sort=ac_desc&algo=14

 

✦ 백준 1094(JavaScript)

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

function solution(arr) {
  let target = +arr;
  let cnt = 0; // 막대기 개수

  while (target > 0) {
    cnt += target & 1; // 최하위 비트(즉, 필요한 막대)가 1이면 cnt에 더해줌
    target >>= 1;      // 비트를 오른쪽으로 한 칸씩 이동
  }

  return cnt;
}


console.log(solution(input));

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Operators/Left_shift_assignment

왼쪽 시프트 할당 연산자 (<<=) - JavaScript | MDN