비트 마스킹 C++

연산자의 종류

&	AND연산자. 두 값이 모두 1이라면 1의 출력값을 가진다.
\|	OR연산자. 두 값중 하나라도 1이라면 1의 출력값을 가진다.
~	NOT연산자. 0은 1로, 1은 0으로 바꾼다.
^	XOR연산자. 두 값이 서로다르면 1을 출력값으로 가지고, 다르면 0을 출력값으로 가진다
>>	SHIFT연산자. 오른쪽으로 비트를 1회 이동시킨다.
<<	SHIFT연산자. 왼쪽으로 비트를 1회 이동시킨다.

4비트라고 가정.

A = 6    //0110
B = 10  //1010

A&B: 2     //0010
A|B: 14    //1110
~A: 9      //1001
A^B: 12    //1100
A>>1: 3    //0011
A<<1: 12   //1100

S의 총 원소개수가 10개라고 가정

공집합 만들기

S = 0;

꽉찬 집합 만들기

S = (1<<10)-1;

원소N 추가하기

S |= (1<<N);

원소N 삭제하기

S &= ~(1<<N)

원소N이 있는지 확인하기

if(S&(1<<N))

최소원소 찾기

int first = (S&-S)

2의 보수의 특성을 활용.

-를 붙이게 되면 최소원소를 제외한 최소원소부터 왼쪽의 모든 비트가 반전이 됨.

S가 1110 0100이라면 -S는 0001 1100

최소원소 지우기

S &= (S-1)

원소N 토글(있으면 삭제, 없으면 추가)

S ^= (1<<N)

11723번: 집합

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

www.acmicpc.net