비트마스크(1)

아래 내용은 본인이 종만북을 공부한 후에 나중에 다시 공부할 때 보기 위해 정리한 것임.

1. 비트마스크란?

현대의 모든 CPU는 이진수를 이용해 모든 자료를 표현한다. 그래서 이진법 관련 연산(비트 연산)은 아주 빨리 수행된다고 한다.

이와 같은 특성을 이용해 정수의 이진수 표현을 자료 구조로 사용하는 방법이 있는데 이를 비트마스크라고 한다.

 

하나 예를 들자면,

 

A = {1, 3, 5, 7}

 

위와 같은 정수가 담겨 있는 집합 A를 표현하고자 할 때, 일반적으로 C++에서는

 

bool set[8] = {0, 1, 0, 1, 0, 1, 0, 1};

 

boolean 타입의 배열의 사용하여, 해당하는 수의 인덱스 값의 원소를 1로 만들어주고, 나머지는 0으로 만들어주는 형식으로 저장한다.

 

이제 똑같은 집합을 배열이 아니라 비트마스크로 표현해 보자.

 

unsigned char set[1] = 170; // 1010 1010

 

저런 식으로 이진수 표현을 활용해서 집합을 나타낼 수가 있다.

예시에서 사용했지만, 이처럼 비트마스크의 가장 중요한 사용 사례는 집합을 구현하는 것이다. 비트마스크로 집합을 구현하게 되면,

비트 연산만으로도 집합을 쉽게 조작할 수 있다.

 

1. 공집합과 꽉 찬 집합 구하기

2. 집합에 원소 추가

3. 원소의 포함 여부 확인

4. 원소의 삭제

5. 원소의 토글

6. 집합의 크기 구하기

7. 집합에서 가장 작은 원소 찾기

8. 가장 작은 원소 지우기

9. 모든 부분 집합 순회하기

 

종만북에 있는 예시들을 적어 보았다. 왠만한 집합 연산은 모두 비트연산으로 구현이 가능하다.

 

 

2. 비트연산(c++ 기준)

비트마스크를 사용하기 위해서는 정수 변수를 비트별로 조작할 수 있는 비트 연산들을 알고 있어야 한다.

 

아래 비트 연산들의 예시이다.

 

#include <iostream>
using namespace std;

int main()
{
    unsigned char a = 3;  // 0000 0011
    unsigned char b = 24; // 0001 1000
	
    cout << ~a << '\n';       // 1111 1100 NOT(비트를 뒤집는다)
    cout << (a & b) << '\n';  // 0         AND
    cout << (a | b) << '\n';  // 27        OR
    cout << (a ^ b) << '\n';  // 27        XOR
    cout << (a << 3) << '\n'; // 24        왼쪽으로 3만큼 시프트(2의 3승을 곱함)
    cout << (b >> 2) << '\n'; // 6         오른쪽으로 2만큼 시프트(2의 제곱으로 나눔)
    return 0;
}

 

참고로 비트 연산자의 연산자 우선 순위는 ==, !=와 같은 비교연산자보다 낮다.

 

int num = (6 & 4 == 4);

 

이렇게 사용하게 되면 4==4가 먼저 계산되고 이 결과인 1이 6과 AND연산을 수행하게 되어 c는 0이 된다. 이런 사소한 실수를 방지하기 위해 비트연산을 사용할 때에는 괄호로 묶어서 사용하자.

 

 

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

1. 공집합

먼저 공집합은 모든 비트가 0인 경우이니, 그냥 상수 0이다.

 

unsigned char set = 0;	// 0000 0000

 

 

2. 꽉 찬 집합

모든 비트가 1인 경우이다.

 

집합의 원소의 개수가 20개인 집합이 있다고 하자. 그리고 20개의 비트가 모두 1이라면

 

unsigned int set = (1 << 20) - 1;

 

이렇게 표현하면 된다. 1 << 20을 하게 되면 이진수로 1뒤에 20개의 0이 있는 정수가 된다. 여기서 1을 빼면 20개의 1을 가진 수를 얻는다.

 

 

3. 원소 추가

비트마스크를 사용한 집합에서 원소를 추가한다는 것은 해당 위치의 비트를 1로 만들어 준다는 의미이다.

p 번째에 있는 비트를 1로 만들어 주는 예시 코드이다.

 

set = set | (1 << p);

 

1 << p 는 p 번째 비트만 1이고 나머지는 0인 이진수를 의미하는데, 원래 있던 집합과 OR연산을 하게 되면 p번째 비트가 1이 된다.

 

 

4. 원소 삭제

비트마스크를 사용한 집합에서 원소를 삭제한다는 것은 해당 위치의 비트를 0으로 만들어 준다는 의미이다.

p번째에 있는 비트를 0으로 만들어 주는 예시 코드이다.

 

set = set & ~(1 << p);

 

~(1 << p)는 p번째 비트는 0이고 나머지 비트는 모두 1인 이진수를 의미한다.

원래 있던 집합과 AND연산을 하게 되면 p번째 비트만 0으로 바뀌고 나머지는 그대로 남게된다.

 

 

5. 원소의 유무 확인

 

p번째에 원소가 있는지 알아보는 예시코드 이다. p번째 비트가 1인지 확인해주면 된다.

 

if(set & (1 << p)) cout << "원소가 존재";

 

set & (1 << p)를 보면 만약 p번째에 원소가 존재하면 1을, 존재하지 않으면 0을 리턴하게 된다.

 

 

6. 원소의 토글

p번째 비트를 뒤집어 준다. XOR연산을 이용하여 쉽게 구현할 수 있다.

 

set = set ^ (1 << p);

 

 

7. 집합의 크기 구하기

비트마스크를 이용한 집합의 원소의 개수는 1의 개수를 의미하게 되는데, gcc 컴파일러에 내장함수가 존재한다.

다음은 정수를 이진수로 나타내었을 때 1의 개수를 세주는 함수이다.

 

#include <iostream>
using namespace std;

int main()
{
    unsigned char a = 3;	// 0000 0011  -> 1이 두개 있음.
    cout << __builtin_popcount(a) << '\n';  // 2
    // __builtin_popcount() 함수는 헤더파일을 추가 안해도 됨.
    return 0;
}

 

 

8. 집합에서 가장 작은 원소 찾기

gcc 컴파일러에는 가장 처음 1이 등장할 때 까지의 0의 개수를 세주는 함수가 존재한다. 정수 100을 예시로 들어보겠다.

 

#include <iostream>
using namespace std;

int main()
{
    unsigned char a = 100;            // 0110 0100
    cout << __builtin_clz(a) << '\n'; // 왼쪽에서부터 보면 처음 1이 나올 때 까지 0이 1개 있다.  1을 리턴
    cout << __builtin_ctz(a) << '\n'; // 오른쪽부터 보면 처음 1이 나올 때 까지 0이 2개 있다. 2를 리턴
    return 0;
}

 

작은 원소를 찾을 때에는 ctz함수를 사용하게 되는데, 0의 개수를 인덱스로 바꿔서 생각해보면 쉽게 가장 작은 원소를 찾을 수 있다.

 

참고로 clz는 count leading zero, ctz는 count trailing zero 정도로 기억하면 되지 않을까 한다.

 

 

9. 가장 작은 원소 지우기

바로 예시코드를 먼저 보고 설명하겠다.

 

set = set & (set - 1);

 

우선 set - 1을 먼저 생각해보자.

이진수에서 1을 빼게 되면 가장 마지막에 있던 비트 1은 0 으로 변하고 그 밑의 비트는 모두 1이된다.

이것을 원래의 비트마스크 집합과 AND 연산을 해주게 되면 최하위 비트와 그 밑의 비트가 모두 0이 되는 결과를 얻게 된다!

아니면 __builtin_ctz()함수로 가장 작은 원소를 찾고 지워줘도 된다.

 

 

10. 모든 부분 집합 순회하기

부분 집합 순회를 떠올리면 가장 먼저 생각나는 것은 재귀함수이지만, 비트마스크로 집합을 표현했을 때는 반복문 하나로 충분하다.

 

unsigned int set;
    for(int subset = set; subset != 0; subset = ((subset-1) & set)) {
        // subset은 set의 부분집합이다.
    }

 

(subset - 1) & set을 먼저 생각해보자.

subset 에서 1을 빼게되면 최하위 비트는 0이 되고, 그 밑의 비트는 모두 1이 될 것이다. 여기서 set 이랑 AND 연산을 해주면, set에 존재하지 않는 원소들은 모두 0이 된다. 노트에 끄적이며 일일이 살펴보면 정말로 부분집합이 된다는 것을 알 수 있다.

 

 

처음 블로그 포스팅을 해보았는데 정말 쉽지 않다...