C++ 비트 마스킹 (비트 연산) [컴공과고씨]

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

만약 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<<3); 

-> (1<<3) : 하나씩 해보면 1을 먼저 3칸 왼쪽으로 이동 1 에서 > 10 > 100 > 1000
-> s |= : OR연산 후 s 에 대입 (8비트만 쓴다고 가정)
0000 0000 | 1000 = 0000 1000 이것을 s에 대입하면 0번째부터 센다고했을 때 3번째 비트가 1로 켜짐

s에 원소를 삭제

     s &= ~(1<<3);

-> ~(1<<3) : 1000에서 0과 1을 바꿔줌 0111
-> s &= : AND 연산 후 s 에 대입
0000 1000 & 0111 = 0000 0000 : 3번째 비트 꺼짐

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

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

-> 0000 1000 & 1000 = 1000 = 8 = true
-> 0000 0100 & 1000 = 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
이런식으로 모든 원소를 채울 수 있음