[C++] 비트마스킹(Bitmasking)

비트마스킹

데이터 타입마다 각 메모리 사용 크기가 있다.

만약 int 라고 하면 4byte 즉, 32 bit의 크기를 가진다.
표현하면 0000 0000 0000 0000 0000 0000 0000 0000이 될 것이다. (0과 1을 씀)

만약 아이템이 있고 없고를 구현해야할 때 bool 변수 32개를 쓰는 대신에 하나의 비트를 다룰 수 있을경우,

우리는 int 자료형 하나로 32개의 아이템이 있고 없고를 표현할 수 있다.

 

또한 비트 연산은 연산 속도가 빠르다는 장점을 가지고 있다.

만약 2번째 아이템이 있다면 0100 이런식으로 0을 1로 바꾸어 표현하는 것이다.

 

&, |, ~, ^, >>, << 연산자

• & - AND 연산자로 하나라도 0 이면 0으로 둘다 1이면 1의 출력값을 가진다.
• | - OR 연산자로 하나라도 1이면 1이고 둘다 0이면 0의 출력값을 가진다.
• ~  - NOT 연산자로 0과 1을 바꾸어 준다.
• ^  - XOR 연산자로 두 값이 다르면 1 같으면 0의 출력값을 가짐
• << n , >> n - shift 연산자 오른쪽 혹은 왼쪽으로 n비트 만큼 이동 후 뒤에는 0으로 채움

공집합 만들기

     int s = 0;

• s 집합 : 0000 0000 0000 0000 0000 0000 0000 0000

s에 원소를 추가

     s |= (1<<2);

• (1<<2) : 1을 2칸 왼쪽으로 이동 1 -> 10 -> 100
• s |= : OR연산 후 s 에 대입 (8비트만 쓴다고 가정)

0000 0000 | 0100 = 0000 0100 이것을 s에 대입하면 0번째부터 센다고했을 때 2번째 비트가 1로 켜짐

 

s에 원소를 삭제

     s &= ~(1<<2);

• ~(1<<2) : 0100에서 0과 1을 바꿔줌 1011
• s &= : AND 연산 후 s 에 대입

0000 0100 & 1011 = 0000 0000 : 0번째부터 센다고했을 때 2번째 비트가 0으로 꺼짐

 

s에 원소가 있는 지 없는 지 확인

     if(s & (1<<2)){
        cout << yes! << endl;
    }

• 0000 0100 & 0100 = 0010 = 4 = true
• 0000 1000 & 0100 = 0000 = 0 = false

s의 최소 원소 지우기

    s &= (s-1); // s = 0101 1110 이라고 가정

• (s-1) : 0101 1110 - 0000 0001 = 0101 1101 이런식으로 최소 원소의 1만 0으로 바뀌게 됨
• & : 0101 1110 & 0101 1101 = 0101 1100

 

s의 모든 원소 채우기

     s |= (1<<8) - 1 ;

• 10000 0000 - 1 = 1111 1111

이런식으로 모든 원소를 채울 수 있음