비트마스킹 기법 정리

비트연산자

• a & b - and 연산
• a | b - or 연산
• a ^ b - xor 연산 (둘이 다르면 1, 아니면 0)
• ~a - not
• a << b - a 를 b 비트만큼 왼쪽으로 시프트 a = 001 b = 2 => a << b => 100
• a >> b - a 를 b 비트만큼 오른쪽으로 시프트

집합 표현

• {A, B, C, D, E} => {A} = 10000

원소 추가

• 현재 상태 cur 이 있을 때 p 번 원소 추가시 아래와 같은 코드는 p 번 left shift 를 한 뒤, or 연산을 하므로 내가 원하는 p 번째 자리를 1 로 바꿔서 원소를 추가하듯 동작할 수 있게 된다.
• cur = cur | (1 << p)

원소 삭제

• & 는 둘다 1이어야 1이므로 특정 p 번째 비트만 0으로 만들어 p 번째 비트만 0으로 전환시켜줄 수 있는 방식이다.
• cur = cur & ~ (1 << p);

원소 토글

• ^ 는 다르면 1, 같으면 0인데 p 번째만 1이니 원래 p 번째가 1 이었다면 0으로 0 이었다면 1로 토글될 수 있다.
• cur = cur ^ ( 1 << p )

집합연산

• a | b 합집합
• a & b 교집합
• a & ~b a 에서 b 를 뺀 차집합
• a ^ b a 와 b 중 하나에만 포함된 원소들의 집합

left shift

• 참고한 문제 에서는 전체 크기가 20으로 제한이 되어있다. 그럴 경우 left shift 는 최대치를 려해야 한다.
• 아래와 같이 & 와 ~ 을 활용하면 overflow 를 무시할 수 있다.

right shift

• right shift 의 경우 0보다 작아질 수 없다. 그래서 그냥 >> 만 사용해도 된다.

레퍼런스

백준 15787 기차가 어둠을 헤치고 은하수를
굳건하게 - 비트마스킹이란