[Javascript 코테 대비] 비트 마스크

비트마스크(bitmask)

정수의 이진수 표현을 자료 구조로 쓰는 기법을 비트마스크라고 부른다.

비트마스크를 사용하는 코드의 장점

1. 더 빠른 수행 시간
   $O(1)$에 구현되는 것이 많다.
2. 더 간결한 코드
   반복문 없이 한 줄에 코드를 쓸 수 있다.
3. 더 작은 메모리 사용량
   많은 데이터를 미리 계산해 둘 수 있어서 캐시 효율이 더 좋다.
4. 연관 배열을 배열로 대체
   boolean 값 배열을 키로 갖는 연관 배열 객체 <vetor<bool>, int> 를 사용하고 있다고 할 때, 비트마스크를 써서 같은 정보를 정수 변수로 나타내면 단순한 int[]를 사용해 같은 정보를 나타낼 수 있다.

비트 연산자

비트마스크를 사용하기 위해서는 정수 변수를 비트별로 조작할 수 있는 비트 연산자를 사용해야 한다.

• AND 연산: 두 비트가 모두 켜져있을 때만 결과의 비트를 켠다.
• OR 연산: 두 비트 중 하나라도 켜져 있을 경우 결과의 비트를 켠다.
• XOR 연산: 하나는 켜져 있고 하나는 꺼져 있을 경우 결과의 비트를 켠다.
• NOT 연산: 정수 하나를 입력받아 켜져 있는 비트는 끄고, 꺼져 있는 비트는 켜서 반환한다.
• 시프트(shift) 연산: 정수 $a$의 비트들을 왼쪽 또는 오른쪽으로 원하는 만큼 움직인다. 움직이고 나서 빈자리는 0으로 채워진다.

JS의 비트 연산자

JS에서 비트마스크를 사용하면 비트 연산의 피연산자가 32비트 정수로 변환된다

연산	코드
두 정수 $a$, $b$를 비트별로 AND 연산	a & b
두 정수 $a$, $b$를 비트별로 OR 연산	a ⅼ b
두 정수 $a$, $b$를 비트별로 XOR 연산	a ^ b
정수 $a$의 비트별로 NOT 연산 결과	~a
정수 $a$를 왼쪽으로 $b$비트 시프트	a << b
정수 $a$를 오른쪽으로 $b$비트 시프트	a >> b

유의할 점

• 비트 연산자의 우선 순위는 비교 연산자보다 낮다.

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

비트마스크의 가장 중요한 사용 사례는 집합을 구현하는 것이다.
이 표현에서 $N$비트 정수 변수는 0부터 $N$-1까지의 정수 원소를 가질 수 있는 집합이 된다.

원소 $i$가 집합에 속해 있는지 여부는 $2^i$을 나타내는 비트가 켜져 있는지 여부로 나타낸다.

집합 {1, 4, 5, 6, 7}을 표현하는 정수는 754이다.

$2^1 + 2^4 + 2^5 + 2^7 + 2^9 = 10 1111 0010_2 = 754$

예제로 보는 집합 비트마스크 연산

피자는 0부터 19까지의 번호를 갖는 스무 가지의 토핑이 있으며, 주문시 토핑을 넣기 / 넣지 않기를 선택할 수 있다.

-> 피자의 토핑을 비트마스크를 이용해 표현해본다.

공집합과 꽉 찬 집합 구하기

const plainPizza = 0; // 공집합
const fullPizza = (1 << 20) - 1; // 꽉 찬 집합

원소 추가

const toppings |= (1 << p);

원소의 포함 여부 확인

if (topping & (1 << p)) 
  	// 1 << p: 포함되어 있음
  	// 0 :  포함되어 있지 않음

원소의 삭제

topping &= ~(1 << p))

원소의 토글

toppings ^= (1 << P);

두 집합에 대해 연산하기

result = (a | b) 	// a와 b의 합집합
result = (a & b) 	// a와 b의 교집합
result = (a & ~b) 	// a에서 b를 뺀 차집합
result = (a ^ b) 	// a와 b중 하나에만 포함된 원소들의 집합

집합의 크기 구하기

function bitCount(x) {
  if(x === 0) return 0;
  return x % 2 + bitCount(x / 2);
}

최소 원소 찾기

const firstTopping = (toppings & -toppings);

• 컴퓨터는 음수를 표현하기 위해 2의 보수를 사용한다.
• toppings의 NOT 연산을 적용하고 그 결과에 1을 더한다.
• 결과: $2^i$를 구할 수 있다!

최소 원소 삭제하기

toppings &= (toppings - 1);

• topping-1의 이진수 표현은 최하위 비트를 끄고 그 밑의 비트들을 전부 킨 것이다.
• 최하위 비트를 지웠을 때 0이 된다면 주어진 수는 2의 거듭제곱인 것이다

모든 부분 집합 순회하기

let pizza; 
for(let subset = pizza; subset; subset = ((subset-1) & pizza)) {
	
}

subset = ((subset-1) & pizza)

• subset-1은 subset의 최하위 비트가 꺼지고, 그 밑의 비트들은 전부 켜진다.
• 교집합을 구하면 그 중 pizza에 속하지 않는 비트들은 모두 꺼진다.

+) N진수 변환

10진수 -> N진수

var dec = 123;
var hex = dec.toString(16); // === "7b"
var bin = dec.toString(2); 	// === "1111011"

N진수 -> 10진수

var hex = "7b";
var bin = "11110111";
var dec1 = parseInt(hex, 16);	// === "123"
var dec2 = parseInt(bin, 2);	// === "123"