비트 연산

연산	설명	예시 (a = 0101, b = 0011)
a&b AND	두 값의 각 자릿수를 비교해, 두 값 모두에 1이 있을 때에만 1을, 나머지 경우에는 0을 계산한다.	a&b = 0101
a|b OR	두 값의 각 자릿수를 비교해, 둘 중 하나라도 1이 있다면 1을, 아니면 0을 계산한다.	a|b = 0111
a^b XOR	두 값의 각 자릿수를 비교해, 값이 같으면 0, 다르면 1을 계산한다.	a^b = 0110
~a NOT	각 자릿수의 값을 반대로 바꾼다.	~a = 1010

쉬프트 연산

비트를 이동시키는 연산.

• left shift << : 비트를 왼쪽으로 이동시킨다.
  eg) 0001 << 2 = 0100

• right shift >> : 비트를 오른쪽으로 이동시킨다.
  eg) 0001 >> 2 = 0000, 1000 >> 1 = 0100

• 2를 곱하거나 2를 나누는 연산.
  - a << n = $a*2^n$
  - a >> n = $a/2^n$
  eg) a = 0110$_{2}$ = 6$_{10}$, a<<1 = 1100$_{2}$ = 12$_{10}$, a>>1 = 0011$_{2}$ = 3$_{10}$

비트마스킹

이진수 표현을 자료구조로 사용하는 방식. 어떠한 상태를 이진수로 표현하여 공간을 확보하고, 연산 시간 또한 줄일 수 있다.

• 0을 false, 1을 true로 하여 자료의 상태를 표현하는 자료구조로 활용 가능.
• 비트 연산은 대부분 $O(1)$ 만에 일어나기 때문에 더 빠르게 연산할 수 있다.

예제

집합 표현

백준 11723 집합

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
all: S를 {1, 2, ..., 20} 으로 바꾼다.
empty: S를 공집합으로 바꾼다. 

• 한 집합을 비트로 표현해보자. 비트의 인덱스는 숫자를 뜻하고, 해당 비트의 1/0 은 각각 그 숫자가 집합에 존재하는지/존재하지 않는지를 표현할 수 있다. eg) 0010 (오른쪽부터 0으로 시작하여 왼쪽으로 갈수록 증가하는 인덱스) → {1}, 1010 → {1, 3}
• 여기에 비트 연산을 적용하면 집합 연산(추가, 삭제 등)을 매우 빠르게 할 수 있다.

설명	연산	예시 (set=0110={1, 2}, i=2)
i번 원소 추가	set | (1<<i)	= 0110 | 0100 = 0110 = {1, 2} (2는 이미 있는 원소이므로)
i번 원소 삭제	set & ~(1<<i)	= 0110 & ~(0100) = 0110 & 1011 = 0010 = {1}
i번 원소 토글	set ^ (1<<i)	= 0110 ^ 0100 = 0010 = {1}, = 0110 ^ 1000 = 1110 = {1,2,3}
i번 원소 체크(true, false)	set & (1<<i)	=0110 & 0100 = 0100 = {2} (원소 2가 있다), =0110 & 1000=0000={} (원소 3이 없다! => 공집합인 경우 해당 원소가 없다.)
교집합	set1 & set2
합집합	set1 | set2
차집합	set1 & ~set2
둘 중 하나만 포함된 원소들의 집합	set1 ^ set2

        if (operators == "add") {
            cin >> operands;
            ans |= (1<<operands);
        }
        else if (operators == "remove") {
            cin >> operands;
            ans &= ~(1<<operands);
        }
        else if (operators == "check") {
            cin >> operands;
            if (ans & (1 << operands)) 
                cout << 1 << '\n';
            else 
                cout << 0 << '\n';
        }
        else if (operators == "toggle") {
            cin >> operands;
            ans ^= (1<<operands);
        }
        else if (operators == "all") {
            ans = (1 << 21) - 1;
        }
        else if (operators == "empty") {
            ans = 0;
        }