비트마스크(bitmask)

Posted on

bitmasks

비트마스크 (bitmask)

정수의 이진수 표현을 자료 구조로 쓰는 기법

비트마스크 장점

  1. 더 빠른 수행 시간
    O(1)에 구현되는 것이 많다. 비트마스크를 사용할 수 있다는 말은 원소의 수가 많지 않다는 뜻이기 때문에 큰 속도 향상을 기대할 수는 없지만, 여러 번 수행해야 할 경우에는 작은 최적화도 큰 속도 향상을 가져올 수 있다.
  2. 더 간결한 코드
    다양한 집합 연산자들을 반복문 없이 한 줄에 쓸 수 있다.
  3. 더 작은 메모리 사용량
    더 적은 메모리를 사용할 수 있다는 말은 데이터를 미리 계산하여 저장해 둘 수 있으므로 캐시 효율이 좋다.
  4. 연관 배열을 배열로 대체
    연관 배열 객체 map<vector,int>가 있다고 하자. 이때 비트마스크를 이용해 정수 변수로 나타내면 단순한 배열 int[]를 사용할 수 있다.

용어 정의

  • 비트(bit) : 0과 1로 나타내는 이진수의 한 자리
  • 부호 없는 N비트 값 : 2의 0제곱 ~ 2의 N-1제곱
  • 최하위 비트 : 2의 0제곱에 있는 비트
  • 최상위 비트 : 2의 N-1제곱에 있는 비트
  • 비트가 켜져있다 : 1
  • 비트가 꺼져있다 : 0

c언어에서 크기별 별도의 정수타입

__int64_t  i64Val;    // 64bit 정수
__int32_t  i32Val;    // 32bit 정수
__int16_t  i16Val;    // 16bit 정수
__int8_t   i8Val;     // 8bit 정수

비트 연산자

  • AND연산 : a & b
  • OR연산 : a | b
  • XOR연산 : a ^ b
  • NOT연산 : ~a
  • 정수a를 왼쪽으로 b비트 시프트 : a « b
  • 정수 a를 오른쪽으로 b비트 시프트 : a » b

하기 쉬운 실수들

  1. 연산자 우선순위
    int c = (6 & 4 == 4);
// 4==4가 먼저 계산
int d = ((6 & 4) == 4);
// 6&4가 먼저 계산
  2. 상수의 자료형
    1은 부호 있는 32비트 상수로 취급되기 때문에 부호 없는 64비트 정수일 때는 접미사 ull을 붙여 주어야 한다.
    접미사 종류
    • U : unsigned int
    • L : long
    • UL : unsigned long
    • LL : long long
    • ULL : unsigned long long
  3. 부호 있는 정수형의 사용
    최상위 비트가 켜진 숫자는 음수를 표현한다. 32비트 전부 사용할 때, 음수를 오른쪽으로 시프트 하면 왼쪽 끝 비트들이 0이 아니라 1로 채워진다. 따라서 변수의 모든 비트를 쓰고 싶을 때는 부호 없는 정수형을 쓰는 것이 좋다.

비트마스크를 이용한 집합의 구현

N비트 정수 변수는 0부터 N-1까지의 정수 원소를 가질 수 있는 집합이 된다.
원소 i는 2의 i제곱을 나타낸다.
ex) {1, 4, 5, 6, 7, 9} = 1011110010(2) = 754

피자집 예제

0부터 19까지 번호를 갖는 20가지의 토핑이 있고, 주문 시 토핑을 넣기/넣지 않기를 선택할 수 있다.

공집합과 꽉 찬 집합 구하기

  • 토핑을 올리지 않은 피자(공집합) : 상수 0
  • 모든 토핑을 올린 피자(꽉 찬 집합) : 20개의 비트가 모두 켜진 상태 
    int fullPizza = (1 << 20) - 1;

    1«20은 이진수로 1뒤에 20개의 0이 있는 정수인데, 여기서 1을 빼면 20개의 비트가 모두 켜진 수를 얻는다.

원소 추가

비트마스크에서 원소를 추가한다는 것은 해당 비트를 켠다는 것이다.
토핑 목록에 페퍼로니를 추가하고 싶다고 하자.
페퍼로니의 번호가 p일때, 다음 코드로 집합 toppings에 추가할 수 있다.

toppings |= (1 << p);

//같은 표현
pepperoni = 1 << p;
toppings = toppings | pepperoni;

1을 왼쪽으로 p비트 시프트하면 p번 비트만 켜진 정수가 된다.
이 값과 toppings를 비트별 OR하면 해당 비트는 반드시 켜진다.
toppings에 이미 페퍼로니가 들어가 있을 경우 값이 변하지 않는다.

원소의 포함 여부 확인

집합 toppings에 페퍼로니가 포함되어 있는지를 다음 코드로 알 수 있다.

if(toppings & (1 << p) {
	printf("pepperoni is in");
}

&연산의 결과값이 0 또는 1<<p라는 점에 유의해라.
1 혹은 true가 반환된다고 생각하면 아래와 같은 코드를 작성하는 실수를 범하게 된다.

//제대로 동작하지 않음
if((toppings & (1 << p)) == 1) {
	printf("pepperoni is in");

원소의 삭제

페퍼로니가 토핑 목록에 없을 때도 동작하는 방법이다.

toppings &= ~(1 << p);

~연산자는 비트별 NOT연산을 수행하므로 ~(1<<p)는 해당 비트만 꺼지고 나머지는 다 켜진 숫자가 된다.
이 숫자와 비트별 AND연산을 하면 toppings의 나머지 비트는 유지되고 p번 비트는 항상 꺼지게 된다.

원소의 토글

p번째 토핑을 빼고 모두 넣는 경우 유용하다.
XOR연산이 토글 역할을 한다.

toppings ^= (1 << p);

두 집합에 대해 연산하기

두 개의 토핑 집합 a와 b에 대한 연산이다.

int added = a | b;		//a와 b의 합집합
int intersection = a & b;	//a와 b의 교집합
int removed = a & ~b;		//a에서 b를 뺀 차집합
int toggled = a ^ b;		//a와 b중 하나에만 포함된 원소들의 집합

집합의 크기 구하기

재귀 호출로 각 비트를 순회하면서 켜져 있는 비트의 수를 세는 방법이다.

int bitCount(int x) {
	if(x == 0) return 0;
	return x % 2 + bitCount(x / 2);