비트마스크

PARK JOOCHANG·2023년 12월 4일

Algorithm

목록 보기

5/9

Bit Mask

비트 마스크는 알고리즘이 아닌 하나의 기법으로 정수를 이진수로 표현 하고, 비트 연산 으로 문제를 해결하는 방법이다.

예를 들어 알파벳이 아래와 같이 있다고 가정해보자.

a	b	c	d	e	f
1	0	1	0	1	0

이 중 a, b, c를 가지고 있다면 위와 같이 표현할 수 있다. 가지고 있는 경우를 1, 가지고 있지 않은 경우를 0 으로 표현 한 것이 비트 마스크이다.

그리고 비트 마스크의 상태를 변경하기 위한 연산을 비트 연산 으로 수행할 수 있다.

장점
1. 수행 시간이 빠르다.
- bit 연산이기 때문에 O(1)에 구현되는 것이 많다. 따라서 다른 자료구조를 사용하는 것보다 훨씬 빠르게 동작한다.

코드가 짧다.
- 다양한 집합 연산들을 비트연산자 한 줄로 작성할 수 있기 때문에 반복문, 조건문을 이용한 코드보다 훨씬 간결하다.
메모리 사용량이 적다.
- 비트마스크를 이용하는 가장 큰 이유이다.
- 예를 들어 bit가 10개인 경우 2^10 가지 경우를 10bit 이진수 하나로 표현 가능하다.
- 하나의 정수로 매우 많은 경우의 수를 표현할 수 있기 때문에 메모리 측면에서 효율적이다.
- 많은 데이터를 미리 계산해서 저장해 둘 수 있는 장점이 있다. (DP에 매우 유용)

비트마스크를 이용하기 위해서, 정수 변수를 비트 별로 조작할 수 있는 비트연산자를 사용한다. 두 정수 변수 또는 하나의 정수 변수를 이용하여 새로운 값을 만들어 내는 것이 목적이다.

AND 연산

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

C에서 제공하는 연산자 기호는 ' & '이다.

(ex. c = a & b)

00001111 & 00010101 = 00000101

OR 연산

AND 연산과 같은 방식으로, 해당 비트가 둘 중 하나라도 켜져 있는 경우에 c의 해당 비트를 켠다.

C에서 제공하는 연산자 기호는 ' | (shift + ) ' 이다.

(ex. c = a | b)

00001111 | 00010101 = 00011111

XOR 연산

마찬가지로 같은 방식이며, 해당 비트가 둘 중 하나만 켜져 있는 경우에 c의 해당 비트를 켠다.

C에서 제공하는 연산자 기호는 ' ^ ' 이다.

(ex. c = a ^ b)

00001111 ^ 00010101 = 00011010

NOT 연산

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

C에서 제공하는 연산자 기호는 ' ~ ' 이다.

(ex. c = ~a)

~00001111 = 11110000

시프트(shift) 연산

시프트 연산자는 정수 a의 비트들을 왼쪽 또는 오른쪽으로 원하는 만큼 움직인다. 움직이고 나서 빈자리는 0으로 채워지게 된다. 예를 들어 13 (1101)을 오른쪽으로 1bit 움직인다고 하면, 6 (0110)이 되는 것이다.

C에서 제공하는 연산자 기호는 ' << ' 또는 ' >> ' 이다.

(ex. c = (a << 1) )

00001010 << 2 = 101000
00001010 >> 2 = 000010

ex) 방문한 알파벳인지 체크할 때 사용

int bitmask = 0;  
// 방문하지 않은 알파벳  
char[] c = {'A', 'B', 'C', 'E', 'G', 'C'};  

for (char value : c) {  
	if ((bitmask & 1 << value - 'A') == 0) {  
		bitmask = bitmask | 1 << value - 'A';  
	} else {  
		System.out.println(value + ": 이미 방문한 알파벳");  
	}  
}