비트마스크 (Bitmask)

 

부호 없는 N비트 정수형 변수는 N자리의 이진수로 쓸 수 있다. 각 비트가 표현하는 값은 2^0 ~ 2^N-1까지이고, 이때 2^0를 나타내는 비트를 최하위 비트(least significant bit), 2^N-1을 나타내는 비트를 최상위 비트(most significant bit)라고 한다.

 

비트 연산

AND : 두 정수를 한 비트씩 비교하면서 두 정수의 해당 비트가 모두 1일 때만(켜져 있을 때만) 결과의 비트를 켠다.

ex) 1111 & 1101 => 1101

 

OR : 두 정수를 한 비트씩 비교하면서 두 비트 중 하나라도 켜져 있을 경우 결과 비트가 켜진다.

ex) 1111 | 1101 => 1111

 

XOR : 두 정수를 한 비트씩 비교하면서 하나는 켜져 있고 하나는 꺼져 있을 경우 결과 비트가 켜진다.

ex) 1111 ^ 1101 => 0010

 

NOT : 한 정수의 모든 비트를 반대로 바꾼다. 켜져 있을 경우 끄고 꺼져 있을 경우 킨다.

ex) ~1101 => 0010

 

SHIFT : 한 정수의 모든 비트들을 왼쪽 또는 오른쪽으로 원하는 만큼 움직인다. 반대 방향의 비트들은 0으로 채워진다.

ex) 754(10 1111 0010) << 2 => 3016(1011 1100 1000)

     754 >> 2 => 188(1011 1100)

 

 

주의 사항

1. 특정 언어에서 비트 연산자의 우선순위는 비교 연산자보다 낮을 수 있기 때문에 괄호를 붙이는 습관을 갖는다.

2. 정수 자료형의 크기를 주의한다. 8바이트 정수 자료형과 4바이트 정수 자료형을 비트 연산하거나 하면 오버플로가 발생한다.

3. 부호 있는 정수형을 사용할 때 MSB가 1일 경우 음수를 표현한다. 이 경우에 모든 비트를 사용하면 버그가 발생할 수 있다.

4. N비트 정수를 N비트 이상 왼쪽으로 시프트 하는 경우에 대한 결과 (C++)

 

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

/*
	참고 : 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2, 구종만, 인사이트
*/
#include <iostream>
using namespace std;

//집합의 크기 구하기
int bitCount(int x)
{
    if (x == 0)
        return 0;
    return x % 2 + bitCount(x / 2);
}

int main()
{
    /*
        0부터 9까지 10개의 원소를 갖는 집합 a
    */
    int fullElement = (1 << 10) - 1; //모든 원소를 갖는 집합
    int nullSet = 0;                 //공집합

    int num = 3;          //추가하고자 하는 원소
    int originalSet = 18; //0001 0010으로 1번째 원소와 4번째 원소가 존재
    originalSet |= (1 << num);
    printf("%d\n", originalSet); //26(0001 1010) -> (3번째 비트가 켜짐으로써 3번째 원소가 추가되었음)

    if (originalSet & (1 << num)) //num 원소가 존재하는지 확인
    {
        cout << "3번째 원소가 존재함\n";
    }

    originalSet &= ~(1 << num); //num 원소 삭제 (num 원소가 이미 집합에 없더라도 안전)
    printf("%d\n", originalSet);

    originalSet ^= (1 << num); //num 원소 토글, 1이면 0으로 0이면 1로 스위칭, 결과 -> 26(0001 1010)

    int originalSet2 = 70;                           //0100 0110
    int added = (originalSet | originalSet2);        //합집합
    printf("합집합 -> %d\n", added);                 //94(0101 1110)
    int intersection = (originalSet & originalSet2); //교집합
    printf("교집합 -> %d\n", intersection);          //2(0000 0010)
    int removed = (originalSet & ~originalSet2);     //차집합 (originalSet - originalSet2)
    printf("차집합 -> %d\n", removed);               //24(0001 1000)
    int toggled = (originalSet ^ originalSet2);      //originalSet과 originalSet2중 하나의 집합에만 포함된 원소들의 집합
    printf("toggled -> %d\n", toggled);              //94(0101 1110)

    printf("집합의 크기 -> %d\n", bitCount(originalSet));
    printf("집합의 크기2 -> %d\n", __builtin_popcount(originalSet)); //gcc/g++ 컴파일러 내장 함수

    /*
        집합의 크기를 구하는 내장 함수
        visual c++ => __popcnt(originalSet);
        Java => Integer.bitCount(originalSet);
    */

    printf("최소 원소 위치 => %d\n", __builtin_ctz(originalSet)); //1반환 (첫 번째 비트가 최소 원소), gcc/g++ 컴파일러 내장 함수
    printf("최소 원소 => %d\n", (originalSet & -originalSet));    //2반환 (2가 최소 원소)

    /*
        최소 원소 위치를 구하는 내장 함수
        visual c++ => _BitScanForward(originalSet);
        Java => Integer.numberOfTrailingZeros(originalSet);

        __builtin_ctz()는 매개 변수로 0을 넣지 않도록 주의한다.
    */

    originalSet &= (originalSet - 1);
    printf("최소 원소 지우기 => %d\n", originalSet); //24(0001 1000)

    //24(0001 1000)의 부분집합 => 0001 0000, 0000 1000, 0001 1000, 공집합은 반환하지 않는다.
    for (int subset = originalSet; subset; subset = ((subset - 1) & originalSet))
    {
        printf("부분집합 => %d\n", subset);
    }

    return 0;
}