[Algorithm] 비트마스크
in Algorithm on DataStructure, Dp, 비트마스크
비트마스크
- 정수의 이진수 표현을 자료 구조로 쓰는 기법을 비트마스크 라고 함.
- 엄밀하게 자료 구조라고 할 수는 없지만 종종 굉장히 유용하게 사용된다.
비트마스크의 장점
- 더 빠른 수행시간: 비트마스크 연산은 O(1)에 구현되는 것이 많기 때문에 적절히 사용할 경우 다른 자료 구조를 사용하는 것보다 훨씬 빨리 동작한다.
- 더 간결한 코드 : 다양한 집합 연산들을 반복문 없이 한 줄에 쓸 수 있어 굉장히 짧은 코드를 작성할 수 있다.
- 더 작은 메모리 사용량 : 비트마스크를 이용하는 코드들은 같은 데이터를 더 적은 메모리를 사용해 표현할 수 있다.
- 연관 배열을 배열로 대체 : 불린 값 배열을 키로 갖는 연관 배열 객체 map<vector
, int>를 사용한다고 합시다. 이때 비트마스크를 써서 같은 정보를 정수 변수로 나타내면 단순한 배열을 사용해 같은 정보를 나타낼 수 있다.
비트마스크를 이용한 집합의 구현
비트마스크의 가장 중요한 사용 사례는 집합을 구현하는 것. 이 표현에서 N비트 정수 변수는 0부터 N-1까지의 정수 원소를 가질 수 있는 집합이 된다. 이때 원소 i가 집합에 속해 있는지 여부는 2^^i을 나타내는 비트가 켜져 있는지 여부로 나타냅니다. 예를 들어 여섯개의원소를 갖는 집합 {1,4,5,6,7,9}을 표현하는 정수는 754임을 알 수 있다.
두 집합에 대해 연산하기
AND 연산(&)
대응하는 숫자가 모두 1일 경우 1을 반환
bin(0b1010011010 & 0b1101101100) # 0b1000001000, python에서는 앞에 '0b'를 붙여 이진수 표현 가능
OR 연산(|)
대응하는 숫자중 하나라도 1일 경우 1을 반환
bin(0b1010011010 | 0b1101101100) # 0b1111111110
XOR 연산(^)
대응하는 숫자가 서로 다를 경우 1을 반환
bin(0b1010011010 ^ 0b1101101100) # 0b111110110
SHIFT 연산(»,«)
a<<b 는 a의 비트를 b칸 만큼 왼쪽으로 밀어 내는 것, a>>b는 a의 비트를 b칸 만큼 오른쪽으로 밀어내는 것 가령 1(2)를 왼쪽으로 2비트 밀면 100(2) == 4 가 된다. 3비트를 밀게 되면 1000(2) == 8 이 된다.
bin(0b0010 << 2) # 0b1000
bin(0b1100 >> 2) # 0b11
NOT 연산(~)
- 비트 값을 반전시킨다. 그러나 파이썬에서의 NOT연산은 비트 연산이 아닌 정수 연산을 한다. 연산결과는 -(입력값 +1) 이 됩니다(1을 더하고 음수로 변환).
- 또한, python3 에서는 음수를 보여줄 때는 양의 정수를 표현하는 방식과 동일하게 이진수로 표현하고 부호만 따로 앞에 표기를 한다. 다만 비트 연산이 필요할 때만 2의 보수로 변환한다.
bin(~0b0011) # '-0b100'
bin(0b0101 & ~0b0011) # 연산 시 2의 보수로 변환한 '0b1100'이 된다. -> '0b100'
비트 연산 응용
원소 추가(n번째 수를 추가 하고자 할 때)
n = 3
print(bin(0b0010 | (1 << n))) # 0b1010
원소 제거(n번째 수를 제거 하고자 할 때)
n = 3
print(bin(0b1010 & ~(1 << n))) # 0b10
원소 조회
n = 3
print(bin(0b1010 & (1 << n))) # 0b1000
원소 토글
n = 3
print(bin(0b1010 ^ (1 << n))) # 0b10
