비트마스크란?
: 정수의 이진수 표현을 자료구조로 쓰는 기법을 말한다
- 0과 1로 이루어진 형태의 정수 표현으로, 모든 자릿수가 0 또는 1이다.
- 이 특성을 활용해 각 자리를 배열의 인덱스, 자릿수를 boolean 값으로 활용한다. 0이면 '꺼져 있다'라고 하며, 1이면 '켜져 있다' 라고 한다.
비트마스킹은 세가지의 장점이 있다.
-
더 빠른 수행 시간
대부분의 삽입을 에 처리할 수 있다. -
더 적은 메모리 사용량
비트마스크는 정수를 배열로 확장시키기 때문에 메모리를 효율적으로 쓸 수 있다. -
더 간결한 코드
비트 연산자를 활용하면 대부분 반복문 없이 쓸 수 있어 더 간결하다.
비트 연산자
비트마스크를 활용하기 위해서는 비트 연산을 해야 한다.
다음의 연산자를 조합해 비트를 집합으로 표현한다.
a & b : AND 연산. 양쪽 비트 모두 켜졌을때만 1.
a | b : OR 연산. 양쪽 비트 중 하나라도 켜지면 1.
a ^ b : XOR 연산. 양쪽 비트 둘중 하나만 켜지면 1 .
~a : NOT 연산. 결과를 반전한다.
a << b : a를 b만큼 왼쪽으로 시프트.
a >> b : a를 b만큼 오른쪽으로 시프트.
- 공집합
int a = 0;공집합은 당연히 모든 비트가 꺼져 있으니 0을 입력하면 된다.
- 원소 개수가 n개인 꽉 찬 집합
int a = ( 1 << n ) - 1;일의 자리부터 n개의 1이 있는 형태가 된다.
- p번째 원소 추가
a |= ( 1 << p );p번째 비트에 OR 연산을 한다.
- p번째 원소 포함여부 확인
if ( a & ( 1 << p ) ) ...p번째 비트가 켜졌는지 알기 위해 AND 연산을 한다.
- p번째 원소 삭제
a &= ~( 1 << p );p번째 비트를 제외한 모든 비트가 1인 마스크를 만들고,
해당 마스크와 AND 연산을 통해 나머지 비트는 살리되 p번째 비트는 0으로 만든다.
- 원소 토글 (켜졌으면 끄고 꺼졌으면 켜기)
a ^= ( 1 << p );p번째 비트에 XOR 연산을 한다.
- 집합 연산
a | b // 합집합
a & b // 교집합
a & ~b// 차집합
a ^ b // 서로소 집합비트마스크끼리 연산도 가능하다.
이를 통해 교집합, 합집합 등을 만들 수 있다.
- 집합의 크기
int bitCount(int x){
if( x == 0 ) return 0;
return x % 2 + bitCount( x / 2 );
}
// 컴파일러별로 이미 만들어진 함수가 있으니 해당 함수를 찾아 쓸 것.십진법에서 자릿수를 구하는 것과 비슷한 원리이다.
라이브러리에 동일한 작업을 하는 함수가 있는지 찾아보는 것이 좋다.
- 최하위 원소 탐색
int onlyfirst = ( a & -a ); //0000100 형식으로 나옴2의 보수법을 사용하기 때문에 우측 끝 비트는 서로 값이 같다.
이를 이용해 최하위 비트만 남기고 모든 비트를 0으로 만든다.
- 최하위 원소 삭제
a &= ( a - 1 );최하위 원소 탐색과 마찬가지로 한다.
특정 마스크에서 1을 빼면 최하위 비트만 0이 된다.
그 이전 자리에 대한 변화는 원본 비트마스크가 전부 0이기 때문에 무시된다.
- 모든 부분집합 순회
for( int subset = a; subset; subset = ( ( subset - 1 ) & a )){
// 공집합은 방문 x.
// 예를 들어 subset = 1111이면,
// 1111, 1110, 1101, 1100, 1011, 1010, ...
}최하위 비트를 계속에서 제거해나가면서 순회한다.
직접 비트마스크를 찍어보면 어떤식으로 동작하는지 확실히 알 수 있다.
- 집합 내 원소의 개수 세기
int cnt = 0;
for( int mask = bitmask; mask != 0; mask >>= 1 ) cnt += (mask & 1);시프트 연산을 통해 최하위 비트만 비교해나간다.
비트 연산 시 다음에 유의해야 한다.
- 비트 연산자들은 등호 연산자보다 우선순위가 낮으므로, 반드시 괄호를 사용한다.
- C++의 경우 일반적인 상수는 32비트 정수로 취급한다.
64비트 정수와 같이 쓸 경우 상수 뒤에 접미사 ull을 붙여 64비트 정수임을 명시한다.
