[비트 마스크] bitmask

1. 비트 마스크

 

이진법 관련 연산들을 아주 빨리 할 수 있도록

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

(엄밀하게 자료 구조라고 할 수 없음)

 

2. 비트 마스크의 장점

 

- 더 빠른 수행 시간 : 대부분 연산은 O(1)에 구현된다.

- 더 간결한 코드: 다양한 집합 연산들을 반복문 없이 한 줄에 쓸 수 있기 때문

- 더 작은 메모리 사용량: 같은 데이터를 더 적은 메모리를 사용해 표현할 수 있다.

- 연관 배열을 배열로 대체: map같은 연관 배열 객체를 단순 배열을 사용해 같은 정보를 표현

 

3. 비트 연산자

- AND연산: 두 비트가 모두 1인 경우. 1반환

- OR연산: 두 비트중 하나라도 1인 경우. 1반환

- XOR연산: 두 비트중 하나만 1인 경우 (1의 개수가 홀수). 1반환

- NOT연산: 정수 하나를 받아 각 비트를 1인 경우 0. 0인 경우 1 반환.

- shift연산: 정수 하나를 받아 왼쪽 또는 오른쪽으로 원하는 만큼 움직임

 

- c++에서 제공하는 비트 연산자들

AND	a & b
OR	a | b
XOR	a ^ b
NOT	~ a
left shift b bit	a << b
right shift b bit	a >> b

- 유의할 점들: & | ^ 연산자들의 우선순위는 ==, != 보다 낮음.

                   64비트 정수를 비트마스크로 사용할 때 발생하는 오버플로

                   부호 있는 정수형의 사용 -> 모든 비트를 다 쓰고 싶을 때는 부호 없는 정수형으로

                   N비트 정수를 N비트 이상 왼쪽으로 시프트하면 0이 나오지 않음, 결과가 정의되지 않음.

 

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

 

N 비트 정수 변수 = 0~N-1 의 정수 원소를 가질 수 있는 집합

 

i가 집합에 속해있는지 여부 -> 2^i을 나타내는 비트가 켜져 있는지?

 

공집합과 꽉 찬 집합 구하기:

int full = (1<<20)-1;

상수 0: 공집합

1<<20 -1 : 1뒤에 0이 20 개에 -1을 하게 되면 1이 20개 즉, 비트가 모두 켜진 수

 

원소추가: 

집합의 가장 기초적인 연산

원소를 추가한다는 것은 해당 비트를 1로 바꾼다는 것을 의미한다.

집합 S의 i번째 비트를 1로 바꾸기:

S |= (1<<i);

 

원소의 포함 여부 확인:

if(S & (1<<i))

&연산으로 결과 값이 0 또는 1<<i 가 나온다.

 

원소의 삭제:

S &= ~(1<<i);

NOT을 사용하여 삭제하고 싶은 비트만 0으로 만든 뒤

AND 연산하면 결국 i번째 원소가 삭제된다.

 

원소의 토글:

S ^= (1<<i);

토글(toggle): 비트가 1이면 0으로, 비트가 0이면 1로 => XOR연산

 

 

두 집합에 대해 연산하기(합집합, 교집합, 차집합)

int add = (a|b); //합집합
int intersection = (a&b) // 교집합
int removed = (a&~b); //차집합
int toggled = (a^b); //하나만 포함된 원소들의 집합

집합의 크기와 상관없이 상수시간안에 수행된다.

 

집합의 크기 구하기

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

각 비트를 순회하면서 1인 비트를 직접 세는 방법

아래는 S의 1인 비트의 수를 구하는 내장 명령어이다.

 

gcc/g++ : __builtin_popcount(S)

Visual c++: __popcnt(S)

java: Integer.bitCount(S)

 

최소 원소 찾기

 

정수의 이진수 표현에서 끝에 붙어 있는 0은 몇개인가?

밑의 연산들은 1인 비트가 있는 최하위 비트의 번호를 반환한다.

 

gcc/g++ : __builtin_ctz(S)             ... S= 0일때 정의되지 않음.

Visual c++: _BitScanForward(&index, S)

java: Integer.numberOfTrailingZeros(S)

 

최하위 비트 직접 구하기

int firstS = (S & -S);

비트의 위치를 구한 뒤 1을 왼쪽으로 시프트하는 대신 음수와 &연산을 사용하여 쉽게 얻을 수 있다.

 

컴퓨터가 음수를 표현하기 위해 2의 보수(Two's complement)를 사용한다는 점을 이용한 것이다.

 

2의 보수를 사용하는 시스템에서는 음수 -S를 표현하기 위해서 

S에 비트별 NOT연산을 적용하고 그 결과에 1을 더한다.

 

S에서 켜진 최하위 비트가 2^i라고 하면

마지막 i+1 자리는 1 뒤에 i개의 0이 있는 형태여야한다.

이 S에 비트별 NOT연산을 적용하면

마지막 i+1자리는 0 뒤에 i개의 1이 있는 형태가 되고.

여기에 1을 더하면 1과 i개의 0이 있는 형태가 된다.

 

2^i보다 상위 비트들에는 NOT연산이 적용된 상태이므로

AND연산하게 되면 결국 최하위 비트만을 얻을 수 있다.

 

펜윅트리에서 유용하게 사용된다.

 

최소 원소 지우기

S &= (S - 1);

 

최소 원소를 얻은 뒤, 그 원소를 지우는 것보다 훨씬 간결하다.

 

S-1의 이진수 표현을 생각해보자.

S-1의 이진수 표현은 S에서 켜져있는 최하위 비트를 끄고

그 밑의 비트들을 전부 켠 것이다. 

 

그래서 AND연산하게되면 최하위 비트와 그 이하 비트들은 0이된다.

 

이 방법은 어떤 정수가 2의 거듭제곱 값인지 확인할 때도 사용한다.

거듭제곱 값들은 1인 비트가 하나이기때문에 

지웠을때 0 이 되어버린다.

 

모든 부분 집합 순회하기

for(int subset = S; subset; ((subset-1) & S)) {
}

1을 빼면 켜져 있던 최하위 비트가 꺼지고, 그 밑의 비트들은 전부 켜지게된다.

그리고 S와 &연산을 통해 원래 속해 있지 않은 비트들을 전부 꺼버린다.

 

 

비트마스크의 응용

에라토스테네스의 체

 

unsigned char sieve[(MAX_N + 7) / 8];

이 배열은 MAX_N/8 바이트만을 써서 MAX_N개의 원소를 갖는 불린 값 배열을 구현한다.

 

즉, k번의 원소가 참인지를 알기 위해서 [k/8]의 원소의 k%8 번째 지트가 켜져 있는지를 확인하는 것이다.

 

정수를 3비트 오른쪽 시프트하는것은 8로 나누는것과 같고,

7과 AND연산하는 것은 8로 나눈 나머지를 구하는것과 같다.( 8즉 4번째 비트 이상부터는 8로 다 나누어짐)

밑의 코드는 원소 삭제와 원소의 포함 여부를 이용한 것이다.

//k가 소수인지 파악한다
inline bool isPrime(int k) {
    return sieve[k>>3]&(1<<(k&7));
}
//k가 소수가 아니라고 표시한다.
inline void setComposite(int k) {
   sieve[k>>3] &= ~(1<<(k&7));
}
   

15퍼즐 상태 표현

 

15퍼즐의 상태는 0부터 15까지 숫자가 들어 있는 4*4 크기의 배열로 표현할 수 있다.

 

각 숫자는 4비트로 표현할 수 있고, 16개의 숫자가 있기 때문에 비트마스크를 사용하면 

64비트 정수 하나로 표현할 수 있다.

 

크기 16*8 인 char배열에 비해 크기가 절반으로 줄어들고, 

상태 전체를 워드 하나에 넣을 수 있다는 것 또한 장점이다.

 

typedef unsigned long long uint64;
//mask의 index위치에 쓰인 값을 반환한다.
int get(uint64 mask, int index) {
    return (mask >> (index<<2))&15;
}
//mask의 index위치를 value로 바꾼 결과를 반환한다.
//먼저 1111를 mask에 서 빼어 0000으로 만든다음 value를 추가한다.
uint64 set(uint64 mask, int index, int64 value) {
    return (mask & ~(15ll << (index << 2))) | (value << (index << 2));
}

 

O(1) 우선순위 큐

 

우선순위 큐는 포함된 원소 중에서 우선순위가 가장 높은 원소를 빠르게 찾아낼 수 있는 자료 구조이다.

이 우선순위 큐에 자료를 추가하거나 삭제하는 작업에는 N개의 원소가 있을 때 O(lgN)의 시간이 걸린다.

 

그런데 우선순위가 특정 범위로 제한되어 있을 경우 비트마스크를 이용하면 

모든 작업을 O(1)에 할 수 있는 우선순위 큐를 만들 수 있다.

 

예를 들면 우선순위가 1~140 인 정수가 있다고하면 (겹치지 x)

부울 배열 140개 대신 64비트 3개로 표현하여

첫 번째 비트를 찾는 연산을 이용하여 가장 우선순위가 높은 원소가

어디에 있는지 찾을 수 있다. 

 

 

 

- 알고리즘 문제해결전략 575p