비트마스크(Bit Mask) 알고리즘 장점 및 연산자 사용 방법

비트마스크(BitMask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여 정수의 이진수 표현을 자료 구조로 쓰는 기법

 

✅ 이진수 0 또는 1을 이용하므로 하나의 비트(Bit)가 표현할 수 있는 경우는 두 가지이다.

 

비트마스크 장점

1. 빠른 수행시간

비트마스크 연산은 bit 연산이기 때문에 O(1)에 구현되는 경우가 많다.

 

2. 짧은 코드

다양한 집합 연산들을 비트연산자로 한 줄로 작성할 수 있다.

 

3. 적은 메모리 사용량 ★

bit가 5인 경우에 $2^{5}$ 개의 경우를 표현할 수 있다. 하나의 정수로 많은 경우의 수를 표현할 수 있기 때문에 메모리 측면에서 효율적이다.

 

비트 연산자

연산	연산자	설명
AND	&	두 개의 비트가 모두 1인 경우, 1을 반환함
OR	|	두 개의 비트 중 하나라도 1인 경우, 1을 반환함
XOR	^	두 개의 비트 중 한 개만 1인 경우, 1을 반환함
NOT	~	1인 경우 0을 반환, 0인 경우 1을 반환
Left Shift	<<	지정한 수 만큼 비트를 왼쪽으로 이동 (빈 자리는 0으로 채움)
Right Shift	>>	지정한 수 만큼 비트를 오른쪽으로 이동 (빈 자리는 0으로 채움)

 

1. AND, OR, XOR, NOT 연산자

 

 

2. Left Shift 연산자.   a << 1

 

3. Right Shift 연산자.   a >> 1

 

 

✅ 비트 연산자 사용 시에 주의할 점

1. 비교 연산자보다 우선순위가 낮기 때문에 생각한 답이 나오지 않을 수 있다. 비교 연산자와 함께 사용할 경우에는 괄호를 씌워주는 것이 좋다.

 

2. 오버플로우가 발생할 수 있다. 

64비트 정수를 비트마스크로 사용할 때 오버플로우가 발생한다. 이런 경우에는 1 뒤에 64비트 정수임을 나타내는 ull(unsinged long long)을 붙여서 사용하면 된다.

 

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

연산	예시
공집합과 꽉 찬 집합 구하기	A = 0; A = (1 << K) - 1;
원소 추가	A |= (1 << K);
원소 삭제	A &= ~(1 << K);
원소의 포함 여부 확인	if (A &= (1 << K);
원소의 토글	A ^= (1 << K);
두 집합에 대해서 연산	A  | B         합집합 A & B        교집합 A & (~B)    A에서 B를 뺌 A ^ B         A와 B중 하나에만 포함된 원소들의 집합
최소 원소 찾기	A & (-A);
최소 원소 지우기	A &= (A - 1);

 

1. 공집합과 꽉 찬 집합 구하기

: 공집합은 모두 0인 상태를 말하므로 A=0, 반대로 꽉 찬 집합은 모두 켜진 상태이므로 원소가 K-1개인 꽉 찬 집합을 구하려면 $2^{K}$ 에서 -1 해주면 된다.

 

ex) 10000 -1 → 01111 (4개의 원소를 가진 꽉 찬 집합)

 

2. 원소 추가

: A 집합에 특정 원소를 추가하려면 해당 bit가 1이 되어야 한다. 즉, OR 연산자를 이용해야 함.

 

3. 원소 삭제

: A 집합에 특정 원소를 삭제하려면 해당 bit가 0이 되어야 한다. 무조건 0이 되어야 하므로 AND 연산자와 NOT 연산자를 함께 이용해야 함.

 

ex) 1 << K 는 K번째 bit만 1이 된다. 여기에 NOT 연산자를 사용하면 K번째 bit만 0이 된다.

      이 상태로 AND 연산자를 사용하면 K번째 bit만 0으로 변경되고, 나머지는 변화가 없다.

 

4. 원소의 포함 여부

: A 집합에 특정 원소가 포함되어 있는지 확인할 수 있다. 반환되는 값이 0이면 없다는 뜻이고, 1 이상이면 값이 포함되어있다는 뜻이다.

 

5. 원소의 토글

: A 집합에 원소가 포함되어있는 경우 삭제하고, 포함되어있지 않은 경우 추가해야 한다. 즉, XOR 연산자를 이용해야 함.

 

6. 최소 원소 찾기

: A 집합에 가장 작은 값을 찾는 방법이다. 즉, 1의 값을 가진 bit 중에 가장 오른쪽에 있는 것을 찾는 것이다. 

 

컴퓨터는 2의 보수를 이용해서 음수를 표현한다. 그렇기 때문에 ~A를 표현하기 위해 ~A + 1을 한다.

ex) 101000 에 NOT 연산자를 사용하면 010111 + 1 이 되어서 011000 이 된다.

      오른쪽에서부터 i개의 0이 존재하므로 i+1번째가 최소 원소의 위치가 된다.

 

7. 최소 원소 지우기

ex) 101000 에 -1을 해주면 100111 이 된다.

      여기서 AND 연산자를 이용하면 100000 이 되므로 최소 원소가 삭제된 것을 볼 수 있다.