비트마스킹이란?
컴퓨터가 이진수 표현을 쓰는 것을 이용하여 bit를 자료구조로 사용하는 기법
비트마스크의 장점
거의 모든 연산이 O(1)의 시간복잡도를 가진다.
비트 연산 종류
& AND
a & b
a와 b 양쪽의 각 비트를 비교하여 모두 1이면 1, 아니면 0으로 계산
| OR
a | b
a와 b 양쪽의 각 비트를 비교하여 하나라도 1이면 1, 아니면 0으로 계산
^ XOR
a ^ b
a와 b 양쪽의 각 비트를 비교하여 서로 다르면 1, 같으면 0으로 계산
~ NOT
~a
a의 각 비트가 1이면 0, 0이면 1로 계산
<<, >> SHIFT
a << b, a >> b
a의 비트를 왼쪽, 오른쪽으로 b칸 만큼 밀어줌 (빈자리는 0으로)
(단순하게 2의 b제곱을 곱하는 것과 나누는 것으로 생각하면 됨)
집합 연산
bit연산을 이용해 비트마스크를 집합으로 쓸 수 있다.
원소 추가
a의 b번째 원소를 1으로 변경
a | (1 << b)
원소 삭제
a의 b번째 원소를 0으로 변경
a & ~(1 << b)
원소 포함 여부
a에 b번째 원소가 포함되어있는지 확인
a & (1 << b)
결과가 0이 아니라면 원소가 포함된 것
원소 토글
a의 b번째 원소를 1이라면 0, 0이라면 1로 바꿈
a ^ (1 << b)
참조
https://velog.io/@alkwen0996/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B9%84%ED%8A%B8%EB%A7%88%EC%8A%A4%ED%81%AC
https://banwolcode.tistory.com/52
https://seoarc.tistory.com/24
