비트마스크(BitMask)

비트마스크란

• 비트마스크는 이진수를 사용하는 컴퓨터의 연산 방식을 사용하며, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말한다.
• 이진수는 0 또는 1을 사용하므로 하나의 비트가 표현할 수 있는 경우는 2 가지이다.

 

비트마스크의 장점

1. 수행 시간이 빠르다.

-> 비트마스크 연산은 비트 연산이기 때문에 O(1)의 시간복잡도로 구현되는 것이 많다. 따라서 다른 자료구조를 이용하는 것보다 훨씬 빠르게 동작한다. 다만, 비트마스크를 이용하는 경우에는 비트의 개수만큼 원소를 다룰 수 있기 때문에 연산 횟수가 적은 경우에는 속도에 큰 차이가 없지만, 연산 횟수가 늘어날수록 차이가 매우 커지게 된다.

2. 코드가 짧다.

-> 다양한 집합 연산들을 비트 연산자로 한 줄로 작성할 수 있기 때문에 반복문, 조건문 등을 이용한 코드보다 훨씬 간결한 코드를 작성할 수 있다.

3. 메모리 사용량이 적다. <- 비트마스크를 사용하는 가장 큰 이유

-> 하나의 정수로 매우 많은 경우의 수를 표현할 수 있기 때문에 메모리 측면에서 효율적이며, 더 많은 데이터를 미리 계산해서 저장해 둘 수 있다는 장점이 있다.

 

비트 연산자

1. AND 연산( & )

두 정수 변수 a와 b를 통해서 c를 생성한다고 가정하면, a와 b를 한 비트씩 비교하면서 해당 비트가 둘 다 켜져 있는 경우에만 c의 해당 비트를 켠다.

1010 & 1111 = 1010

2. OR 연산( | )

두 정수 변수 a와 b를 통해서 c를 생성한다고 가정하면, a와 b를 한 비트씩 비교하면서 해당 비트가 둘 중 하나 이상 켜져 있는 경우에만 c의 해당 비트를 켠다.

1010 | 1111 = 1111

3. XOR 연산( ^ )

두 정수 변수 a와 b를 통해서 c를 생성한다고 가정하면, a와 b를 한 비트씩 비교하면서 해당 비트가 둘 중 하나만 켜져 있는 경우에만 c의 해당 비트를 켠다.

1010 ^ 1111 = 0101

4. NOT 연산( ~ )

정수 하나를 입력받아서 켜져 있는 비트는 끄고, 꺼져 있는 비트는 켠다.

~1010 = 0101

5. Shift 연산 ( <<, >>)

정수 a의 비트들을 왼쪽 또는 오른쪽으로 원하는만큼 움직인다. 움직이고 나서 빈 자리는 0으로 채워지게 된다.

1010 << 2 = 101000
1010 >> 2 = 000010

 

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

연산	사용 예시
공집합과 꽉 찬 집합 구하기	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 ^ B -> A와 B 중에서 하나에만 포함된 원소들의 집합