비트마스크

정의

이진수를 사용하는 컴퓨터의 연산 방식을 이용하여,  정수의 이진수 표현을 자료 구조로 쓰는 기법

 

비트 연산자

A	B	~A	~B	A & B	A | B	A ^ B
0	0	1	1	0	0	0
0	1	1	0	0	1	1
1	0	0	1	0	1	1
1	1	0	0	1	1	0

NOT(~) : 비트 값을 반전하여 변환 

AND(&) : 대응하는 두 비트가 모두 1일 때, 1 반환

OR(|) : 대응하는 두 비트 중 모두 1이거나 하나라도 1일 때, 1 반환

XOR(^) : 대응하는 두 비트가 서로 다를 때, 1 반환

SHIFT(>>, <<) : 왼쪽 or 오른쪽으로 비트 옮겨 반환

 

왼쪽 시프트 : A * 2^B

오른쪽 시프트 :  A  / 2^B

왼쪽 시프트 : 0001 -> 0010 -> 0100 -> 1000 :  1 -> 2 -> 4 -> 8
오른쪽 시프트 : 1000 -> 0100 -> 0010 -> 0001 :  8 -> 4 -> 2 -> 1

 

비트 마스크의 집합의 활용

다음과 같이 집합 개념 문제에서 활용이 가능하다. 백준 11723 집합 문제에서와 같이 비트 마스킹 집합을 구현하는 문제가 나온다.

우선 문제에서 x의 범위는 1~20까지이므로 0번째는 0, 길이가 21인 비트를 생각하면 된다.

 

원소 추가(add x)

• S에 num을 추가한다면, S의 num번 비트만 1로 만들어준다. (1 << num)은 num번째를 1로 세팅하는 거라고 생각하면 된다.

S |= (1 << num)

 

원소 삭제(remove x)

• S에서 num을 삭제한다면, S의 num번 비트를 0으로 만들어준다. 이렇게 하고 and 연산을 하면 num을 제외한 나머지 비트는 동일하게 유지할 수 있다.

S &= ~(1 << num)

 

원소 체크(check x)

• S에 num이 있으면 1, 없으면 0을 출력해주는 연산이다. and 연산은 두 비트가 모두 1이어야 1을 반환하는 성질을 이용하면 된다.

print(1 if S & (1 << int(op[1])) != 0 else 0))

 

원소 토글(toggle x)

• S에 num이 없다면 추가, 있다면 삭제하는 연산이다. xor 연산은 두 비트가 서로 다를 때 1을 반환하므로 토글을 구현할 수 있다.

S ^= (1 << num)

 

원소 비우기 및 채우기

• S의 모든 비트를 0으로 만들면 되고 반대로 채우려면 모든 비트를 1로 만들면 된다.

S = 0 # 비우기
S = (1 << 21) - 1 # 채우기

 

집합의 크기 구하기

• x % 2는 마지막 비트를 의미하고 x //2는 마지막 비트의 삭제를 의미한다.

def bitCount(x):
	if x == 0 : 
    	return 0
        return x % 2 + bitCount(x//2)

 

장점

• 수행 시간이 빠르다
  • bit 연산이기 때문에 대부분 O(1)로 구현된다. 하지만 비트의 개수만큼 원소를 다룰 수 있기에 연산횟수가 많아지면 많아 질수록 차이가 매우 커지게 된다.
• 코드가 짧다
• 메모리 사용량이 더 적다
  • 하나의 정수로 많은 경우의 수를 표현할 수 있기 때문이다. 예를 들어 bit가 3개면 각 bit당 0,1을 표현할 수 있으므로 2³가지의 경우를 표현 할수 있다.
  • 이런 이유로 메모리 측면에서 효율적이고 더 많은 데이터를 미리 계산해서 저장할 수 있다는 장점이 있다.

 

활용

• 집합의 구현, DP, 에라토스테네스의 체, 우선순위 큐 

 

 

출처:

https://velog.io/@1998yuki0331
https://gyoogle.dev/blog/algorithm/BitMask.html