비트마스킹

안녕하세요 laeto입니다.

이번 글에서는 비트마스크에 대해 다뤄보도록 하겠습니다.

 

비트 마스크란?

컴퓨터의 최소 연산 단위는 bit입니다. bit는 이진수를 나타내기 위해 0과 1로만 이루어져 있죠.

우리는 이 비트 연산을 이용하여 문제를 빠르게 풀 수 있습니다.

 

예를 들어, 많은 알고리즘 문제에서 방문을 체크하는 리스트가 존재할 수 있습니다. 가령 10곳을 우리가 방문 체크해야 한다면 기존에는 아마 아래처럼 리스트를 이용하여 확인할 수 있습니다.

 

visited = [False] * 10

 

하지만 비트마스크 기법을 이용한다면 똑같이 표현할 수 있습니다.

 

visited = 0b0000000000

 

비트마스크에서 각 비트는 하위 주소(오른쪽)부터 인덱스를 세면 됩니다. 예를 들어 4번째 도시를 우리가 방문했다고 하면 현재 비트는 visited=0b0000001000으로 표현할 수 있다는 것이죠.

 

따라서 비트 연산을 하게 되면 장점이 있을까요?

 

1. 비트연산을 통해 삽입, 삭제, 조회 등이 간단해집니다.
2. 더 간결하게 코드를 짤 수 있습니다.
3. 더 빠른 연산이 가능합니다.
4. 비트마스크를 이용한 정수 표현으로 다이나믹 프로그래밍 문제를 해결할 수 있습니다.

비트 연산

AND 연산(&)

대응하는 숫자가 모두 1일 경우 1을 반환합니다.

bin(0b1010011010 & 0b1101101100) # 0b1000001000

OR 연산( | )

대응하는 숫자 중 하나라도 1일 경우 1을 반환합니다.

bin(0b1010011010 | 0b1101101100)  # 0b1111111110

XOR 연산 (^)

대응하는 숫자가 서로 다를 경우 1을 반환합니다.

bin(0b1010011010 ^ 0b1101101100)  # 0b111110110

SHIFT 연산(>>, <<)

a << b는 a의 비트를 b칸 만큼 왼쪽으로 밀어 내는 것이고, a >> b는 a의 비트를 b칸 만큼 오른쪽으로 밀어내는 것 입니다.

bin(0b0010 << 2)  # 0b1000
bin(0b1100 >> 2)  # 0b11

NOT 연산 (~)

비트 값을 반전시킵니다.

bin(~0b0010 << 2)  # 0b1101

 

비트 연산 응용

원소 추가

n번째 수를 추가하고자 할 때

n = 3
print(bin(0b0010 | (1 << n)))  #  0b1010

원소 제거

n번째 수를 제거 하고자 할 때

n = 3
print(bin(0b1010 & ~(1 << n)))  #  0b10

원소 조회

n번째 수가 있나 없나 확인 할 때 (0이면 없고, 1 이상이면 있는 것)

n = 3
print(bin(0b1010 & (1 << n)))  #  0b1000

원소 토글

n번째 수를 켜져 있으면 끄고, 꺼져 있으면 켬

n = 3
print(bin(0b1010 ^ (1 << n)))  #  0b10