[자료구조] 비트마스크(bitmask)_I

비트마스크란?

컴퓨터는 모든 정수형변수를 이진수로 표현합니다. 이 때 이진수의 한 자리를 비트(bit)라고 부릅니다.

비트는 0 또는 1의 값을 가지며 컴퓨터가 표현하는 모든 자료의 근간이 됩니다.

이러한 이진수표현을 자료구조로 사용하는 기법을 비트마스크(BitMask) 라고 부릅니다.

비트마스크는 엄밀하게 ㅏ료구조라고 할 수는 없지만 굉장히 유용하게 사용 됩니다.

 

비트마스크를 왜 사용하는가?

1. 더 빠른 수행시간 : 비트마스크 연산은 O(1)으로 구현이 됨, 따라서 여러번 수행하는 경우에는 작은 최적화로 속도 향상을 가져올 수 있음

2. 더 간결한 코드 : 반복문 없으 한줄에 사용하므로 짧은 코드를 작성

3. 더 작은 메모리 사용 : 32비트형 정수형 자료형에 32개의 0/1 형태의 정보를 저장

 

비트연산

1. 비트연산의 우선순위

산술연산(덧셈,뺄셈,곱셈,나눗셈) > 쉬프트연산( <<,>>) > 관계연산(크기비교) > 비트연산(&,|^) > 논리연산(&&,||)

- 가능하면 괄호로 우선순위를 지정하자.

2. 비트연산

 

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

3. 특정 위치의 원소가 1 인지 판단하기

bool isBitSet(unsigned long long a, int b) {
    return (a&(1ull<<b)) > 0
} 
 

※ 주의사항 

- 1이 32비트 상수로 취급 되므로 b가 32bit 이상이면 오버플로 발생

- 1ull(64비트 상수로 반드시 표시할것)

4. 오른쪽 b 의 갯수만큼 모든 비트를 1로 채우기

- (1ull <<b ) - 1 : b가 3이라고 하면 3비트만큼 1을 왼쪽으로 쉬프트 하면 1000 이 된다. 여기서 1을 빼면 111 이 되는 원리이다.

5. a의 오른쪽에서 b 위치의 비트를 1로 셋팅하기(비트마스크는 항상 오른쪽이 0번째 이다.)

unsigned long long bitSetting(unsigned long long a, int b) {
    return a |= (1<<b);
}
 

6. a의 오른쪽에서 b 위치의 비트가 1인지 체크하기(비트마스크는 항상 오른쪽이 0번째 이다.)

bool isBitSetting(unsigned long long a, int b) {
    //동작하지 않는 코드 return (a & (1ull << b))==1;
    return a & (1ull << b);
}

7. a의 오른쪽에서 b 위치의 비트를 0으로 셋팅하기(비트마스크는 항상 오른쪽이 0번째 이다.)

unsigned long long bitRemove(unsigned long long a, int b) {
    //return a -= (1ull<<b) 해당 비트가 0 이면 오류 발생 
    return a &=~(1ull<<b);
}

8. a의 오른쪽에서 b 위치의 비트를 토글( 0 이면 1로 1이면 0으로)

unsigned long long bitToggle(unsigned long long a, int b) {
    return a ^=~(1ull<<b);
}

9. a와 b의 합집합(두개중 하나라도 1이면 1로 만들어 주는 함수)

unsigned long long bitUnion(unsigned long long a, unsigned long long b) {
    return a|b;
}

10. a와 b의 교집합(두개의 비트 중 두개가 모두 1인 경우만 1로 만들어 주는 함수)

unsigned long long bitIntersection(unsigned long long a, unsigned long long b) {
    return a&b;
}

11. a에서 b를 뺀 차집합

unsigned long long bitDifference(unsigned long long a, unsigned long long b) {
    return a & ~b;
}
 

12. a와 b 중에 하나만 포함된 집합

unsigned long long bitExclusive(unsigned long long a, unsigned long long b) {
    return a ^ b;
}

13. 집합에서 1의 갯수 구하기

int bitCount(unsigned long long a){
    if(a==0) return 0;
    return a%2 + bitCount(a/2);
} 
 

또는 Gcc/g++ 에서 __builtin_popcount(a) 함수를 사용할 수도 있다.(내장함수 사용하는 것이 속도가 더 빠름)

14. 최소원소 찾기 : 오른쪽에서 처음 만나는 1의 위치 찾기

int firstBitPosition(unsigned long long a) {
    if(a==0) return -1;
    unsigned long long first = a & -a;
    int cnt = 0;
    while(1)
    {
        if(first & (1ull<<cnt) ) return cnt;
        cnt++;
    }
}
 

unsigned long long firstBitRemove(unsigned long long a) {
    return a &= -a;
}
 

※ 해당 숫자가 2의 거듭제곱인지 판별하기가 쉽다. 만약 첫번째의 1의 위치를 제거 후 0 이라면 1의 갯수가 하나이므로 2의 거듭제곱이 된다.

 

 

이 자료는 학생들과 비트마스크는 무엇이고 어떻게 사용되는지 알아 보기 위해 작성된 문서입니다.

 

오늘도 최선을 다하는 우리 학생들을 응원합니다.

 

인천 서구 검단신도시 원당컴퓨터학원