[알고리즘] 비트마스크(BitMask)란?

비트마스크(BitMask)란?

비트마스크는 이진수를 사용하는 컴퓨터의 연산 방식을 이용해, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말합니다.

이진수는 0 또는 1을 이용하므로 하나의 비트(bit)가 표현할 수 있는 2가지 경우가 있는데,

비트가 1이면 "켜져 있다"라고 말하며, 0이면 "꺼져 있다"라고 말합니다.

 

비트마스크를 사용하는 이유

🟢 빠른 수행시간

원소의 수가 많지 않을 때 사용되며, bit연산이기 때문에 시간복잡도 O(1)에 구현되는 것이 많습니다.

 

🟢 작은 메모리 사용량

만약 bit가 10개인 경우, 각 bit당 두 가지의 경우를 가지기 때문에 2^10가지의 경우를 10bit 이진수 하나로 표현 가능합니다.

그렇기 때문에 하나의 정수로 매우 많은 경우의 수를 표현할 수 있기 때문에 메모리 측면에서 효율적이며, 데이터를 미리 계산하여 저장해 둘 수 있으므로 캐시 효율이 좋습니다.

 

🟢 간결한 코드

다양한 집합 연사자들을 반복문 없이 한 줄에 쓸 수 있어 반복문, 조건문을 이용한 코드보다 훨씬 간결하게 코드를 작성할 수 있습니다.

 

---

비트 논리 연산자

연산자	논리	설 명
&	AND	두 비트 모두 1이면 1
|	OR	두 비트 중 1개만 1이면 1
^	XOR	두 비트가 서로 다르면 1
~	NOT	비트 반전(보수)
<<	LEFT SHIFT	지정한 수만큼 비트들을 전부 왼쪽으로 이동(이동되고 남은 비트는 0으로 채움)
>>	RIGHT SHIFT	지정한 수만큼 비트를 전부 오른쪽으로 이동(이동되고 남은 비트는 부호 비트로 채움) 부호를 유지

 

비트 논리 연산자 사용 예시

int x = 10; // 2진수로 변환시 1010
int y = 15; // 2진수로 변환시 1100
System.out.println("x (십진법) = " + x + " | (이진법) = " + Integer.toBinaryString(x));
System.out.println("y (십진법) = " + y + " | (이진법) = " + Integer.toBinaryString(y));
System.out.println("x & y (AND 연산) (십진법) = " + (x & y) +" | (이진법) = " + Integer.toBinaryString(x & y));
System.out.println("x | y (OR 연산) (십진법) = " + (x | y) + " | (이진법) = " + Integer.toBinaryString(x | y));
System.out.println("x ^ y (XOR 연산) (십진법) = " + (x ^ y)  + " | (이진법) = " + Integer.toBinaryString(x ^ y));
// int는 32bit이기때문에 앞의 28개의 0이 0의 보수인 1으로 변경되어 출력
System.out.println("~x (NOT 연산) (십진법) = " + ~x +" | (이진법) = " + Integer.toBinaryString(~x));
System.out.println("--------------------------------------");

int z = -32;
System.out.println("z (십진법) = " + z + " | (이진법) = " + Integer.toBinaryString(z));
System.out.println("z << 2 (십진법) = " + (z << 2) + " | (이진법) = " + Integer.toBinaryString(z << 2));
System.out.println("z >> 2 (십진법) = " + (z >> 2) + " | (이진법) = " + Integer.toBinaryString(z >> 2));

int k = 128;
System.out.println("k (십진법) = " + k + " | (이진법) = " + Integer.toBinaryString(k));
System.out.println("k << 2 (십진법) = " + (k << 2) + " | (이진법) = " + Integer.toBinaryString(k << 2));
System.out.println("k >> 2 (십진법) = " + (k >> 2) + " | (이진법) = " + Integer.toBinaryString(k >> 2));
System.out.println("~(k >> 2) + 1) (십진법) = " + (~(k >> 2) + 1 + " | (이진법) = " + Integer.toBinaryString(~(k >> 2) + 1)));

위 쉬프트 연산의 결과를 보면

z << n 의 경우에는 z * 2^n

z >> n 의 경우에는 z / 2^n

이라는 결과가 나오는 것을 알 수 있습니다.  

 

---

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

비트마스크를 이용한 집합 구현은 가장 대표적이고 자주 쓰이는 방법으로, "하나의 bit가 하나의 원소"를 의미하게 됩니다.

bit가 켜져 있으면(bit = 1) 해당 원소가 집합에 포함되어 있다는 의미이고, 꺼져 있으면(bit = 0) 포함되어 있지 않다는 의미를 갖습니다.

따라서 N비트 정수 변수라면 N개의 원소를 갖는 집합의 부분집합들을 모두 표현할 수 있습니다.

 

A라는 변수를 집합이라고 가정하고, 집합의 총원소의 개수를 10개라고 가정했을 경우 예시 (0번째 ~ 9번째 원소)

연산	사용 예시
공집합	A = 0;
꽉 찬 집합 구하기	A = (1 << 10) - 1;
원소 추가	A |= (1 << n);
원소 삭제	A &= ~(1 << n);
원소의 포함 여부 확인	if((A & (1 << n) == (1 << n))
원소의 토글(toggle)	A ^= (1 << n);
두 집합에 대해서 연산	A | B       →   A와 B의 합집합 A & B      →   A와 B의 교집합 A & (~B) →   A에서 B를 뺀 차집합 A ^ B      →   A와 B중 하나에만 포함된 원소들의 집합
집합의 크기 구하기	int bitCount(int A){   if(A == 0) return 0;   return A%2 + bitCount(A / 2); } 자바의 경우 내장 명령어 = Integer.bitCount(A)
최소 원소 찾기	int first = A & (-A);
최소 원소 지우기	A &= (A - 1);
모든 부분 집합 순회하기	for (int subset = A ; subset>0; subset = ((subset - 1) & A)){ }

 

• ▶ 공집합

기본적으로 공집합은 모든 bit가 0으로 꺼진 상태이기 때문에 상수 0이 공집합을 표현합니다.

 

• ▶ 꽉 찬 집합

꽉 찬 집합은 모든 bit가 1로 꺼진 상태이기 때문에 1111111111(2) 의 값으로 표현합니다.

(1 << 10) 의 이진법 값은 10000000000(2)로 여기서 -1을 하면 1111111111(2)가 됩니다.

 

• ▶ 원소 추가

원소에 해당하는 bit만 켜야하기 때문에 bit를 항상 1로 만들 수 있는 OR 연산을 이용합니다.

 

• ▶ 원소 삭제

A 집합에 n번째 원소의 포함 여부와 상관없이 해당 bit를 끄기 위해 AND 연산을 이용합니다.

EX : ) 

1 << n : n번째가 켜진 상태

^(1 << n) : n번째만 꺼진 상태

A &= ^(1 << n) : A 집합에 담긴 n번째 상태를 OFF

 

• ▶ 원소의 포함 여부 확인

n번째 원소가 포함되어 있는지 확인하려면, n번째 bit가 켜져 있는지 확인하면 됩니다.

if((A & (1 << n) == (1 << n)) 

 

• ▶ 원소의 토글

A 집합에 해당 원소가 빠져있는 경우에는 추가하고, 들어있는 경우에는 삭제하므로 XOR 연산을 이용합니다.

 

• ▶ 두 집합에 대한 연산

두 집합을 A와 B라고 한다면 비트연산자들을 통해서 A와 B의 교집합, 합집합, 차집합 등을 구할 수 있습니다.

 

• ▶ 집합의 크기 구하기

집합에 포함된 원소의 크기를 구한다면 A에서 켜진 bit의 수를 구하면 됩니다.

내장 명령어가 있으니 자바의 경우 Integer.bitCount(A)을 활용합니다.

 

• ▶ 최소 원소 찾기

집합에 포함된 가장 작은 원소 (index가 가장 작은 원소)를 찾는 방법입니다.

켜져 있는 bit 중에서 가장 오른쪽에 있는 bit를 찾습니다.

펜윅 트리 (Fenwick Tree)에서도 사용되는 기법입니다.

 

• ▶ 최소 원소 지우기

집합에 포함된 가장 작은 원소 (index가 가장 작은 원소)의 bit를 지우고 싶다면 A - 1과 AND 시킬 수 있습니다.

A에서 1을 빼주게 되면 가장 오른쪽에 있던 bit는 0이 되고 그보다 오른쪽에 있는 모든 bit들이 1이 됩니다.

 

• ▶ 모든 부분 집합 순회 

A의 모든 부분 집합을 탐색합니다.