📌개요
컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다. 이 이진수는 비트(bit)이며, 0,1 값을 가질 수 있고, true/false라는 상태를 나타낸다. 이 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스크라고 한다. 비트 마스크를 이용하면 더 빠른 수행 시간, 더 간결한 코드, 더 적은 메모리 사용이라는 효과를 얻을 수 있다.
🤷♂️비트마스킹을 쓰는 이유
1. 수행 시간이 빠르다.
비트마스크 연산은 bit 연산이기 때문에 O(1)에 구현되는 것이 많다. 따라서 다른 자료구조를 이용하는 것보다 훨씬 빠르게 동작하게 된다. 하지만, 비트마스크를 이용하는 경우에는 비트의 개수만큼 원소를 다룰 수 있기 때문에 연산 횟수가 늘어날수록 속도에 큰 차이가 생기게 된다.
2. 코드가 짧다.
다양한 집합 연산들을 비트연산자로 한 줄로 작성할 수 있기 때문에 반복문, 조건문 등을 이용한 코드보다 훨씬 간결한 코드를 작성할 수 있다.
3. 메모리 사용량이 더 적다.
예를 들어, bit가 10개인 경우에 2^10가지 경우를 10bit 이진수 하나로 표현이 가능하다.
이처럼 하나의 정수로 매우 많은 경우의 수를 표현할 수 있기 때문에 메모리 측면에서 효율적이며, 더 많은 데이터를 미리 계산해서 저장해 둘 수 있는 장점이 있다. (DP에 유용)
📱비트 연산자
비트마스크를 이용하기 위해서, 정수 변수를 비트 별로 조작할 수 있는 비트연산자를 사용한다. 두 정수 변수 또는 하나의 정수 변수를 이용하여 새로운 값을 만들어 내는 것이 목적이다.
a & b // AND 000101 & 000011 = 000001 a | b // OR 000101 | 000011 = 000111 a ^ b // XOR 000101 ^ 000011 = 000110 ~a // NOT ~000101 = 111010 a << b // SHIFT 000101 << 000011 = 101000 a >> b // SHIFT 000101 >> 000011 = 000000
⚙비트마스크를 이용한 집합 구현
비트마스크를 이용한 집합 구현은 가장 대표적이고, 중요한 사례이다. "하나의 bit가 하나의 원소"를 의미하게 된다. bit가 켜져 있으면 해당 원소가 집합에 포함되어 있다는 의미이고, 꺼져있으면 포함되어 있지 않다는 표현이다.
따라서 N비트 정수 변수라면 N개의 원소를 갖는 집합의 부분집합들을 모두 표현할 수 있게 한다.
원래는 N개의 boolean 원소를 갖는 배열을 선언해야 했지만, 비트마스크를 이용하면 정수 하나로 표현이 가능하기 때문에 사용하는 메모리의 크기가 많이 줄어드는 장점이 있다.
| 연산 | 사용 예시 |
|---|---|
| 공집합과 꽉 찬 집합 구하기 | A = 0; / A = (1 << 10) - 1; |
| 원소 추가 | A I= (1<<k); |
| 원소 삭제 | A &= ~(1<<k); |
| 원소의 포함 여부 확인 | if(A & (1<<k)) |
| 원소의 토글 | A ^= (1<<k); |
| 두 집합에 대해서 연산 | AIB -> A와 B의 합집합 |
| A&B -> A와 B의 교집합 | |
| A&(~B) -> A와 B를 뺀 차집합 | |
| A^B -> A와 B중 하나에만 포함된 원소들의 집합 | |
| 집합의 크기 구하기 | Integer.bitCount(A) |
| 최소 원소찾기 | int first = A & (-A); |
| 최소 원소 지우기 | A &= (A-1); |
| 모든 부분 집합 순회하기 | for(int subset = A; subset ; subset = ((subset-1) & A)){} |
야호