[알고리즘] 비트마스크 (Bitmask)

해당 글은 모든 자바스크립트 개발자가 알아야 하는 33가지 개념에서 열두 번째인 Bitwise Operators, Type Arrays and Array Buffers 항목을 공부하면서 간단하게 작성한 글이다.

비트마스크란?

컴퓨터가 사용하는 데이터의 최소 단위인 비트를 활용해서 정수의 이진수 표현을 자료구조로 쓰는 기법이다. 비트마스크는 알고리즘보다는 비트를 활용한 테크닉으로 본다. 비트는 0 또는 1만 있을 수 있고 0은 off를 1은 on을 의미한다.

장점

• 비트 연산을 사용하기 때문에 O(1)이라는 빠른 연산속도를 가진다. 
• 하나의 정수만을 이용해서 다양한 경우의 수를 표현할 수 있기 때문에 메모리 사용량이 적다. (DP 문제에 유용)
• 비트 연산자를 사용해서 한 줄의 간결한 코드로 원하는 값을 찾을 수 있다.

비트 연산자

AND 연산자 (&)

각 비트를 비교해서 둘 다 1인 경우에만 1을 반환한다.

const a = 10;
const b = 15;
a & b; // 1010 & 1111 = 1010 (10)

OR 연산자 (|)

각 비트를 비교해서 둘 중에 하나만 1이어도 1을 반환한다.

const a = 10;
const b = 15;
a | b; // 1010 | 1111 = 1111

XOR 연산자 (^)

OR 연산자와 비슷하게 둘 중 하나만 1이어도 1을 반환하지만 둘 다 1인 경우에는 0을 반환한다. 즉 둘 중 하나만 1인 경우에만 1을 반환한다.

const a = 10;
const b = 15;
a ^ b; // 1010 ^ 1111 = 0101

NOT 연산자 (~)

정수 하나를 입력받아서 1인 비트는 0으로, 0인 비트는 1로 바꾼다.

const a = 10;
~a; // ~1010 = 0101

SHIFT 연산자 (<< , >>)

비트들은 왼쪽 또는 오른쪽으로 원하는 만큼 움직이고 빈 공간은 0으로 채운다.

const a = 13;
a << 1; // 1101 << 1 = 1010

집합

하나의 비트가 하나의 원소를 표현하기 때문에 집합의 모든 부분집합을 표현할 수 있다. 부분집합에서 0은 해당 원소가 없음을 1은 있음을 의미한다. 일단 아래의 모든 예제에서는 한 집합에 10개의 원소가 있다고 가정을 한다.

공집합과 꽉 찬 집합

공집합은 모든 비트가 0인 상황을 의미하고 꽉 찬 집합은 모든 원소가 1인 상황을 의미한다.

a = 0; // 공집합 0000000000(2)
a = (1 << 10) - 1; // 꽉 찬 집합 -> 10000000000(2) - 1 = 1111111111(2)

원소 추가

원소를 추가하려면 원하는 원소에 해당하는 비트를 1로 만들어야 한다. 그러기 위해서는 항상 1로 만드는 OR 연산자를 사용한다. b는 추가하고 싶은 원소의 위치를 의미한다.

a | (1 << b);

원소 삭제

원소를 삭제하려면 원하는 원소에 해당하는 비트를 0으로 만들어야 한다. 하지만 원소 추가할 때와 비슷하게 먼저 SHIFT 연산자를 사용하고 AND 연산자를 사용하게 되면 나머지 원소들의 포함 여부까지 바꿔버릴 수 가있다. 

a & (1 << b); 
// 0111111111 & (1 << 9) 를 하게 되면 0111111111 & 10000000000 = 0000000000 이 되버린다.

그러므로 SHIFT 연산자를 하고 난 결과값에 NOT 연산자를 추가로 해줘서 삭제를 원하는 원소만 0이 되고 나머지는 1이 되게 만들어서 원하는 값만 삭제할 수 있다.

a & ~(1 << b); 
// 1111111111 & ~(1 << 9) 를 하게 되면 1111111111 & 0111111111 = 0111111111 이 된다.

원소 포함 여부 확인

확인하고자 하는 원소의 비트가 1인지만 확인하면 된다.

if( a & (1 << b) )

원소의 토글

원하는 원소가 0이면 1로, 1이면 0으로 바꿔주면 되기 때문에 XOR 연산자를 사용한다.

a ^ (1 << b); 
// 1111111111 ^ ~(1 << 3) 를 하게 되면 1111111111 & 0000001000 = 1111110111 이 된다.

두 집합에 대한 연산

A | B; // 합집합
A & B; // 교집합
A & ~B; // 차집합
A ^ B; // 합집합에서 교집합을 제외한 집합

집합의 크기

비트를 오른쪽으로 SHIFT를 해주면서 1의 개수를 세어준다.

function size(a){
    if(a === 0) return 0;
    
    return (a & 1) + size(a >> 1);
}

최소 원소 찾기

컴퓨터는 음수를 표현할 때 two's compliment를 이용하기 때문에 -a = ~a + 1의 공식이 사용된다. 이것을 활용해서 최소 원소를 찾을 수 있다.

a & (-a);
/*
    a = 1010001010
    -a = ~a + 1 -> two's compliment
    ~a = 0101110101
    ~a + 1 = 0101110110
    따라서 a & (-a) = 0000000010
 */

최소 원소 지우기

최소 원소를 지우려면 집합 a에서 1을 빼준 다음에 AND 연산자를 사용하면 된다. a 에서 1을 빼면 가장 오른쪽에 있는 1, 즉 최소 원소의 비트 값이 0이 되고 그보다 더 오른쪽에는 비트들은 모두 1이 되기 때문이다.

a & (a - 1);
/*
	a = 0100010100
    a - 1 = 0100010011
    a & (a - 1) = 0100010000
*/

모든 부분 집합 순회하기

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